CODEWITHSUNDEEP
javalinked-listreverselistiterator
Vitruvie
Vitruvie

Reputation: 2327

Is linkedList.listIterator(linkedList.size()) optimized?

I'm trying to create a reverse ListIterator for a LinkedList, and was going to just implement it as a wrapper to linkedList.listIterator(linkedList.size()) that swaps the next and previous operations, but then realized that if LinkedList#listIterator(int) is implemented to just traverse forwards to the position specified, using it to start at the end would be terribly unoptimized, having to traverse the list twice rather than once, when the list supports going directly to the end. Is linkedList.listIterator(linkedList.size()) optimized to not traverse the entire list?

Upvotes: 2

Views: 70

Answers (2)

Shashank
Shashank

Reputation: 13869

A ListIterator uses indexes to identify which element to start at. In the Oracle docs for LinkedList, it says:

All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

Thus when you do linkedList.listIterator(linkedList.size()), it will traverse the list backwards exactly 0 steps to grab the correct index. So, you could say that it's as optimized as it possibly can be. Go ahead and wrap that iterator.

Upvotes: 2

Evgeniy Dorofeev
Evgeniy Dorofeev

Reputation: 135992

It is optimized, it's here 

private class ListItr implements ListIterator<E> {

...

ListItr(int index) {
    // assert isPositionIndex(index);
    next = (index == size) ? null : node(index);
    nextIndex = index;
}

...

Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {  <-- if index less than half size go forward
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {                     <-- otherwise backwards
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

Upvotes: 1

Related Questions