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

Ken Rune Helland kenh at csc.no
Fri Mar 9 01:42:26 PST 2001


At 09:28 AM 3/9/2001 +0000, Richard Cook wrote:
>It's OK java.util.LinkedList will "perform as could be expected for a
>doubly-linked list."
>

Yes, LinkedList will, but i'm talking about Jools FilterList witch
will be singel linked acording to his post.


Best Regards
KenR


> > -----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
>
>_______________________________________________
>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