Skip to main content

Iterator: Decoupling Traversal from Container

What This Concept Is​

Iterator lets a client walk through the elements of a collection without knowing how the collection is organized. The container exposes some way to produce an iterator; the iterator exposes two or three operations (hasNext, next, optionally reset).

Three roles:

  • Aggregate (collection) -- the data structure. Exposes createIterator() or is itself iterable.
  • Iterator -- carries traversal state (current position) and produces elements one at a time.
  • Client -- uses iterators as interchangeable cursors.

The point is not "add a for loop" -- every language has that. The point is that the client code is the same whether the underlying structure is an array, a linked list, a tree, or a paginated API.

Why It Matters Here​

Most collections you implement or wrap have internal representation you do not want clients to see. Leaking it means clients assume indexing or ordering and break when you change the data structure.

Iterator is also the pattern behind language-level iterables, generators, streams, and LINQ. Understanding it at the object level lets you see those features as instances of the same idea.

Concrete Example​

A tree that supports two traversal orders via distinct iterators.

from typing import Iterator, Callable

class TreeNode:
    def __init__(self, value, children=None):
        self.value = value
        self.children = children or []

def depth_first(root: TreeNode) -> Iterator[int]:
    stack = [root]
    while stack:
        node = stack.pop()
        yield node.value
        stack.extend(reversed(node.children))

def breadth_first(root: TreeNode) -> Iterator[int]:
    from collections import deque
    q = deque([root])
    while q:
        node = q.popleft()
        yield node.value
        q.extend(node.children)

class Tree:
    def __init__(self, root): self.root = root
    def traverse(self, order: Callable = depth_first) -> Iterator[int]:
        return order(self.root)

root = TreeNode(1, [TreeNode(2, [TreeNode(4), TreeNode(5)]), TreeNode(3)])
tree = Tree(root)

print(list(tree.traverse(depth_first)))    # [1, 2, 4, 5, 3]
print(list(tree.traverse(breadth_first)))  # [1, 2, 3, 4, 5]

Two generators, one collection, zero client changes when adding a third traversal order. Python generators are iterators -- the pattern, with less boilerplate.

A classical class-based iterator in Java looks like this:

interface TreeIterator { boolean hasNext(); int next(); }
// depthFirst and breadthFirst are two implementations.

Same roles; more code; same shape.

Common Confusion / Misconception​

  • Exposing the cursor. If the iterator is really just the integer index of an underlying array, clients will reach past it. Keep iterator state inside the iterator.
  • Single-use iterators. Most iterators are exhausted by one walk. Document this. If you need re-iteration, return a fresh iterator, not the consumed one.
  • Concurrent modification. Mutation semantics depend on the collection: snapshot, live, fail-fast and weakly consistent traversal are possible. Fail-fast detection is not synchronization or a correctness guarantee.
  • Forcing a class when a generator exists. Python/JavaScript/Kotlin generators are idiomatic. Use them. The class form is for languages without first-class generators or when the iterator needs rich lifecycle.
  • Iterator as a collection. list(iter) materializes it. For very large or infinite sources, that is the bug that kills the machine.

How To Use It​

  1. Decide the minimum interface your clients need. Usually "advance" and "is there more".
  2. Put traversal state inside the iterator, not the collection.
  3. Keep the collection responsible for producing iterators; do not split that factory across files.
  4. For multiple orders, produce different iterator types (or generator functions). A small explicit order selector is also valid; avoid duplicating cursor invariants unnecessarily.
  5. Document whether the iterator snapshots or reflects live changes.
  6. If traversal is expensive or paginated, make the iterator lazy -- fetch on demand.

Check Yourself​

  1. What does a client gain when traversal is an iterator rather than a loop over list.get(i)?
  2. Why should iterator state live in the iterator, not the collection?
  3. When is a generator preferable to a class iterator?
  4. What should happen if the collection changes while an iterator is walking it?

Mini Drill or Application​

Implement a paginated API iterator:

  1. Given a function fetchPage(n) returning {items, hasNext}, produce an iterator that walks all items across pages.
  2. Fetch lazily: do not fetch page n+1 until the client has consumed all of page n.
  3. Write a consumer that terminates after reading the first 10 items and shows that no later pages were fetched.

Stop when the client loop never mentions page numbers.

Read This Only If Stuck​

Contract and transfer​

The tree sample assumes a finite acyclic structure and a chosen mutation policy. Its generator reads children after yielding a node; mutation between next() calls can therefore alter traversal. It is not a snapshot iterator. A graph with cycles needs a visited policy, and sharing nodes raises a choice between visiting nodes once and visiting every path. DFS memory is not always just tree height in this particular implementation: pushing all siblings can retain a wide frontier.

For pagination, laziness is observable. Constructing an iterator should not fetch under L05. Consuming exactly the current page should not fetch the following page until another next() asks for an item. Empty pages with more=True must not end the stream. Repeated exhaustion must not make new requests.

Transfer: fetch now returns a resource-owning response. State who closes it after early termination, perhaps an explicit context manager. A plain break from a loop is not a universal cross-language resource cleanup contract. P16 and L05 use fake fetch functions so you can test call counts without a live service.