Clever Geek Handbook

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?

+3


source to share


5 answers


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.

+1


source


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.



+1


source


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.

+1


source


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();
+1


source


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.

+1


source






More articles:


All Articles