Why are iterators faster for non-contiguous containers?

Question

This other topic on Stack Overflow, "traditional for loop vs Iterator in Java", discusses the performance difference between using indexes and using iterators. The top answer points out that there's a very significant difference (a factor of 60.000) when dealing with containers such as LinkedList.

I expect this has something to do with caching. If that's so, how do iterators get around this issue? If it has nothing to do with cache misses, what is it that makes iterators for non-contiguous containers so much faster?

For a linked list, access by index means traversing from the head each time. That adds up. The iterator just follows the `next` pointer. — Daniel Fischer, Nov 03 '12 at 21:31
@PaulManta You can look at the [`LinkedList` source](http://developer.classpath.org/doc/java/util/LinkedList-source.html) to see. — arshajii, Nov 03 '12 at 21:33

score 2 · Accepted Answer · answered Nov 03 '12 at 21:32

The difference for linked lists isn't any constant factor - it's the difference between "a step" taking O(1) or O(N). (So the bigger the list, the bigger the difference.)

An iterator retains whatever state it needs to "take the next step". For a linked list, taking the next step means just following a reference from one node to the next... whereas accessing an element by index means starting at the head and executing the same "move next" step that many times.

Compare that with ArrayList, where the iterator just needs to remember the current index, and then both "random access" and "sequential" access involve simply going straight to the right element of the array.

So it's not really caching as such - it's retaining state. Whether an iterator is faster than access by index depends on what that access by index has to do. In the case of ArrayList, it's cheap. In the case of LinkedList, it's not.

Why are iterators faster for non-contiguous containers?

1 Answers1