Seeking further understanding on Iterators in java

Question

If I am using a for loop (the standard for loop, not an enhanced for statement), I fail to see how an iterator increases efficiency when searching through a collection. If I have a statement such as:

(Assuming that aList is a List of generic objects, type E, nextElement refers to the next element within the list)

for (int index = 0; index < aList.size(); index++){
E nextElement = aList.get(index);
// do something with nextElement...
}

and I have the get method that looks something like:

Node<E> nodeRef = head;
for (int i = 0; i < index; i++){
    nodeRef = nodeRef.next;
    // possible other code
}

this would essentially be searching through the List, one element at a time. However, if I use an iterator, will it not be doing the same operation? I know an iterator is supposed to be O(1) speed, but wouldn't it be O(n) if it has to search through the entire list anyway?

Answer 1

It's not primarily about efficiency, IMO. It's about abstraction. Using an index ties you to collections which can retrieve an item for a given index efficiently (so it won't work well with a linked list, say)... and it doesn't express what you're trying to do, which is iterate over the list.

With an iterator, you can express the idea of iterating over a sequence of items whether that sequence can easily be indexed or not, whether the size is known in advance or not, and even in cases where it's effectively infinite.

Your second case is still written using a for loop which increments an index, which isn't the idiomatic way of thinking about it - it should simply be testing whether or not it's reached the end. For example, it might be:

for (Node<E> nodeRef = head; nodeRef != null; nodeRef = nodeRef.next)
{
}

Now we have the right abstraction: the loop expresses where we start (the head), when we stop (when there are no more elements) and how we go from one element to the next (using the next field). This expresses the idea of iterating more effectively than "I've got a counter starting at 0, and I'm going to ask for the value at the particular counter on each iteration until the value of the counter is greater than some value which happens to be the length of the list."

We're fairly used to the latter way of expressing things, but it doesn't really say what we mean nearly as may as the iterator approach.