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

[Ken Rune Helland]

Jools wrote:
>I'm currently rewriting specific portions of JDOM to use a FilterList
>which internally uses a singly linked list and allows filtering of the
>items contained therein.
>
>
>Iterating
>~~~~~~~~~
>
>
>Why use a singly linked list ? Because most operations on a JDOM object
>are via an iterator, and this is normally in one direction. Thus
>the FilterList is optimized for this operation, in JDOM terms it means
>that the following is very efficient;
>
>
>Iterator iter = element.getChildren("foo").iterator();
>while (iter.hasNext()) {
>         iter.next();
>}


At 04:41 PM 3/8/2001 -0800, Joseph Bowbeer wrote:
>PS - Correction to the information in my previous message about traversing a
>list in reverse:
>
>There is no List.reverse(), but there is a Collections.reverse(List).
>However, I believe the recommended way to traverse a list in reverse is as
>follows:
>
>List foos = element.getChildren("foo");
>for (Iterator iter = foos.listIterator(foos.size()); iter.hasPrevious(); )
>{
>     bar( iter.previous() );
>}


This woud be very inefficient with a singely linked list.
The only way to get to the previos item woud be to traverse
the whole list again.

With a doubly linked list it woud be very efficient.

Is the cost of having the list dobbel linked so great?
One reference per item extra in memory cost and two extra
reference assignments when inserting an item in cpu cost?


KenR