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

[Richard Cook]

It's OK java.util.LinkedList will "perform as could be expected for a
doubly-linked list."


> -----Original Message-----
> From: jdom-interest-admin at jdom.org
> [mailto:jdom-interest-admin at jdom.org]On Behalf Of Ken Rune Helland
> Sent: Friday, March 09, 2001 8:44 AM
> To: Joseph Bowbeer; Jools
> Cc: jdom-interest at jdom.org
> Subject: Re: [jdom-interest] Re: List's in JDOM - a small essay
>
>
> 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
>
> _______________________________________________
> To control your jdom-interest membership:
> http://lists.denveronline.net/mailman/options/jdom-interest/yourad
dr at yourhost.com