Iterating from the end of a list
I know that we can iterate over the list in reverse order like this:
List<Object> lst;
ListIterator<Object> i = lst.listIterator(lst.size());
But is it effective, if lst
any LinkedList
? I mean, when we get a ListIterator
pointing to the end of a list, does the reprogramming through the list from start to position list.size()
(takes O(n)
time, where n
is the size of the list)?
If so, is there a way to avoid this?
The javadoc states that LinkedList is a doubly linked list, so I expect descendingIterator()
that returns an iterator pointing to the tail of the list like O(1)
. Note that descendingIterator
is an interface Deque
.
Now it is difficult to tell if the operator is lst.listIterator(lst.size())
also O(1)
because it is undocumented if the method listIterator
optimizes the fact that the next element from lst.size()
is a tail.
The documentation states that it LinkedList
is a " Doubly-linked implementation of the List and Deque interfaces". Therefore, each item in the list is referenced as next AND previous items. So, the iterator should be as fast in reverse order as it is in natural order.
It doesn't iterate over the list to create an iterator.
The best place to look for solutions is in Source Code .
if (index < (size >> 1)) {
next = header.next;
for (nextIndex=0; nextIndex<index; nextIndex++)
next = next.next;
} else {
next = header;
for (nextIndex=size; nextIndex>index; nextIndex--)
next = next.previous;
}
As you can see, it will try to reach the index using the shortest path from either the first node or the last node.
LinkedList also implements the Deque interface.
So if you implement it as
Deque list = new LinkedList();
Or, if you additionally need list methods
LinkedList list = new LinkedList();
you can use
list.descendingIterator();
Your code won't work, the index is lst.size()
out of scope, maybe you meant it lst.size()-1
. But still it is not a reverse iterator, it is a forwarding iterator that instead of starting at 0 starts at the element you specified. In this case, you will only read the last element and get to the end.
LinkedList
implements the interface Deque , which provides Deque.descendingIterator . In this case, both starting the iterator and going to the next (previous) element are operations O(1)
. In the first case, this is because the implementation Deque
retains a reference to both the beginning and end of the queue, in the second, because it LinkedList
is a doubly linked list in which each element retains a reference to both its successor and its predecessor.