The Cost of Iterating

Let’s look at the iterator we just wrote and analyze its cost:

private class ArraySetIterator implements Iterator<T> {
  private int cursor;

  ArraySetIterator() {
    this.cursor = 0;
  }

  @Override
  public boolean hasNext() {
    return cursor < size;
  }

  @Override
  public T next() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    return arr[cursor++];
  }
}

I added a constructor that technically is not needed, but it makes it clearer what each part of the iterator does:

• We may have some fields in the iterator that help us keep track of where we are in the iteration.
• We may need to do some setup work in the constructor, like initializing those fields, to prepare for iteration.
• The hasNext() method has one job: to report whether we are done iterating or not. It should not change any state of the iterator.
• The next() method returns the next element and advances the iterator’s state.

Each method of ArraySetIterator, including the constructor, does a constant amount of work:

• ArraySetIterator() initializes the cursor field to 0. $O(1)$.
• hasNext() is a single comparison, cursor < size. $O(1)$.
• next() is a guard check, one array access, and one increment. $O(1)$.

Let’s look at how we would use the iterator to iterate through all the elements of a set:

Iterator<String> it = subscribers.iterator();
while (it.hasNext()) {
  String email = it.next();
  sendNewsletter(email);
}

The iterator() method instantiates a new ArraySetIterator and returns it. Since the constructor is $O(1)$, that is the cost of creating the iterator. Then we call hasNext() and next() once per element in the set, so visiting all $n$ elements costs $O(n)$. That is the best any iteration can do, since each element has to be visited at least once.

Notice that the iterator does not make a copy of the elements in the set. It iterates through the original array and returns the elements one at a time. This is important because it means that the space cost of iterating is constant too (auxiliary space, not counting the input). A common anti-pattern is to first gather all the elements into a separate linear structure like a list, and then iterate through that list. You see this especially with complex non-linear data structures. That takes $O(n)$ auxiliary space and an extra pass over the elements, and it is often unnecessary.