Iterating through LinkedList in O(n)

Question

I think I have this understanding right, but wanted to double check.

Say we are iterating through a LinkedList like this:

for(int i = 0 ; i < lst.size() ; i++) {
  System.out.println(lst.get(i));
}

lst.get() runs in O(n) time, and we're calling it n times. So, would this code have O(n^2) time?

Sorry if this is a dumb question - just want to make sure I'm getting this correctly. I'm assuming it would be better to use Iterator, where we could iterate through the list in O(n) time?


Show source
| java   | algorithm   | linked-list   | runtime   2016-12-28 15:12 1 Answers

Answers ( 1 )

  1. 2016-12-28 16:12

    On a LinkedList as defined by the JDK...

    Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

    So yes, get(n) is O(n). Of course, an implementation could try to optimize (keeping track of the last node returned by get, for instance, and potentially navigating from there). Oracle's version doesn't. get calls an internal node method that finds the node:

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
    

    ...and node works as defined above: It starts at the beginning or end, without reference to any previous access:

    Node<E> node(int index) {
        // assert isElementIndex(index);
    
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
    

    I'm assuming it would be better to use Iterator, where we could iterate through the list in O(n) time?

    Yes, absolutely. Because the iterator remembers what the next node is rather than re-getting it.

◀ Go back