[jdom-interest] JDOM BOF at SD West: problem resolving
jozart at csi.com
Thu Apr 12 22:10:25 PDT 2001
> > 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%.
More information about the jdom-interest