[jdom-interest] Re: List's in JDOM - a small essay
jozart at csi.com
Fri Mar 9 11:30:18 PST 2001
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.
More information about the jdom-interest