Lazy Lists In Java – Part 2
Mark Rhodes, October 11th, 2011
In my last post back in June, I introduced a new data structure, the PatchWorkArray, which performs insertions and deletions lazily in an attempt to improve performance over the lifetime of the list. In this post, I’ll detail a simple extension to this class which makes it more practically usable and show how it compares [...]
Lazy Lists in Java
Mark Rhodes, June 24th, 2011
This post outlines a general purpose alternative to ArrayLists which provide lazy insertions and deletions to speed up those operations. The Java source code, unit tests, javadoc and jar file for all the classes mentioned in this blog is available here:scottlogic-utils-mr.zip. ArrayLists are perfect when you want to get elements by their indices but not [...]
Lists with Fast Insertions and Removals in Java
Mark Rhodes, April 19th, 2011
This post describes the implementation of a List in Java which allows log time removals and insertions. Lists are probably the most useful data structures in programming. Java provides a number of ways of creating a list out of the box with regular arrays, and the ArrayList, LinkedList and Vector classes in the java.util package. [...]
Sorted Lists in Java
Mark Rhodes, December 22nd, 2010
This post goes through an implementation a SortedList in Java which ensures its elements are kept in order and guarantees O(log(n)) run time for all the basic operations: get, contains, remove and add. The source code, javadoc, unit tests and class files for this post are available here: scottlogic-utils-mr-1.4.zip. Sorting is one of the most [...]