## 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
2016-12-28 15:12 1 Answers

## Answers to Iterating through LinkedList in O(n) ( 1 )

1. 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-`get`ting it.