The LinkedSet Iterator

LinkedSet has to supply an iterator() too. The contract is the same as before. The traversal is different, because the elements are stored in a linked list instead of an array. We take the same approach: write the plain loop first, then map its parts onto the iterator.

Traversing a linked list with an ordinary loop looks like this:

Node<T> current = head;
while (current != null) {
  T element = current.value;
  // do something with element
  current = current.next;
}

Here is how each part of the loop maps onto the iterator:

The current variable becomes a field, starting at head, so the iterator remembers where it is between calls.
The condition current != null becomes the logic for hasNext().
The body becomes the logic for next(): read current.value, then move on with current = current.next.

Here is the whole class:

private class LinkedSetIterator implements Iterator<T> {
  private Node<T> current = head;  // node holding the next element to return

  @Override
  public boolean hasNext() {
    return current != null;
  }

  @Override
  public T next() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    T element = current.value;
    current = current.next;
    return element;
  }
}

LinkedSetIterator is an inner class, so it can read the set’s head directly.

The order in next() matters: we save the value before moving current forward, because once current advances we can no longer reach the node we were on. The array iterator could read and advance in one expression, arr[cursor++]. With a linked list, the read and the advance have to be two separate statements.

After the last element, current advances to null, so hasNext() is false and the traversal ends.

Finally, iterator() returns a new LinkedSetIterator:

@Override
public Iterator<T> iterator() {
  return new LinkedSetIterator();
}

The costs are the same as for the array iterator: $O (1)$ per call, $O (n)$ to traverse the whole set, and $O (1)$ auxiliary space, since the iterator holds only the current reference.