Iterator Pattern

Overview

Intent: Provide a way to access the elements of an aggregate object sequentially without exposing its underlying representation.

The Iterator pattern is a behavioural design pattern that extracts the traversal logic of a collection into a separate object called an iterator. Instead of the collection itself being responsible for how its elements are accessed, the iterator encapsulates the traversal algorithm, position tracking, and termination logic. This separation allows clients to traverse different data structures (arrays, trees, graphs, hash maps) through a uniform interface, regardless of how data is stored internally.

The pattern was formalized by the Gang of Four (GoF) and is one of the most widely adopted patterns in modern programming languages - so much so that most languages provide built-in iterator protocols (Java's Iterator<E>, Python's __iter__/__next__, C#'s IEnumerable<T>).

Also Known As: Cursor

---

Problem It Solves

Collections are among the most common data structures in programming. A collection may be a simple list, a tree, a graph, or a complex composite structure. Regardless of how a collection is structured internally, clients need a way to access every element without understanding the storage mechanism.

Core problems addressed:

1. Decoupling traversal from structure - Without iterators, traversal code is embedded inside the collection or scattered across client code. Adding a new traversal algorithm (reverse, filtered, depth-first) forces modification of the collection class, violating the Open/Closed Principle.

2. Supporting multiple simultaneous traversals - Each iterator instance maintains its own traversal state (cursor position), so multiple independent traversals can occur concurrently on the same collection.

3. Uniform access interface - Clients interact with hasNext() and next() regardless of whether the underlying structure is an array, linked list, B-tree, or network stream.

4. Lazy element production - Iterators can compute or fetch elements on demand, enabling traversal of infinite sequences or large datasets that cannot fit in memory.

---

When to Use / When NOT to Use

---

Key Concepts & Theory

Internal vs External Iterators

• External Iterator (Active): The client explicitly calls next() to advance. The client controls the iteration pace and can pause, resume, or interleave with other logic. Example: Java's Iterator<E>.
• Internal Iterator (Passive): The collection itself drives the traversal, accepting a callback/function to apply to each element. The client surrenders control. Example: Ruby's each { |x| ... }, Java's forEach(Consumer).

Cursor Concept

The iterator maintains a cursor - an internal pointer to the current position within the collection. The cursor advances with each next() call and is used by hasNext() to determine if more elements remain. For array-backed collections, the cursor is typically an integer index; for linked structures, it's a node reference; for trees, it may be a stack of nodes.

Fail-Fast vs Fail-Safe

• Fail-Fast: The iterator detects structural modification of the underlying collection during iteration and immediately throws an exception (e.g., Java's ConcurrentModificationException). Implemented via a modification counter (modCount).
• Fail-Safe: The iterator works on a snapshot or copy of the collection, so modifications don't affect the ongoing traversal. Trades memory for safety (e.g., Java's CopyOnWriteArrayList iterator).

Lazy Evaluation

Iterators need not pre-compute all elements. A lazy iterator produces the next element only when next() is called. This enables:

• Traversal of infinite sequences (Fibonacci, sensor streams)
• Pipeline composition (filter → map → limit) without intermediate collections
• Memory-efficient processing of large datasets

---

ASCII Class Diagram

┌─────────────────────────┐         ┌──────────────────────────────┐
│    «interface»          │         │       «interface»             │
│      Aggregate          │         │         Iterator              │
├─────────────────────────┤         ├──────────────────────────────┤
│                         │         │ + hasNext(): boolean          │
│ + createIterator():     │────────▶│ + next(): Element             │
│     Iterator            │         │ + remove(): void              │
└────────────┬────────────┘         └──────────────┬───────────────┘
             │                                      │
             │ implements                           │ implements
             ▼                                      ▼
┌─────────────────────────┐         ┌──────────────────────────────┐
│   ConcreteAggregate     │         │     ConcreteIterator          │
├─────────────────────────┤         ├──────────────────────────────┤
│ - elements: Element[]   │         │ - aggregate: ConcreteAggregate│
│                         │         │ - cursor: int                 │
│ + createIterator():     │────────▶│                               │
│     Iterator            │         │ + hasNext(): boolean          │
│ + getSize(): int        │         │ + next(): Element             │
│ + getAt(index): Element │         │ + remove(): void              │
└─────────────────────────┘         └──────────────────────────────┘

Relationships:

• Aggregate declares a factory method createIterator() returning an Iterator.
• ConcreteAggregate implements the factory, returning a ConcreteIterator initialized with a reference to itself.
• ConcreteIterator holds a reference back to the aggregate and maintains traversal state via the cursor.

---

Pseudocode Implementation

Book and BookShelf Collection

class Book:
    title: String
    author: String
    year: int

class BookShelf implements Aggregate:
    books: Book[] = []
    
    addBook(book: Book):
        books.append(book)
    
    getSize(): int
        return books.length
    
    getBookAt(index: int): Book
        return books[index]
    
    createIterator(): Iterator<Book>
        return new BookShelfIterator(this)
    
    createReverseIterator(): Iterator<Book>
        return new ReverseBookShelfIterator(this)
    
    createFilteredIterator(predicate: Function<Book, boolean>): Iterator<Book>
        return new FilteredIterator(this.createIterator(), predicate)

Forward Iterator

class BookShelfIterator implements Iterator<Book>:
    shelf: BookShelf
    cursor: int = 0
    
    constructor(shelf: BookShelf):
        this.shelf = shelf
    
    hasNext(): boolean
        return cursor < shelf.getSize()
    
    next(): Book
        if not hasNext():
            throw NoSuchElementException
        book = shelf.getBookAt(cursor)
        cursor = cursor + 1
        return book
    
    remove(): void
        throw UnsupportedOperationException

Reverse Iterator

class ReverseBookShelfIterator implements Iterator<Book>:
    shelf: BookShelf
    cursor: int
    
    constructor(shelf: BookShelf):
        this.shelf = shelf
        this.cursor = shelf.getSize() - 1
    
    hasNext(): boolean
        return cursor >= 0
    
    next(): Book
        if not hasNext():
            throw NoSuchElementException
        book = shelf.getBookAt(cursor)
        cursor = cursor - 1
        return book
    
    remove(): void
        throw UnsupportedOperationException

Filtered Iterator (Decorator over any Iterator)

class FilteredIterator<T> implements Iterator<T>:
    inner: Iterator<T>
    predicate: Function<T, boolean>
    nextItem: T = null
    hasBuffered: boolean = false
    
    constructor(inner: Iterator<T>, predicate: Function<T, boolean>):
        this.inner = inner
        this.predicate = predicate
    
    hasNext(): boolean
        if hasBuffered:
            return true
        while inner.hasNext():
            candidate = inner.next()
            if predicate(candidate):
                nextItem = candidate
                hasBuffered = true
                return true
        return false
    
    next(): T
        if not hasNext():
            throw NoSuchElementException
        hasBuffered = false
        return nextItem

Client Usage

shelf = new BookShelf()
shelf.addBook(Book("Design Patterns", "GoF", 1994))
shelf.addBook(Book("Clean Code", "Martin", 2008))
shelf.addBook(Book("Refactoring", "Fowler", 1999))
shelf.addBook(Book("DDIA", "Kleppmann", 2017))

// Forward traversal
iter = shelf.createIterator()
while iter.hasNext():
    print(iter.next().title)

// Reverse traversal
rev = shelf.createReverseIterator()
while rev.hasNext():
    print(rev.next().title)

// Filtered: only books after year 2000
modern = shelf.createFilteredIterator(book -> book.year > 2000)
while modern.hasNext():
    print(modern.next().title)  // "Clean Code", "DDIA"

---

Internal vs External Iterator

---

Real-World Examples

Java Iterator / Iterable

Java's Collections Framework is built on the Iterator pattern. Every Collection implements Iterable<E>, which provides iterator(). The enhanced for-loop (for (E e : collection)) is syntactic sugar over iterator calls.

Python Generators

Python generators (yield) are lazy iterators. A generator function returns a generator object implementing __iter__ and __next__. Each yield suspends execution, making them memory-efficient for large or infinite sequences.

Database Cursors

SQL database cursors (DECLARE CURSOR, FETCH NEXT) iterate over result sets row by row without loading the entire result into memory. They maintain server-side state tracking the current position in the result set.

File Line Readers

Reading a file line-by-line (BufferedReader.readLine() in Java, for line in file in Python) is an iterator over an I/O stream. Each next() reads the next line from disk, enabling processing of files larger than available RAM.

Tree Traversal Iterators (DFS / BFS)

class DFSIterator implements Iterator<Node>:
    stack: Stack<Node>
    
    constructor(root: Node):
        stack = new Stack()
        stack.push(root)
    
    hasNext(): boolean
        return not stack.isEmpty()
    
    next(): Node
        node = stack.pop()
        for child in node.children.reversed():
            stack.push(child)
        return node

class BFSIterator implements Iterator<Node>:
    queue: Queue<Node>
    
    constructor(root: Node):
        queue = new Queue()
        queue.enqueue(root)
    
    hasNext(): boolean
        return not queue.isEmpty()
    
    next(): Node
        node = queue.dequeue()
        for child in node.children:
            queue.enqueue(child)
        return node

The same tree can be traversed depth-first or breadth-first simply by swapping the iterator - the client code remains identical.

---

Iterator vs For Loop vs Stream

---

Advantages & Disadvantages

---

Constraints & Edge Cases

Concurrent Modification

When a collection is modified while an iterator is active, the iterator's assumptions about size and element positions become invalid. Solutions:

• Fail-fast: Track a modCount; throw on mismatch (Java's ArrayList).
• Snapshot: Copy the collection at iterator creation time (memory cost).
• Concurrent collections: Use lock-free structures (e.g., ConcurrentLinkedQueue).

Iterator Invalidation

In languages like C++, inserting or removing elements can invalidate existing iterators (dangling pointers). The STL documents which operations invalidate which iterators for each container type. Always check invalidation rules before mixing mutation with iteration.

Infinite Iterators

Iterators over infinite sequences (random number generators, event streams, mathematical series) never return false from hasNext(). Clients must impose external termination conditions (limit, takeWhile). Forgetting to do so causes infinite loops.

Stateful vs Stateless

• Stateful iterators maintain mutable cursor state - they are single-use and not thread-safe by default.
• Stateless iteration (functional streams) recreates traversal state on each terminal operation, making them safer but potentially less efficient for complex traversals.

Null and Empty Collections

Iterators over empty collections should return false on the first hasNext() call. The Null Iterator pattern (an iterator that is always exhausted) avoids null checks in client code.

---

Interview Follow-ups

Q1: How does Java's ConcurrentModificationException work internally?

A: Java collections maintain an integer modCount that increments on every structural modification (add, remove, clear). When an iterator is created, it snapshots expectedModCount = modCount. On each hasNext() or next() call, the iterator checks modCount != expectedModCount. If they differ, it throws ConcurrentModificationException. This is best-effort - not guaranteed under concurrent access without synchronization.

Q2: How would you implement an iterator over a binary tree that uses O(h) space instead of O(n)?

A: Use a stack-based approach for in-order traversal. Push all left children of the root onto the stack. On next(), pop the top node, push all left children of its right child. The stack never holds more than h nodes (tree height), giving O(h) space. This is the approach used by database index scans over B-trees.

Q3: What is the difference between Iterator and ListIterator in Java?

A: ListIterator extends Iterator with bidirectional traversal (hasPrevious(), previous()), index-based positioning (nextIndex(), previousIndex()), and in-place modification (set(), add()). It's only available for List implementations, not general Collection types, because it requires sequential indexing semantics.

Hint-Only Questions

H1: How would you design a thread-safe iterator for a concurrent collection without copying the entire collection?

• Hint: Think about segment-level locking, weakly consistent semantics, and how ConcurrentHashMap's iterators reflect state "at some point" during traversal without throwing exceptions.

H2: How can you compose multiple iterators to implement SQL-like operations (JOIN, GROUP BY) in a streaming fashion?

• Hint: Consider merge iterators (sorted inputs), grouping iterators that buffer elements with the same key, and how database query executors use the Volcano/iterator model where each operator is an iterator calling next() on its child operators.

---

Counter Questions to Ask Interviewer

1. "Is the collection mutable during iteration, or can we assume it's read-only?" - Determines whether you need fail-fast/fail-safe mechanisms or can use a simpler stateless design.

2. "What's the expected size of the collection - bounded or potentially infinite?" - Influences whether lazy evaluation is necessary and whether O(n) space for snapshots is acceptable.

3. "Do we need to support multiple concurrent iterators over the same collection?" - Affects whether iterator state must be fully independent and whether thread-safety is a concern.

4. "Is random access required, or is sequential-only traversal sufficient?" - Determines if a simple forward iterator suffices or if a ListIterator-style bidirectional interface is needed.

5. "Are there ordering guarantees required (insertion order, sorted order, priority)?" - Shapes the iterator's traversal algorithm and whether the underlying structure needs to maintain order.

---

References & Whitepapers

1. Gamma, E., Helm, R., Johnson, R., Vlissides, J. - Design Patterns: Elements of Reusable Object-Oriented Software (1994), Chapter 5: Behavioral Patterns - Iterator. The canonical definition of the pattern with Smalltalk and C++ examples.

2. Bloch, J. - Effective Java (3rd Edition, 2018), Item 58: "Prefer for-each loops to traditional for loops." Discusses how Java's iterator protocol enables the enhanced for-loop.

3. Java Collections Framework Design FAQ - Sun/Oracle documentation on the design decisions behind Iterator, ListIterator, fail-fast semantics, and why Enumeration was superseded.

4. Graefe, G. - Volcano - An Extensible and Parallel Query Evaluation System (1994). Describes the iterator model for database query execution where each operator implements open(), next(), close().

5. Python PEP 234 - Iterators (2001). Defines Python's iterator protocol (__iter__, __next__) and the rationale for separating iteration from container types.

6. Lea, D. - Concurrent Programming in Java (2nd Edition, 1999). Discusses iterator safety in concurrent environments and the design of java.util.concurrent iterators.

---

Related Topics

• Observer Pattern - Both decouple producers from consumers; Observer pushes, Iterator pulls
• Composite Pattern - Iterators are often used to traverse composite structures
• Strategy Pattern - Different iterator implementations are strategies for traversal
• Factory Method - createIterator() is a factory method
• Visitor Pattern - Alternative for traversing complex structures when operations vary
• Generator Pattern (Python) - Language-level support for lazy iterators