[jdom-interest] Re: List's in JDOM - a small essay

[Joseph Bowbeer]

Is there more information about the singly linked list design?  I don't want
to jump in without first understanding more of the details.

That said...  Because JDOM is a representation for generic documents which
can have as varied a set of structures and intended uses as any data
structure I know, we need to make sure that our underlying representation
supports a wide range of uses.

We should also be careful not to violate the principle of "least
astonishment".  That is, if getChildren returns a List then users will
expect that they can go forward or backward with equal ease.  No one would
expect that JDOM would be returning a list representation that performed
significantly worse than a LinkedList during some types of traversal.

It's interesting to note that reverse traversal is sometimes used without
the user's knowledge.  For example, the LinkedList (doubly-linked)
implementation uses reverse traversal to implement random accessors: get(i).
When accessing element 'i' of a LinkedList, the accessor will start from the
end and iterate backwards if 'i' is closer to the end.

I'm interested in comparing the singly linked design with the design I
sketched in a previous message, which is a sequential list implementation
based on a reversible, mutable FilterListIterator and using an ArrayList or
a LinkedList as the underlying representation.

Using an ArrayList as the underlying representation is very lean in terms of
memory usage and very performant for a large set of uses.  A filtered
version of this would have the performance characteristics of a
doubly-linked list, with no significant additional memory overhead.

--
Joe Bowbeer