[jdom-interest] JDOM BOF at SD West: problem resolving

[Joseph Bowbeer]

> > When does SinglyLinkedList beat ArrayList?

> An ArrayList *can* be more space efficient, but only at the cost
> of CPU.  [...] So what you generally have is a list of 10 slots of
> which generally only 3 are filled, wasting the rest of the space.

That's using the default initialCapacity.  For JDOM, a different
initialCapacity might be more appropriate.

Consider a larger list containing N elements.  If the list is implemented as
an ArrayList and it has exceeded its initialCapacity at least once, then the
underlying array has no more than N/2 empty slots.  Whereas a SinglyLinked
list with the same number of elements will have N "wasted" 'next' links.  In
other words, ArrayList wastes 25% less in this case.

> add(end) can be fast too because a SinglyLinked can store
> it's tail pointer.

But SinglyLinked.add(end) always has to allocate a new node, whereas
ArrayList only allocates when the list grows by 50%.

--
Joe Bowbeer