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

Dennis Sosnoski dms at sosnoski.com
Fri Apr 13 13:21:10 PDT 2001

The memory comparison between SinglyLinkedList and ArrayList is even worse than
discussed here, because this discussion ignores the object overhead in Java. I'd
suspect that normal JVMs are going to use *at least* 16 bytes for the representation
of any Java object (including the class reference, the synchronization lock hook,
etc.). The memory comparison is then between a 4 byte reference in an ArrayList and a
list node that's 4 times the size.

  - Dennis

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.
> > 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
> _______________________________________________
> To control your jdom-interest membership:
> http://lists.denveronline.net/mailman/options/jdom-interest/youraddr@yourhost.com

More information about the jdom-interest mailing list