reverse-iterator for LinkedList

[Andreas Leitgeb]

In some app of mine I've got a LinkedList of items. Now,
I want to check the last couple of items for some condition.

In practice I expect the list to be about 30 elements
long, and only the last three elements to be actually
visited. Oh and the context is somewhat time-critical.

Now, I think that an Iterator (actually ListIterator) would be
appropriate for my task, but the only way to get one seems to be
through method listIterator(int index). I can't help, but passing
in the lists size for the index feels like it would search forward
completely through the list to obtain an iterator that starts
from end.

Is there some better way to just scan the "last few elements"
from a LinkedList, or can someone assure me that calling
listIterator with an index at end will be efficient, or
is it best to redesign my app to build up the list in reverse
order in the first place, so I can use a "normal" iterator?

Afaik, the LinkedList is doubly-linked, so iterating from the
end should be a breeze, but indexing rather costly...

What's java's idiom for C++/stl's list::rbegin() ?

 

[Daniel Pitts]

In some app of mine I've got a LinkedList of items. Now,
I want to check the last couple of items for some condition.

In practice I expect the list to be about 30 elements
long, and only the last three elements to be actually
visited. Oh and the context is somewhat time-critical.

Now, I think that an Iterator (actually ListIterator) would be
appropriate for my task, but the only way to get one seems to be
through method listIterator(int index). I can't help, but passing
in the lists size for the index feels like it would search forward
completely through the list to obtain an iterator that starts
from end.

Is there some better way to just scan the "last few elements"
from a LinkedList, or can someone assure me that calling
listIterator with an index at end will be efficient, or
is it best to redesign my app to build up the list in reverse
order in the first place, so I can use a "normal" iterator?

Afaik, the LinkedList is doubly-linked, so iterating from the
end should be a breeze, but indexing rather costly...

What's java's idiom for C++/stl's list::rbegin() ?

LinkedList.listIterator will start from the end if that is closer to
where you need.
LinkList.listIterator(0) and LinkList.listIterator(size()) take the same
time;

 

[Eric Sosman]

In some app of mine I've got a LinkedList of items. Now,
I want to check the last couple of items for some condition.

In practice I expect the list to be about 30 elements
long, and only the last three elements to be actually
visited. Oh and the context is somewhat time-critical.

Now, I think that an Iterator (actually ListIterator) would be
appropriate for my task, but the only way to get one seems to be
through method listIterator(int index). I can't help, but passing
in the lists size for the index feels like it would search forward
completely through the list to obtain an iterator that starts
from end.

"Use the source, Andreas," and you'll find that LinkedList
initializes its ListIterator by searching from the nearer end.

Is there some better way to just scan the "last few elements"
from a LinkedList, or can someone assure me that calling
listIterator with an index at end will be efficient, or
is it best to redesign my app to build up the list in reverse
order in the first place, so I can use a "normal" iterator?

Keeping the list in the other order seems plausible, but
I can't say whether it would be a good idea without having a
lot more information about your situation. Are you positive
that a LinkedList -- or even any flavor of List -- is the
right data structure for the job at hand?

 

[Lew]

"Use the source, Andreas," and you'll find that LinkedList
initializes its ListIterator by searching from the nearer end.

"Use the Javadocs" is better advice - you get the answer in the documentation
for the class:

 

[bugbear]

"Use the Javadocs" is better advice - you get the answer in the
documentation for the class:

If you read further on that page, you'll find:

http://java.sun.com/javase/6/docs/api/java/util/LinkedList.html#descendingIterator()

which "may" be helpful.

BugBear

 

[Andreas Leitgeb]

"Use the source, Andreas," and you'll find ...

See my answer to Lew's followup on this.

Keeping the list in the other order seems plausible, but
I can't say whether it would be a good idea without having a
lot more information about your situation. Are you positive
that a LinkedList -- or even any flavor of List -- is the
right data structure for the job at hand?

The collection is primarily used as a stack, but with extra
read-accesses for dumping the stack (from bottom to top)
casually, and that extra one to search from top to bottom
for first occurrance of an item that meets some condition.
Practically, even the maximum size is strictly pre-determined
at a point long before the first item is added, so a plain
array would have been just as well workable.

Eventually I will do some performance tests and consider
switching to an array, but there are other areas to deal
with first. For now, I just wanted to lock out the possi-
bility of *really bad* performance for indexing to the end
of a LinkedList. Fortunately it now *is* locked out

 

[Andreas Leitgeb]

"Use the Javadocs" is better advice - you get the answer in the documentation
for the class:

I did look at the docu, but only at the method's description, and missed
that line in the class' overview.

Thanks a lot for the pointer. I agree, that documented information
beats what is found from source, as long as it is plausible.

If performance was still bad, then next step would be to see, if the
implementation really adheres to its docu

 

[Andreas Leitgeb]

If you read further on that page, you'll find:
http://java.sun.com/javase/6/docs/api/java/util/LinkedList.html#descendingIterator()
which "may" be helpful.

That's the ultimate answer!

The reason I didn't find that myself was, that it is a 1.6-feature, and
my bookmark to sun's api-doku still pointed to 1.5's docu. Meanwhile
updated.

Thanks!

PS: that's the first new and useful feature of 1.6 that I've
become aware of No doubt there'll be more...

 

[Andreas Leitgeb]

LinkedList.listIterator will start from the end if that is closer to
where you need.
LinkList.listIterator(0) and LinkList.listIterator(size()) take the same
time;

Thanks for correcting my wrong assumption!
(for more, see the other subthreads.)

 

[voorth]

Thanks for correcting my wrong assumption!
(for more, see the other subthreads.)

And, of course, in Java 6 there is LinkedList.descendingIterator()

 

[Lew]

PS: that's the first new and useful feature of 1.6 that I've
become aware of No doubt there'll be more...

Some of them are listed in
<http://java.sun.com/developer/technicalArticles/J2SE/Desktop/javase6/beta2.html>