[jdom-interest] Re: JDOM BOF at SD West: problem resolving
jhunter at collab.net
Thu Apr 12 22:17:15 PDT 2001
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
> > 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
More information about the jdom-interest