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

[Jason Hunter]

Joseph Bowbeer wrote:
> 
> > > 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.

Actually, ArrayList is hard-coded to grow 50% at a time.  That means it
wastes at most 1/3 once you're past 7 elements (assuming a starter of
10).  The cost for the tigher memory is an awful lot of growing and
array copies.  It'll be interesting what the performance numbers
indicate.

> > 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%.

When it grows by 33%.  Here's the growth pattern with a default of 10:

10 -> 16 -> 25 -> 39 -> etc

-jh-