3.4 Iterator

The Iterator pattern provides a way to access the elements of an aggregate sequentially without exposing its internal representation. Whether the backing store is an array, linked list, hash table, or tree, the client traverses with the same hasNext() / next().

This is the most "invisible" pattern in everyday programming — the for (x : collection) you write daily is built on it. The lab below lets you click next() to advance a cursor and watch the traversal state live in the iterator.

Separate traversal from the collection

interface Iterator<T> {
    boolean hasNext();
    T next();
}

interface Iterable<T> {
    Iterator<T> iterator();   // the collection produces iterators
}

Key point: traversal state lives in the iterator, not the collection. That brings two benefits:

• One collection can have multiple independent cursors at once, without interference.

• One collection can offer multiple iterators (preorder, inorder, filtering…), decoupling traversal strategy from the data structure.

The lab below uses one tree and switches preorder/inorder/postorder/BFS, watching the visit order change — the data is unchanged, only the iterator differs.

Language-built-in iterators

Most modern languages bake iterators into the language:

• Java's Iterator / Iterable and enhanced for;

• Python's __iter__ / __next__ and yield generators;

• C++'s begin() / end(), C#'s IEnumerable.

So you rarely hand-write an iterator from scratch — but understanding it helps you correctly implement traversal for custom data structures and see the unified abstraction behind lazy sequences, generators, and streams.