Iterator Pattern — Sequential Access to Collections

What You'll Learn

You will learn how the Iterator pattern decouples collection traversal from the collection itself, enabling uniform iteration over arrays, trees, hash maps, and custom data structures. You will implement both custom iterators and leverage built-in language iteration protocols.

Why It Matters

Every application works with collections, but each collection has a different internal structure — array, Linked List, tree, or graph. Exposing these internals to clients creates tight coupling. Iterator provides a standard traversal interface that works regardless of the underlying data structure. Consider a Binary Search Tree and a hash map — one stores elements in a branching structure, the other uses buckets. Without the Iterator pattern, code that processes all elements would need to understand both internal representations. Iterator lets you write for item in collection: and the collection handles its own traversal.

Real-World Use

Streaming services paginate through millions of search results without loading them all into memory. DodaTech's data export tool uses iterators to read records from databases, APIs, or CSV files through the same cursor interface. The exporter never needs to know whether it's reading from a PostgreSQL result set, a JSON API response, or a local file — it simply calls next() on an iterator until the data is exhausted.

The Pattern

Iterator declares traversal methods. Aggregate declares a Factory Method for iterators. ConcreteIterator tracks the current position and retrieves elements.

from collections.abc import Iterator, Iterable

class TreeNode:
    def __init__(self, value: str):
        self.value = value
        self.left = None
        self.right = None

class DepthFirstIterator(Iterator):
    def __init__(self, root: TreeNode):
        self._stack = [root]

    def __next__(self) -> str:
        while self._stack:
            node = self._stack.pop()
            if node.right:
                self._stack.append(node.right)
            if node.left:
                self._stack.append(node.left)
            return node.value
        raise StopIteration

class Tree(Iterable):
    def __init__(self, root: TreeNode):
        self._root = root

    def __iter__(self) -> Iterator:
        return DepthFirstIterator(self._root)

class Playlist:
    def __init__(self, songs: list):
        self._songs = songs

    def __iter__(self):
        return iter(self._songs)

root = TreeNode("a")
root.left = TreeNode("b")
root.right = TreeNode("c")
root.left.left = TreeNode("d")
root.left.right = TreeNode("e")

tree = Tree(root)
print("Tree DFS:", " ".join(tree))

playlist = Playlist(["Song A", "Song B", "Song C"])
print("Playlist:", " ".join(playlist))

Tree DFS: a b d e c
Playlist: Song A Song B Song C

Structure

classDiagram
    class Iterator {
        <>
        +next(): Element
        +hasNext(): bool
    }
    class ConcreteIterator {
        +next(): Element
        +hasNext(): bool
    }
    class Aggregate {
        <>
        +createIterator(): Iterator
    }
    class ConcreteAggregate {
        +createIterator(): Iterator
    }
    ConcreteIterator ..|> Iterator
    ConcreteAggregate ..|> Aggregate
    ConcreteIterator --> ConcreteAggregate : traverses

Real-World Usage

• Python for x in collection — the language uses __iter__ and __next__ to iterate over any iterable.
• Java java.util.<a href="/design-patterns/iterator/">Iterator</a> — every collection in the standard library provides an iterator.
• C# foreach / IEnumerable — LINQ queries are built on top of the iterator pattern.
• JavaScript Symbol.<a href="/design-patterns/iterator/">iterator</a> — custom iterables power for...of loops and spread operators.

Related Patterns

• Composite is often traversed with an Iterator.
• Factory Method creates the iterator instances.
• Memento can capture the iterator's state for checkpointing.
• Visitor performs operations on elements during iteration.

Pros and Cons

The code demonstrates two different approaches. The DepthFirstIterator is a custom iterator that implements pre-order traversal using an explicit stack. The Playlist class, on the other hand, simply delegates to the built-in iter() function on its underlying list. Both produce objects that work with Python's for item in collection: syntax because they implement the __iter__ protocol.

Practice Questions

1. Implement an iterator that traverses a Binary Tree in breadth-first order instead of depth-first.
2. How would you implement a thread-safe iterator that supports concurrent modification — where elements can be added or removed during iteration?
3. What is the difference between an internal iterator (function callback) and an external iterator (next/hasNext)? When would you choose each?
4. Implement an iterator that yields only elements matching a predicate, filtering a source iterator lazily.

Challenge

Write an iterator that can traverse both depth-first and breadth-first depending on a parameter passed to the constructor. The Tree aggregate should accept the strategy and return the correct iterator.

Real-World Task

Inspect your application's data access layer. Identify places where collection traversal logic is mixed with business logic. Extract those traversals into dedicated iterators and use DodaTech's collection visualiser to verify correctness.