Re: memory-friendly List implementations
Mark Rafn wrote:
Yup. You then lose the constant-time indexed access, though. get(int) now
becomes linear based on the number of blocks.
That can be improved to logarithmic by recursively nesting the blocks.
In the extreme case, the list is implemented as a binary tree under the
hood, with the bit sequence of the index giving a series of left/right
turns to make from the root down to the correct object. The number of
links to follow is O(log n) in this case. When the list reaches 2^foo
size, a new root node is created with the old one as left child and new
list items develop the right side of the tree. When it's doubled again,
this process happens again, and so forth. Of course, the index bit
sequence used to navigate to an item has to be read from left to right
starting with the nth bit and ending with the zeroth, with n the tree's
height minus 1. The height is easy to track, though, since you can just
stuff a zero in it for an empty list and add one every time a new root
node is created. Memory can be saved by leaving unused parts of the tree
absent, with a null child reference. An empty list has a null root node,
a height of zero, and a grow threshold of one. Go to add an item and the
threshold is reached, so a new root node is made, the old (null) added
to it as its left child, and the object stored at index 0. The height's
now 1, so the height minus 1 is 0 and no navigation is done and the
object's stored at the root. The theshold is doubled to 2. Add another
item and the threshold is reached again, so we end up with a root node
with a left child node holding the object. The index 0 is now read to 1
bit to find that object, and that bit is a 0, so you make one left from
the root. The new object's index of 1 has the bit a 1, so it's stored by
creating a right child of the root node and storing the object there.
Turning the index into a path is cheap and O(log n) as well: you can
just take a copy of the grow threshold, halve it, and & the index with
this to get the first left/right choice; halve it and & the index for
the second; and so forth. For the two-element list above, the threshold
is 2 (meaning it's full) so we'd halve that (1) and look at index & 1,
i.e. the zeroth bit. For a three- or four-element list the threshold has
become 4, so we'd check index & 2 and then index & 1 in turn.
You could also use a tree (or a tree of arrays) structure to balance space,
sequential access, and indexed access patterns.
See above. You can get O(log n) indexed access out of that too.
Sequential access is had by either the usual traversal algorithm or
putting the linked list prev and next refs into the leaf node objects.
There's probably also a way to halve the size of these trees by storing
objects in all the nodes rather than only the leaf nodes too, but I
can't be arsed to reinvent it from scratch right now. :)
That said, jakarta commons has a collections package that provides some useful
implementations, and more importantly some useful abstract base classes that
may be easier to extend than writing from scratch.
Linkie?
And THAT said, the previous responses which advised to change the system not
to NEED such an operation are better than making a list which can do it.
That depends on the system's ultimate requirements. It may or may not be
possible, separately for each system where this question arises.