Why iterating is more preferable than random access

Question

The following page states

The List interface provides four methods for positional (indexed) access to list elements. Lists (like Java arrays) are zero based. Note that these operations may execute in time proportional to the index value for some implementations (the LinkedList class, for example). Thus, iterating over the elements in a list is typically preferable to indexing through it if the caller does not know the implementation.

What does this mean? Does it mean I should prefer

ListIterator<Integer> iterator = list.listIterator(0);
iterator.next()
iterator.next()

over

list.get(1)

If so, why? If the underlying list implementation is plain Array, get will be executed in constant time. But using iterator it's O(n). What am I missing here?

Do they mean I should use list.listIterator(1); instead of list.get(1)?

Answer 1

No. But you should prefer

for (Integer value : list) {
    // do something with value
}

(or a loop using the list's iterator explicitly)

over

for (int i = 0; i < list.size(); i++) {
    Integer value = list.get(i);
    // do something with value
}

If the list is a linked list, the first one is O(N), whereas the second one is O(N^2). Indeed, at each iteration, it needs to traverse the list (from the start or the end, depending on the value of i) until it gets to the ith position. That doesn't happen when you use an Iterator or a foreach loop.

Another good reason is that, in the case of concurrent lists, the Iterator can be consistent (i.e. iterate on a consistent snapshot of the list made when the iterator is created). That can't be the case with an iteration using the indices of the list.

Answer 2

I'm almost certain it's implying that to loop through all elements in a list it is preferable to iterate rather than, for example:

// possibly slow depending on List implementation used
for (int i = 0; i < list.size(); ++i)
{
    Foo bar = list.get(i);
}

In the case of a LinkedList where random access is not O(1), every single time you call list.get(i) you are having to iterate from the start all the way to i which is unnecessary.

---

Your example of pure random access (rather than looping through everything) is:

1. In the case of a LinkedList, more verbose (but basically what get(i) does under the hood)

2. In the case of an ArrayList, actually slower than get(i)