Of course, if, as in the proposed scenario, you have 65MB of
_references_ alone (which seems a lot), then a singly linked list
would increase the resident requirement to 130MB and a doubly linked
one to 196MB. This may or may not be considered an improvement over
ArrayList's performance.

I don't know the details of how java.util.LinkedList is implemented
though - it might use more than this, or it might use less (well,
130MB seems like a minimum any way you do it).

It really needs to be said that with 65MB of references, you are
probably more worried about the space needed by the actual objects
being referred to - unless there are multiple repetitions of the same
reference within those 65MB.

Wouldn't this be a useful thing to have a protected method decide so
that the policy can be modified by subclasses?

Cheers
    Bent D

Actually, even if it only increment by 5% the instantaneous
memory use is still double (old copy, slightly larger new copy)
the actual requirment.

  BugBear

Technically true, but the LinkedList will already be using vastly more
memory than ArrayList by the time there is a problem. LinkedList is a
good answer to very few questions.

Tom Hawtin

As does the JDK; AbstractList and AbstractSequentialList are damned useful
things.

   Unless you can randomly access the blocks too, in which case the index
access is O(2) (i.e. one operation to find the relevant block, and another
operation to find the relevant item within that block) which is O(1). When
expanding the list, you'd have to allocate space for more blocks, and copy
the references to the block, which is a bit faster than copying the
references to each element within the block. It's basically the same
asymptotic runtime performance, but you're just playing around with the
constants.

   If you allow blocks of blocks, then you basically have a tree, and so
index access becomes O(log(n)).

   - Oliver

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.

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. :)

Linkie?

That depends on the system's ultimate requirements. It may or may not be
possible, separately for each system where this question arises.