System Design (LLD)Iterator Pattern

Iterator Pattern: Uniform Collection Traversal

LevelIntermediate

Duration60 mins

TopicIterator Pattern

2 / 4

Solution: The Iterator Interface

Building the Uniform Traversal Mechanism

In the previous page, we identified a fundamental problem: code that traverses collections becomes tightly coupled to their internal structures. Change the structure, and every client breaks.

The Iterator Pattern provides an elegant solution: extract traversal responsibility into a dedicated object. This iterator object provides a uniform interface for accessing elements sequentially, hiding all details of how the collection is actually organized.

This page presents the complete Iterator Pattern architecture—the interfaces, the implementations, and the relationships that make uniform collection traversal possible.

What You Will Learn

By the end of this page, you will understand the complete structure of the Iterator Pattern: the Iterator interface, Concrete Iterators, the Aggregate interface, and Concrete Aggregates. You'll implement iterators for multiple collection types and see how the pattern enables polymorphic collection traversal.

Pattern Structure: The Four Participants

The Iterator Pattern involves four key participants, each with a distinct role in enabling uniform traversal:

Iterator Pattern Participants
Participant	Also Known As	Responsibility
Iterator	Cursor, Enumerator	Defines the interface for accessing and traversing elements
Concrete Iterator	ArrayIterator, LinkedListIterator	Implements Iterator interface, tracks current position in traversal
Aggregate	Collection, Container, Iterable	Defines interface for creating an Iterator object
Concrete Aggregate	ArrayList, LinkedList, CustomCollection	Implements Aggregate interface, returns appropriate Concrete Iterator

The relationship flow:

Client asks Aggregate for an Iterator
Concrete Aggregate creates and returns Concrete Iterator
Concrete Iterator has access to the aggregate's internals
Client uses Iterator interface to traverse—never touching aggregate internals

pattern_relationships.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# Iterator Pattern: Relationship Diagram
 
"""
┌─────────────────┐         ┌─────────────────┐
│    Iterator     │         │    Aggregate    │
│   (interface)   │         │   (interface)   │
├─────────────────┤         ├─────────────────┤
│ + has_next()    │         │ + create_       │
│ + next()        │         │   iterator()    │
│ + current()     │         │                 │
└────────▲────────┘         └────────▲────────┘
         │                           │
         │                           │
         │ implements                │ implements
         │                           │
┌────────┴────────┐         ┌────────┴────────┐
│ ConcreteIterator│◄────────│ConcreteAggregate│
│                 │ creates  │                 │
├─────────────────┤         ├─────────────────┤
│ - aggregate     │         │ - elements[]    │
│ - currentIndex  │         │ + add(element)  │
│ + has_next()    │         │ + remove(elem)  │
│ + next()        │         │ + create_       │
│ + current()     │         │   iterator()    │
└─────────────────┘         └─────────────────┘
 
Client code depends only on Iterator and Aggregate interfaces.
Concrete implementations are hidden from clients.
"""

The Key Insight

The Concrete Iterator is a 'friend' of the Concrete Aggregate—it has access to the aggregate's internals. But clients never interact with either concrete class directly. They work exclusively through the abstract interfaces, achieving complete decoupling.

The Iterator Interface: Minimal but Complete

The Iterator interface is deliberately minimal. It defines only the operations necessary for sequential access, nothing more. This simplicity is a feature—it makes the interface easy to implement and easy to use.

iterator_interface.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
from abc import ABC, abstractmethod
from typing import TypeVar, Generic, Optional
 
T = TypeVar('T')
 
class Iterator(ABC, Generic[T]):
    """
    Abstract Iterator Interface
    
    Defines the contract for traversing a collection.
    All concrete iterators must implement these methods.
    """
    
    @abstractmethod
    def has_next(self) -> bool:
        """
        Checks if there are more elements to traverse.
        
        Returns:
            True if next() will return an element,
            False if traversal is complete.
        
        Contract:
            - Must be idempotent (calling multiple times without next() 
              returns same result)
            - Must never modify the iterator's state
            - Should be O(1) time complexity
        """
        pass
    
    @abstractmethod
    def next(self) -> T:
        """
        Returns the current element and advances to the next position.
        
        Returns:
            The current element in the traversal
        
        Raises:
            StopIteration: If no more elements exist
        
        Contract:
            - Must advance position after returning element
            - Calling after has_next() returns False raises exception
            - Should be O(1) amortized time complexity
        """
        pass
    
    @abstractmethod
    def reset(self) -> None:
        """
        Resets the iterator to the beginning of the collection.
        
        After calling reset(), has_next() and next() behave as if
        the iterator were newly created.
        
        Contract:
            - Must restore iterator to initial state
            - Subsequent next() returns first element
        """
        pass
    
    def current(self) -> Optional[T]:
        """
        Returns the current element without advancing.
        
        Optional method - not all iterators support this.
        Default implementation raises NotImplementedError.
        
        Returns:
            Current element, or None if not positioned on an element
        """
        raise NotImplementedError("current() not supported by this iterator")

Core Iterator Operations

•has_next() — The sentinel that prevents overrun. Always check before calling next(). Returns boolean indicating more elements exist.
•next() — The workhorse. Returns current element and advances position. The 'move forward' action is atomic with retrieval.
•reset() — Restart capability. Returns iterator to beginning, enabling multiple traversals with same iterator instance.
•current() (optional) — Peek without advance. Useful when you need to inspect before deciding to consume.

Interface Variations

Different languages use slightly different iterator interfaces. Python uses iter() and next() with StopIteration. Java uses hasNext() and next(). C++ uses operator++, operator*, and comparison operators. The concepts are identical—only syntax differs.

The Aggregate Interface: Iterator Factory

The Aggregate interface is even simpler than the Iterator interface. Its sole responsibility is to create iterators. This single method is the hinge that connects collection implementations to their traversal mechanisms.

aggregate_interface.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
from abc import ABC, abstractmethod
from typing import TypeVar, Generic
 
T = TypeVar('T')
 
class Aggregate(ABC, Generic[T]):
    """
    Abstract Aggregate Interface
    
    Defines the contract for collections that can be iterated.
    Every collection that supports iteration implements this interface.
    """
    
    @abstractmethod
    def create_iterator(self) -> 'Iterator[T]':
        """
        Factory method for creating iterators.
        
        Returns:
            A new Iterator instance positioned at the beginning
            of this collection.
        
        Contract:
            - Must return a NEW iterator each call (independent traversals)
            - Iterator must be positioned before first element
            - Iterator must have access to collection's elements
        
        Why factory method?
            - Encapsulates iterator creation logic
            - Collection knows which iterator type is appropriate
            - Enables different iterator types (forward, reverse, filtered)
        """
        pass
    
    # Optional: Support for multiple iterator types
    def create_reverse_iterator(self) -> 'Iterator[T]':
        """Creates an iterator that traverses in reverse order."""
        raise NotImplementedError("Reverse iteration not supported")
    
    def create_filtered_iterator(
        self, 
        predicate: Callable[[T], bool]
    ) -> 'Iterator[T]':
        """Creates an iterator that yields only elements matching predicate."""
        raise NotImplementedError("Filtered iteration not supported")

Why is this a factory method?

The create_iterator() method is an example of the Factory Method pattern embedded within the Iterator pattern. The aggregate knows:

Its internal structure
Which iterator type can traverse that structure
How to initialize the iterator with access to its elements

Clients don't need any of this knowledge. They just call create_iterator() and receive something that satisfies the Iterator interface.

Multiple Iterator Types

A single aggregate can provide multiple iterator types. create_iterator() might return a forward iterator, while create_reverse_iterator() returns one that goes backward. This is how Java's List provides both iterator() and listIterator() methods.

Implementing an Array Iterator

Let's implement a complete Iterator for an array-based collection. This is the simplest concrete iterator—it tracks position with an integer index and advances by incrementing.

array_iterator.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
from typing import TypeVar, Generic, List, Optional
 
T = TypeVar('T')
 
class ArrayIterator(Iterator[T]):
    """
    Concrete Iterator for array-based collections.
    
    Tracks position using an integer index.
    Traverses from index 0 to len(array) - 1.
    """
    
    def __init__(self, items: List[T]):
        """
        Initialize iterator with reference to the array.
        
        Args:
            items: The array to iterate over
        
        Note: We store a reference, not a copy. This means:
            - Memory efficient (no duplication)
            - Iterator sees modifications to original array
            - Modifying array during iteration has undefined behavior
        """
        self._items = items
        self._current_index = 0
    
    def has_next(self) -> bool:
        """Check if more elements exist."""
        return self._current_index < len(self._items)
    
    def next(self) -> T:
        """Return current element and advance."""
        if not self.has_next():
            raise StopIteration("No more elements")
        
        element = self._items[self._current_index]
        self._current_index += 1
        return element
    
    def current(self) -> Optional[T]:
        """Return current element without advancing."""
        if self._current_index >= len(self._items):
            return None
        return self._items[self._current_index]
    
    def reset(self) -> None:
        """Reset to beginning of array."""
        self._current_index = 0
 
 
class ArrayList(Aggregate[T]):
    """
    Concrete Aggregate: An array-based list implementation.
    """
    
    def __init__(self):
        self._items: List[T] = []
    
    def add(self, item: T) -> None:
        """Add an item to the list."""
        self._items.append(item)
    
    def remove(self, item: T) -> bool:
        """Remove an item from the list. Returns True if removed."""
        try:
            self._items.remove(item)
            return True
        except ValueError:
            return False
    
    def __len__(self) -> int:
        """Return the number of items."""
        return len(self._items)
    
    def create_iterator(self) -> Iterator[T]:
        """
        Factory method: Create an iterator for this list.
        
        Returns a new ArrayIterator positioned at the start.
        Each call returns an INDEPENDENT iterator.
        """
        return ArrayIterator(self._items)
 
 
# Usage demonstration
def demo_array_iterator():
    # Create and populate the collection
    users = ArrayList[str]()
    users.add("Alice")
    users.add("Bob")
    users.add("Charlie")
    
    # Get an iterator - we don't know it's an ArrayIterator
    iterator: Iterator[str] = users.create_iterator()
    
    # Traverse using only the Iterator interface
    print("Users in the system:")
    while iterator.has_next():
        user = iterator.next()
        print(f"  - {user}")
    
    # Reset and traverse again
    iterator.reset()
    print("
Traversing again after reset:")
    while iterator.has_next():
        print(f"  - {iterator.next()}")

Reference vs Copy

The iterator stores a reference to the array, not a copy. This is memory-efficient but means modifying the array during iteration causes undefined behavior. Some iterators make a 'snapshot' copy for safe concurrent modification, trading memory for safety.

Implementing a Linked List Iterator

Now let's implement an iterator for a linked list. The internal structure is completely different—nodes with next pointers instead of contiguous memory—but the iterator interface remains identical.

linked_list_iterator.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
from typing import TypeVar, Generic, Optional
from dataclasses import dataclass
 
T = TypeVar('T')
 
@dataclass
class Node(Generic[T]):
    """A node in the linked list."""
    data: T
    next: Optional['Node[T]'] = None
 
 
class LinkedListIterator(Iterator[T]):
    """
    Concrete Iterator for linked list collections.
    
    Tracks position using a pointer to the current node.
    Traverses by following next pointers.
    """
    
    def __init__(self, head: Optional[Node[T]]):
        """
        Initialize with pointer to the head node.
        
        Args:
            head: The first node of the linked list (or None if empty)
        """
        self._head = head  # Store head for reset capability
        self._current = head  # Current position in traversal
    
    def has_next(self) -> bool:
        """Check if more elements exist."""
        return self._current is not None
    
    def next(self) -> T:
        """Return current element and advance to next node."""
        if not self.has_next():
            raise StopIteration("No more elements")
        
        data = self._current.data
        self._current = self._current.next  # Follow the pointer
        return data
    
    def current(self) -> Optional[T]:
        """Return current element without advancing."""
        if self._current is None:
            return None
        return self._current.data
    
    def reset(self) -> None:
        """Reset to the head of the list."""
        self._current = self._head
 
 
class LinkedList(Aggregate[T]):
    """
    Concrete Aggregate: A singly-linked list implementation.
    """
    
    def __init__(self):
        self._head: Optional[Node[T]] = None
        self._tail: Optional[Node[T]] = None
        self._size = 0
    
    def add(self, item: T) -> None:
        """Add an item to the end of the list."""
        new_node = Node(data=item)
        
        if self._tail is None:
            self._head = new_node
            self._tail = new_node
        else:
            self._tail.next = new_node
            self._tail = new_node
        
        self._size += 1
    
    def add_front(self, item: T) -> None:
        """Add an item to the front of the list (O(1))."""
        new_node = Node(data=item, next=self._head)
        self._head = new_node
        
        if self._tail is None:
            self._tail = new_node
        
        self._size += 1
    
    def __len__(self) -> int:
        """Return the number of items."""
        return self._size
    
    def create_iterator(self) -> Iterator[T]:
        """
        Factory method: Create an iterator for this linked list.
        
        Returns a LinkedListIterator, but caller only knows it's an Iterator.
        """
        return LinkedListIterator(self._head)
 
 
# The power: Same client code works for both!
def process_collection(collection: Aggregate[str]) -> None:
    """
    Generic function that works with ANY Aggregate.
    
    This code has NO IDEA whether it's processing:
    - An ArrayList
    - A LinkedList
    - A Tree
    - A Graph
    - A Database cursor
    - Any future collection type
    
    It only knows the collection provides an Iterator.
    """
    iterator = collection.create_iterator()
    
    count = 0
    while iterator.has_next():
        item = iterator.next()
        print(f"Processing: {item}")
        count += 1
    
    print(f"Total processed: {count}")
 
 
# Demonstration of polymorphism
def demo_polymorphic_iteration():
    # Create an ArrayList
    array_list = ArrayList[str]()
    array_list.add("Apple")
    array_list.add("Banana")
    array_list.add("Cherry")
    
    # Create a LinkedList
    linked_list = LinkedList[str]()
    linked_list.add("Dog")
    linked_list.add("Elephant")
    linked_list.add("Fox")
    
    # Same function processes both!
    print("Processing ArrayList:")
    process_collection(array_list)
    
    print("
Processing LinkedList:")
    process_collection(linked_list)

The crucial observation: The process_collection() function works identically for both ArrayList and LinkedList. It doesn't contain any if isinstance() checks. It doesn't know about array indices or node pointers. It simply uses the Iterator interface.

This is the power of the Iterator Pattern in action.

True Polymorphism Achieved

Any collection that implements Aggregate can be processed by the same client code. Add a new collection type later (tree, graph, database cursor), and existing client code works without modification. This is the Open/Closed Principle: open for extension, closed for modification.

Implementing a Tree Iterator

Tree structures present an interesting challenge: there are multiple valid traversal orders (preorder, inorder, postorder, level-order). The Iterator Pattern handles this elegantly—we can provide different iterator implementations for different traversal orders, all conforming to the same interface.

tree_iterators.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
from typing import TypeVar, Generic, Optional, List
from dataclasses import dataclass
from collections import deque
 
T = TypeVar('T')
 
@dataclass
class TreeNode(Generic[T]):
    """A node in a binary tree."""
    data: T
    left: Optional['TreeNode[T]'] = None
    right: Optional['TreeNode[T]'] = None
 
 
class InOrderTreeIterator(Iterator[T]):
    """
    Iterator that traverses a binary tree in-order (left, root, right).
    
    Uses a stack to simulate the recursive traversal iteratively.
    This yields elements in sorted order for a BST.
    """
    
    def __init__(self, root: Optional[TreeNode[T]]):
        self._root = root
        self._stack: List[TreeNode[T]] = []
        self._push_left_chain(root)
    
    def _push_left_chain(self, node: Optional[TreeNode[T]]) -> None:
        """Push node and all its left descendants onto the stack."""
        while node is not None:
            self._stack.append(node)
            node = node.left
    
    def has_next(self) -> bool:
        """More elements exist if stack is not empty."""
        return len(self._stack) > 0
    
    def next(self) -> T:
        """Return next in-order element."""
        if not self.has_next():
            raise StopIteration("No more elements")
        
        # Pop the top node (next in-order element)
        node = self._stack.pop()
        
        # If it has a right child, push that child's left chain
        if node.right is not None:
            self._push_left_chain(node.right)
        
        return node.data
    
    def reset(self) -> None:
        """Reset to the beginning of in-order traversal."""
        self._stack.clear()
        self._push_left_chain(self._root)
 
 
class PreOrderTreeIterator(Iterator[T]):
    """
    Iterator that traverses a binary tree pre-order (root, left, right).
    
    Pre-order is useful for copying trees or prefix expressions.
    """
    
    def __init__(self, root: Optional[TreeNode[T]]):
        self._root = root
        self._stack: List[TreeNode[T]] = []
        if root is not None:
            self._stack.append(root)
    
    def has_next(self) -> bool:
        return len(self._stack) > 0
    
    def next(self) -> T:
        if not self.has_next():
            raise StopIteration("No more elements")
        
        node = self._stack.pop()
        
        # Push right first (so left is processed first - LIFO)
        if node.right is not None:
            self._stack.append(node.right)
        if node.left is not None:
            self._stack.append(node.left)
        
        return node.data
    
    def reset(self) -> None:
        self._stack.clear()
        if self._root is not None:
            self._stack.append(self._root)
 
 
class LevelOrderTreeIterator(Iterator[T]):
    """
    Iterator that traverses a binary tree level-by-level (BFS).
    
    Level-order is useful for printing trees visually or finding shortest paths.
    """
    
    def __init__(self, root: Optional[TreeNode[T]]):
        self._root = root
        self._queue: deque[TreeNode[T]] = deque()
        if root is not None:
            self._queue.append(root)
    
    def has_next(self) -> bool:
        return len(self._queue) > 0
    
    def next(self) -> T:
        if not self.has_next():
            raise StopIteration("No more elements")
        
        node = self._queue.popleft()
        
        # Enqueue children (left first, then right)
        if node.left is not None:
            self._queue.append(node.left)
        if node.right is not None:
            self._queue.append(node.right)
        
        return node.data
    
    def reset(self) -> None:
        self._queue.clear()
        if self._root is not None:
            self._queue.append(self._root)
 
 
class BinaryTree(Aggregate[T]):
    """
    Concrete Aggregate: A binary tree with multiple iterator types.
    """
    
    def __init__(self):
        self._root: Optional[TreeNode[T]] = None
    
    def set_root(self, root: TreeNode[T]) -> None:
        """Set the root node of the tree."""
        self._root = root
    
    def create_iterator(self) -> Iterator[T]:
        """Default iterator: in-order traversal."""
        return InOrderTreeIterator(self._root)
    
    def create_preorder_iterator(self) -> Iterator[T]:
        """Create a pre-order traversal iterator."""
        return PreOrderTreeIterator(self._root)
    
    def create_levelorder_iterator(self) -> Iterator[T]:
        """Create a level-order (BFS) traversal iterator."""
        return LevelOrderTreeIterator(self._root)
 
 
# Demonstration
def demo_tree_iterators():
    """
    Build a tree and traverse it multiple ways.
    
            4
           / \
          2   6
         / \ / \
        1  3 5  7
    """
    # Build the tree
    tree = BinaryTree[int]()
    
    node1 = TreeNode(1)
    node3 = TreeNode(3)
    node5 = TreeNode(5)
    node7 = TreeNode(7)
    node2 = TreeNode(2, left=node1, right=node3)
    node6 = TreeNode(6, left=node5, right=node7)
    root = TreeNode(4, left=node2, right=node6)
    
    tree.set_root(root)
    
    # Same tree, different traversal orders
    print("In-Order (sorted): ", end="")
    for_each(tree.create_iterator(), lambda x: print(x, end=" "))
    print()  # Output: 1 2 3 4 5 6 7
    
    print("Pre-Order (root first): ", end="")
    for_each(tree.create_preorder_iterator(), lambda x: print(x, end=" "))
    print()  # Output: 4 2 1 3 6 5 7
    
    print("Level-Order (BFS): ", end="")
    for_each(tree.create_levelorder_iterator(), lambda x: print(x, end=" "))
    print()  # Output: 4 2 6 1 3 5 7
 
 
def for_each(iterator: Iterator, action: Callable) -> None:
    """Apply action to each element from the iterator."""
    while iterator.has_next():
        action(iterator.next())

Multiple Iterators, One Collection

The same tree supports multiple traversal strategies through different iterator implementations. Client code chooses the traversal order by selecting the appropriate factory method. The tree itself doesn't change—only the iteration strategy changes.

Language Integration: Python's Iterator Protocol

The Iterator Pattern is so fundamental that Python builds it directly into the language. Understanding Python's iterator protocol helps you leverage the pattern with native syntax.

python_protocol.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
from typing import TypeVar, Generic, Optional, List
 
T = TypeVar('T')
 
class PythonicArrayList(Generic[T]):
    """
    A collection that implements Python's iterator protocol.
    
    Python's protocol uses:
    - __iter__(): Returns an iterator (like create_iterator())
    - __next__(): Returns next element (like next())
    
    When these are implemented, the collection works with:
    - for loops
    - list comprehensions
    - zip(), map(), filter()
    - any() and all()
    - Unpacking: a, b, c = collection
    """
    
    def __init__(self):
        self._items: List[T] = []
    
    def add(self, item: T) -> None:
        self._items.append(item)
    
    def __iter__(self):
        """
        Return an iterator for this collection.
        
        Python calls this when you write:
            for item in collection:
                ...
        """
        return PythonicArrayListIterator(self._items)
    
    def __len__(self) -> int:
        return len(self._items)
 
 
class PythonicArrayListIterator:
    """Python-style iterator with __iter__ and __next__."""
    
    def __init__(self, items: List[T]):
        self._items = items
        self._index = 0
    
    def __iter__(self):
        """Iterators are also iterable (return self)."""
        return self
    
    def __next__(self) -> T:
        """
        Return next element or raise StopIteration.
        
        Python's for loop catches StopIteration automatically
        and exits the loop cleanly.
        """
        if self._index >= len(self._items):
            raise StopIteration
        
        item = self._items[self._index]
        self._index += 1
        return item
 
 
# Now the collection integrates with Python's syntax!
def demo_pythonic_iteration():
    collection = PythonicArrayList[str]()
    collection.add("Python")
    collection.add("Java")
    collection.add("TypeScript")
    
    # Native for loop - Python calls __iter__ and __next__
    print("Using for loop:")
    for language in collection:
        print(f"  {language}")
    
    # List comprehension
    upper_languages = [lang.upper() for lang in collection]
    print(f"Uppercase: {upper_languages}")
    
    # Built-in functions
    print(f"Any starts with 'P': {any(lang.startswith('P') for lang in collection)}")
    print(f"All have length > 2: {all(len(lang) > 2 for lang in collection)}")
    
    # Unpacking
    first, *rest = collection
    print(f"First: {first}, Rest: {rest}")
    
    # Creating list from iterator
    as_list = list(collection)
    print(f"As list: {as_list}")

Iterator Protocol Across Languages
Language	Create Iterator	Check Has Next	Get Next	Loop Syntax
Python	iter()	(implicit)	next()	for x in collection:
Java	iterator()	hasNext()	next()	for (T x : collection)
JavaScript	Symbol.iterator	(implicit)	next().done	for (const x of collection)
C++	begin()	it != end()	*it++	for (auto x : collection)
C#	GetEnumerator()	MoveNext()	Current	foreach (var x in collection)

The Pattern is Universal

Every major language implements the Iterator Pattern in its core libraries. The syntax differs, but the concept is identical: a uniform interface for sequential element access that hides collection internals.

Modern Approach: Generator-Based Iterators

Modern languages provide generators (Python's yield, JavaScript's function*) that make implementing iterators dramatically simpler. Instead of manually tracking state with instance variables, you write sequential code that suspends and resumes.

generator_iterators.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
from typing import Generator, TypeVar, List, Optional
from dataclasses import dataclass
 
T = TypeVar('T')
 
@dataclass
class TreeNode:
    value: int
    left: Optional['TreeNode'] = None
    right: Optional['TreeNode'] = None
 
 
class BinaryTreeWithGenerators:
    """
    Tree that uses generators for iteration.
    
    Generators dramatically simplify iterator implementation:
    - No manual state management
    - No stack/queue data structures
    - Code reads like the recursive algorithm
    """
    
    def __init__(self):
        self.root: Optional[TreeNode] = None
    
    def inorder(self) -> Generator[int, None, None]:
        """
        In-order traversal using a generator.
        
        Compare this to InOrderTreeIterator class:
        - No __init__ with state
        - No stack management
        - No has_next/next methods
        - Just yield when we have a value
        """
        def traverse(node: Optional[TreeNode]) -> Generator[int, None, None]:
            if node is not None:
                yield from traverse(node.left)   # All left values
                yield node.value                  # This value
                yield from traverse(node.right)  # All right values
        
        return traverse(self.root)
    
    def preorder(self) -> Generator[int, None, None]:
        """Pre-order traversal: root, left, right."""
        def traverse(node: Optional[TreeNode]) -> Generator[int, None, None]:
            if node is not None:
                yield node.value
                yield from traverse(node.left)
                yield from traverse(node.right)
        
        return traverse(self.root)
    
    def postorder(self) -> Generator[int, None, None]:
        """Post-order traversal: left, right, root."""
        def traverse(node: Optional[TreeNode]) -> Generator[int, None, None]:
            if node is not None:
                yield from traverse(node.left)
                yield from traverse(node.right)
                yield node.value
        
        return traverse(self.root)
    
    def levelorder(self) -> Generator[int, None, None]:
        """Level-order traversal (BFS)."""
        if self.root is None:
            return
        
        queue = [self.root]
        while queue:
            node = queue.pop(0)
            yield node.value
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    
    def __iter__(self) -> Generator[int, None, None]:
        """Default iteration is in-order."""
        return self.inorder()
 
 
# Even more powerful: generator expressions and comprehensions
def demo_generators():
    tree = BinaryTreeWithGenerators()
    # Set up tree...
    
    # Generator expressions are lazy iterators
    doubled = (x * 2 for x in tree.inorder())
    filtered = (x for x in tree if x > 5)
    
    # Chain iterators together
    from itertools import chain, islice
    
    # First 5 elements from chained traversals
    combined = chain(tree.preorder(), tree.postorder())
    first_five = list(islice(combined, 5))
    
    # Infinite iterator with generator
    def count_forever(start: int = 0) -> Generator[int, None, None]:
        n = start
        while True:
            yield n
            n += 1
    
    # Take first 10 from infinite sequence
    first_ten = list(islice(count_forever(), 10))
    print(f"First 10 naturals: {first_ten}")

Generators: Iterators Made Easy

Generators provide the same benefits as the Iterator Pattern (uniform traversal, encapsulation, polymorphism) with far less boilerplate. They're the modern way to implement custom iteration in languages that support them.

Summary: The Iterator Pattern Architecture

We've built the complete Iterator Pattern from the ground up. Let's consolidate what we've learned:

Key Takeaways

•Four participants — Iterator (interface), Concrete Iterator (implementation), Aggregate (collection interface), Concrete Aggregate (collection implementation)
•Iterator interface is minimal — has_next(), next(), and optionally reset() and current(). Simplicity enables wide adoption.
•Aggregate provides factory method — create_iterator() returns appropriate iterator without exposing internals
•Same interface, different implementations — ArrayIterator, LinkedListIterator, TreeIterator all satisfy the same interface
•Multiple traversal strategies — One collection can provide multiple iterator types (forward, reverse, filtered, different tree orders)
•Language integration — Most languages build the pattern into their syntax (for loops, comprehensions)
•Generators simplify implementation — Modern approach using yield requires minimal boilerplate

What's next:

In the next page, we'll explore the distinction between internal and external iterators—two fundamentally different approaches to iteration. You'll understand when to use each, how they differ in control flow, and how modern functional programming patterns relate to internal iteration.

Page Complete

You now understand the complete architecture of the Iterator Pattern—the interfaces, the implementations, and how they work together to provide uniform collection traversal. Next, we'll examine the internal vs external iterator distinction.

2 / 4

Loading learning content...

System Design (LLD)Iterator Pattern

Iterator Pattern: Uniform Collection Traversal

LevelIntermediate

Duration60 mins

TopicIterator Pattern

2 / 4

Solution: The Iterator Interface

Building the Uniform Traversal Mechanism

In the previous page, we identified a fundamental problem: code that traverses collections becomes tightly coupled to their internal structures. Change the structure, and every client breaks.

This page presents the complete Iterator Pattern architecture—the interfaces, the implementations, and the relationships that make uniform collection traversal possible.

What You Will Learn

Pattern Structure: The Four Participants

The Iterator Pattern involves four key participants, each with a distinct role in enabling uniform traversal:

Iterator Pattern Participants
Participant	Also Known As	Responsibility
Iterator	Cursor, Enumerator	Defines the interface for accessing and traversing elements
Concrete Iterator	ArrayIterator, LinkedListIterator	Implements Iterator interface, tracks current position in traversal
Aggregate	Collection, Container, Iterable	Defines interface for creating an Iterator object
Concrete Aggregate	ArrayList, LinkedList, CustomCollection	Implements Aggregate interface, returns appropriate Concrete Iterator

The relationship flow:

Client asks Aggregate for an Iterator
Concrete Aggregate creates and returns Concrete Iterator
Concrete Iterator has access to the aggregate's internals
Client uses Iterator interface to traverse—never touching aggregate internals

pattern_relationships.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# Iterator Pattern: Relationship Diagram
 
"""
┌─────────────────┐         ┌─────────────────┐
│    Iterator     │         │    Aggregate    │
│   (interface)   │         │   (interface)   │
├─────────────────┤         ├─────────────────┤
│ + has_next()    │         │ + create_       │
│ + next()        │         │   iterator()    │
│ + current()     │         │                 │
└────────▲────────┘         └────────▲────────┘
         │                           │
         │                           │
         │ implements                │ implements
         │                           │
┌────────┴────────┐         ┌────────┴────────┐
│ ConcreteIterator│◄────────│ConcreteAggregate│
│                 │ creates  │                 │
├─────────────────┤         ├─────────────────┤
│ - aggregate     │         │ - elements[]    │
│ - currentIndex  │         │ + add(element)  │
│ + has_next()    │         │ + remove(elem)  │
│ + next()        │         │ + create_       │
│ + current()     │         │   iterator()    │
└─────────────────┘         └─────────────────┘
 
Client code depends only on Iterator and Aggregate interfaces.
Concrete implementations are hidden from clients.
"""

The Key Insight

The Iterator Interface: Minimal but Complete

iterator_interface.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
from abc import ABC, abstractmethod
from typing import TypeVar, Generic, Optional
 
T = TypeVar('T')
 
class Iterator(ABC, Generic[T]):
    """
    Abstract Iterator Interface
    
    Defines the contract for traversing a collection.
    All concrete iterators must implement these methods.
    """
    
    @abstractmethod
    def has_next(self) -> bool:
        """
        Checks if there are more elements to traverse.
        
        Returns:
            True if next() will return an element,
            False if traversal is complete.
        
        Contract:
            - Must be idempotent (calling multiple times without next() 
              returns same result)
            - Must never modify the iterator's state
            - Should be O(1) time complexity
        """
        pass
    
    @abstractmethod
    def next(self) -> T:
        """
        Returns the current element and advances to the next position.
        
        Returns:
            The current element in the traversal
        
        Raises:
            StopIteration: If no more elements exist
        
        Contract:
            - Must advance position after returning element
            - Calling after has_next() returns False raises exception
            - Should be O(1) amortized time complexity
        """
        pass
    
    @abstractmethod
    def reset(self) -> None:
        """
        Resets the iterator to the beginning of the collection.
        
        After calling reset(), has_next() and next() behave as if
        the iterator were newly created.
        
        Contract:
            - Must restore iterator to initial state
            - Subsequent next() returns first element
        """
        pass
    
    def current(self) -> Optional[T]:
        """
        Returns the current element without advancing.
        
        Optional method - not all iterators support this.
        Default implementation raises NotImplementedError.
        
        Returns:
            Current element, or None if not positioned on an element
        """
        raise NotImplementedError("current() not supported by this iterator")

Core Iterator Operations

•has_next() — The sentinel that prevents overrun. Always check before calling next(). Returns boolean indicating more elements exist.
•next() — The workhorse. Returns current element and advances position. The 'move forward' action is atomic with retrieval.
•reset() — Restart capability. Returns iterator to beginning, enabling multiple traversals with same iterator instance.
•current() (optional) — Peek without advance. Useful when you need to inspect before deciding to consume.

Interface Variations

The Aggregate Interface: Iterator Factory

aggregate_interface.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
from abc import ABC, abstractmethod
from typing import TypeVar, Generic
 
T = TypeVar('T')
 
class Aggregate(ABC, Generic[T]):
    """
    Abstract Aggregate Interface
    
    Defines the contract for collections that can be iterated.
    Every collection that supports iteration implements this interface.
    """
    
    @abstractmethod
    def create_iterator(self) -> 'Iterator[T]':
        """
        Factory method for creating iterators.
        
        Returns:
            A new Iterator instance positioned at the beginning
            of this collection.
        
        Contract:
            - Must return a NEW iterator each call (independent traversals)
            - Iterator must be positioned before first element
            - Iterator must have access to collection's elements
        
        Why factory method?
            - Encapsulates iterator creation logic
            - Collection knows which iterator type is appropriate
            - Enables different iterator types (forward, reverse, filtered)
        """
        pass
    
    # Optional: Support for multiple iterator types
    def create_reverse_iterator(self) -> 'Iterator[T]':
        """Creates an iterator that traverses in reverse order."""
        raise NotImplementedError("Reverse iteration not supported")
    
    def create_filtered_iterator(
        self, 
        predicate: Callable[[T], bool]
    ) -> 'Iterator[T]':
        """Creates an iterator that yields only elements matching predicate."""
        raise NotImplementedError("Filtered iteration not supported")

Why is this a factory method?

The create_iterator() method is an example of the Factory Method pattern embedded within the Iterator pattern. The aggregate knows:

Its internal structure
Which iterator type can traverse that structure
How to initialize the iterator with access to its elements

Clients don't need any of this knowledge. They just call create_iterator() and receive something that satisfies the Iterator interface.

Multiple Iterator Types

Implementing an Array Iterator

Let's implement a complete Iterator for an array-based collection. This is the simplest concrete iterator—it tracks position with an integer index and advances by incrementing.

array_iterator.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
from typing import TypeVar, Generic, List, Optional
 
T = TypeVar('T')
 
class ArrayIterator(Iterator[T]):
    """
    Concrete Iterator for array-based collections.
    
    Tracks position using an integer index.
    Traverses from index 0 to len(array) - 1.
    """
    
    def __init__(self, items: List[T]):
        """
        Initialize iterator with reference to the array.
        
        Args:
            items: The array to iterate over
        
        Note: We store a reference, not a copy. This means:
            - Memory efficient (no duplication)
            - Iterator sees modifications to original array
            - Modifying array during iteration has undefined behavior
        """
        self._items = items
        self._current_index = 0
    
    def has_next(self) -> bool:
        """Check if more elements exist."""
        return self._current_index < len(self._items)
    
    def next(self) -> T:
        """Return current element and advance."""
        if not self.has_next():
            raise StopIteration("No more elements")
        
        element = self._items[self._current_index]
        self._current_index += 1
        return element
    
    def current(self) -> Optional[T]:
        """Return current element without advancing."""
        if self._current_index >= len(self._items):
            return None
        return self._items[self._current_index]
    
    def reset(self) -> None:
        """Reset to beginning of array."""
        self._current_index = 0
 
 
class ArrayList(Aggregate[T]):
    """
    Concrete Aggregate: An array-based list implementation.
    """
    
    def __init__(self):
        self._items: List[T] = []
    
    def add(self, item: T) -> None:
        """Add an item to the list."""
        self._items.append(item)
    
    def remove(self, item: T) -> bool:
        """Remove an item from the list. Returns True if removed."""
        try:
            self._items.remove(item)
            return True
        except ValueError:
            return False
    
    def __len__(self) -> int:
        """Return the number of items."""
        return len(self._items)
    
    def create_iterator(self) -> Iterator[T]:
        """
        Factory method: Create an iterator for this list.
        
        Returns a new ArrayIterator positioned at the start.
        Each call returns an INDEPENDENT iterator.
        """
        return ArrayIterator(self._items)
 
 
# Usage demonstration
def demo_array_iterator():
    # Create and populate the collection
    users = ArrayList[str]()
    users.add("Alice")
    users.add("Bob")
    users.add("Charlie")
    
    # Get an iterator - we don't know it's an ArrayIterator
    iterator: Iterator[str] = users.create_iterator()
    
    # Traverse using only the Iterator interface
    print("Users in the system:")
    while iterator.has_next():
        user = iterator.next()
        print(f"  - {user}")
    
    # Reset and traverse again
    iterator.reset()
    print("
Traversing again after reset:")
    while iterator.has_next():
        print(f"  - {iterator.next()}")

Reference vs Copy

Implementing a Linked List Iterator

linked_list_iterator.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
from typing import TypeVar, Generic, Optional
from dataclasses import dataclass
 
T = TypeVar('T')
 
@dataclass
class Node(Generic[T]):
    """A node in the linked list."""
    data: T
    next: Optional['Node[T]'] = None
 
 
class LinkedListIterator(Iterator[T]):
    """
    Concrete Iterator for linked list collections.
    
    Tracks position using a pointer to the current node.
    Traverses by following next pointers.
    """
    
    def __init__(self, head: Optional[Node[T]]):
        """
        Initialize with pointer to the head node.
        
        Args:
            head: The first node of the linked list (or None if empty)
        """
        self._head = head  # Store head for reset capability
        self._current = head  # Current position in traversal
    
    def has_next(self) -> bool:
        """Check if more elements exist."""
        return self._current is not None
    
    def next(self) -> T:
        """Return current element and advance to next node."""
        if not self.has_next():
            raise StopIteration("No more elements")
        
        data = self._current.data
        self._current = self._current.next  # Follow the pointer
        return data
    
    def current(self) -> Optional[T]:
        """Return current element without advancing."""
        if self._current is None:
            return None
        return self._current.data
    
    def reset(self) -> None:
        """Reset to the head of the list."""
        self._current = self._head
 
 
class LinkedList(Aggregate[T]):
    """
    Concrete Aggregate: A singly-linked list implementation.
    """
    
    def __init__(self):
        self._head: Optional[Node[T]] = None
        self._tail: Optional[Node[T]] = None
        self._size = 0
    
    def add(self, item: T) -> None:
        """Add an item to the end of the list."""
        new_node = Node(data=item)
        
        if self._tail is None:
            self._head = new_node
            self._tail = new_node
        else:
            self._tail.next = new_node
            self._tail = new_node
        
        self._size += 1
    
    def add_front(self, item: T) -> None:
        """Add an item to the front of the list (O(1))."""
        new_node = Node(data=item, next=self._head)
        self._head = new_node
        
        if self._tail is None:
            self._tail = new_node
        
        self._size += 1
    
    def __len__(self) -> int:
        """Return the number of items."""
        return self._size
    
    def create_iterator(self) -> Iterator[T]:
        """
        Factory method: Create an iterator for this linked list.
        
        Returns a LinkedListIterator, but caller only knows it's an Iterator.
        """
        return LinkedListIterator(self._head)
 
 
# The power: Same client code works for both!
def process_collection(collection: Aggregate[str]) -> None:
    """
    Generic function that works with ANY Aggregate.
    
    This code has NO IDEA whether it's processing:
    - An ArrayList
    - A LinkedList
    - A Tree
    - A Graph
    - A Database cursor
    - Any future collection type
    
    It only knows the collection provides an Iterator.
    """
    iterator = collection.create_iterator()
    
    count = 0
    while iterator.has_next():
        item = iterator.next()
        print(f"Processing: {item}")
        count += 1
    
    print(f"Total processed: {count}")
 
 
# Demonstration of polymorphism
def demo_polymorphic_iteration():
    # Create an ArrayList
    array_list = ArrayList[str]()
    array_list.add("Apple")
    array_list.add("Banana")
    array_list.add("Cherry")
    
    # Create a LinkedList
    linked_list = LinkedList[str]()
    linked_list.add("Dog")
    linked_list.add("Elephant")
    linked_list.add("Fox")
    
    # Same function processes both!
    print("Processing ArrayList:")
    process_collection(array_list)
    
    print("
Processing LinkedList:")
    process_collection(linked_list)

This is the power of the Iterator Pattern in action.

True Polymorphism Achieved

Implementing a Tree Iterator

tree_iterators.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
from typing import TypeVar, Generic, Optional, List
from dataclasses import dataclass
from collections import deque
 
T = TypeVar('T')
 
@dataclass
class TreeNode(Generic[T]):
    """A node in a binary tree."""
    data: T
    left: Optional['TreeNode[T]'] = None
    right: Optional['TreeNode[T]'] = None
 
 
class InOrderTreeIterator(Iterator[T]):
    """
    Iterator that traverses a binary tree in-order (left, root, right).
    
    Uses a stack to simulate the recursive traversal iteratively.
    This yields elements in sorted order for a BST.
    """
    
    def __init__(self, root: Optional[TreeNode[T]]):
        self._root = root
        self._stack: List[TreeNode[T]] = []
        self._push_left_chain(root)
    
    def _push_left_chain(self, node: Optional[TreeNode[T]]) -> None:
        """Push node and all its left descendants onto the stack."""
        while node is not None:
            self._stack.append(node)
            node = node.left
    
    def has_next(self) -> bool:
        """More elements exist if stack is not empty."""
        return len(self._stack) > 0
    
    def next(self) -> T:
        """Return next in-order element."""
        if not self.has_next():
            raise StopIteration("No more elements")
        
        # Pop the top node (next in-order element)
        node = self._stack.pop()
        
        # If it has a right child, push that child's left chain
        if node.right is not None:
            self._push_left_chain(node.right)
        
        return node.data
    
    def reset(self) -> None:
        """Reset to the beginning of in-order traversal."""
        self._stack.clear()
        self._push_left_chain(self._root)
 
 
class PreOrderTreeIterator(Iterator[T]):
    """
    Iterator that traverses a binary tree pre-order (root, left, right).
    
    Pre-order is useful for copying trees or prefix expressions.
    """
    
    def __init__(self, root: Optional[TreeNode[T]]):
        self._root = root
        self._stack: List[TreeNode[T]] = []
        if root is not None:
            self._stack.append(root)
    
    def has_next(self) -> bool:
        return len(self._stack) > 0
    
    def next(self) -> T:
        if not self.has_next():
            raise StopIteration("No more elements")
        
        node = self._stack.pop()
        
        # Push right first (so left is processed first - LIFO)
        if node.right is not None:
            self._stack.append(node.right)
        if node.left is not None:
            self._stack.append(node.left)
        
        return node.data
    
    def reset(self) -> None:
        self._stack.clear()
        if self._root is not None:
            self._stack.append(self._root)
 
 
class LevelOrderTreeIterator(Iterator[T]):
    """
    Iterator that traverses a binary tree level-by-level (BFS).
    
    Level-order is useful for printing trees visually or finding shortest paths.
    """
    
    def __init__(self, root: Optional[TreeNode[T]]):
        self._root = root
        self._queue: deque[TreeNode[T]] = deque()
        if root is not None:
            self._queue.append(root)
    
    def has_next(self) -> bool:
        return len(self._queue) > 0
    
    def next(self) -> T:
        if not self.has_next():
            raise StopIteration("No more elements")
        
        node = self._queue.popleft()
        
        # Enqueue children (left first, then right)
        if node.left is not None:
            self._queue.append(node.left)
        if node.right is not None:
            self._queue.append(node.right)
        
        return node.data
    
    def reset(self) -> None:
        self._queue.clear()
        if self._root is not None:
            self._queue.append(self._root)
 
 
class BinaryTree(Aggregate[T]):
    """
    Concrete Aggregate: A binary tree with multiple iterator types.
    """
    
    def __init__(self):
        self._root: Optional[TreeNode[T]] = None
    
    def set_root(self, root: TreeNode[T]) -> None:
        """Set the root node of the tree."""
        self._root = root
    
    def create_iterator(self) -> Iterator[T]:
        """Default iterator: in-order traversal."""
        return InOrderTreeIterator(self._root)
    
    def create_preorder_iterator(self) -> Iterator[T]:
        """Create a pre-order traversal iterator."""
        return PreOrderTreeIterator(self._root)
    
    def create_levelorder_iterator(self) -> Iterator[T]:
        """Create a level-order (BFS) traversal iterator."""
        return LevelOrderTreeIterator(self._root)
 
 
# Demonstration
def demo_tree_iterators():
    """
    Build a tree and traverse it multiple ways.
    
            4
           / \
          2   6
         / \ / \
        1  3 5  7
    """
    # Build the tree
    tree = BinaryTree[int]()
    
    node1 = TreeNode(1)
    node3 = TreeNode(3)
    node5 = TreeNode(5)
    node7 = TreeNode(7)
    node2 = TreeNode(2, left=node1, right=node3)
    node6 = TreeNode(6, left=node5, right=node7)
    root = TreeNode(4, left=node2, right=node6)
    
    tree.set_root(root)
    
    # Same tree, different traversal orders
    print("In-Order (sorted): ", end="")
    for_each(tree.create_iterator(), lambda x: print(x, end=" "))
    print()  # Output: 1 2 3 4 5 6 7
    
    print("Pre-Order (root first): ", end="")
    for_each(tree.create_preorder_iterator(), lambda x: print(x, end=" "))
    print()  # Output: 4 2 1 3 6 5 7
    
    print("Level-Order (BFS): ", end="")
    for_each(tree.create_levelorder_iterator(), lambda x: print(x, end=" "))
    print()  # Output: 4 2 6 1 3 5 7
 
 
def for_each(iterator: Iterator, action: Callable) -> None:
    """Apply action to each element from the iterator."""
    while iterator.has_next():
        action(iterator.next())

Multiple Iterators, One Collection

Language Integration: Python's Iterator Protocol

The Iterator Pattern is so fundamental that Python builds it directly into the language. Understanding Python's iterator protocol helps you leverage the pattern with native syntax.

python_protocol.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
from typing import TypeVar, Generic, Optional, List
 
T = TypeVar('T')
 
class PythonicArrayList(Generic[T]):
    """
    A collection that implements Python's iterator protocol.
    
    Python's protocol uses:
    - __iter__(): Returns an iterator (like create_iterator())
    - __next__(): Returns next element (like next())
    
    When these are implemented, the collection works with:
    - for loops
    - list comprehensions
    - zip(), map(), filter()
    - any() and all()
    - Unpacking: a, b, c = collection
    """
    
    def __init__(self):
        self._items: List[T] = []
    
    def add(self, item: T) -> None:
        self._items.append(item)
    
    def __iter__(self):
        """
        Return an iterator for this collection.
        
        Python calls this when you write:
            for item in collection:
                ...
        """
        return PythonicArrayListIterator(self._items)
    
    def __len__(self) -> int:
        return len(self._items)
 
 
class PythonicArrayListIterator:
    """Python-style iterator with __iter__ and __next__."""
    
    def __init__(self, items: List[T]):
        self._items = items
        self._index = 0
    
    def __iter__(self):
        """Iterators are also iterable (return self)."""
        return self
    
    def __next__(self) -> T:
        """
        Return next element or raise StopIteration.
        
        Python's for loop catches StopIteration automatically
        and exits the loop cleanly.
        """
        if self._index >= len(self._items):
            raise StopIteration
        
        item = self._items[self._index]
        self._index += 1
        return item
 
 
# Now the collection integrates with Python's syntax!
def demo_pythonic_iteration():
    collection = PythonicArrayList[str]()
    collection.add("Python")
    collection.add("Java")
    collection.add("TypeScript")
    
    # Native for loop - Python calls __iter__ and __next__
    print("Using for loop:")
    for language in collection:
        print(f"  {language}")
    
    # List comprehension
    upper_languages = [lang.upper() for lang in collection]
    print(f"Uppercase: {upper_languages}")
    
    # Built-in functions
    print(f"Any starts with 'P': {any(lang.startswith('P') for lang in collection)}")
    print(f"All have length > 2: {all(len(lang) > 2 for lang in collection)}")
    
    # Unpacking
    first, *rest = collection
    print(f"First: {first}, Rest: {rest}")
    
    # Creating list from iterator
    as_list = list(collection)
    print(f"As list: {as_list}")

Iterator Protocol Across Languages
Language	Create Iterator	Check Has Next	Get Next	Loop Syntax
Python	iter()	(implicit)	next()	for x in collection:
Java	iterator()	hasNext()	next()	for (T x : collection)
JavaScript	Symbol.iterator	(implicit)	next().done	for (const x of collection)
C++	begin()	it != end()	*it++	for (auto x : collection)
C#	GetEnumerator()	MoveNext()	Current	foreach (var x in collection)

The Pattern is Universal

Modern Approach: Generator-Based Iterators

generator_iterators.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
from typing import Generator, TypeVar, List, Optional
from dataclasses import dataclass
 
T = TypeVar('T')
 
@dataclass
class TreeNode:
    value: int
    left: Optional['TreeNode'] = None
    right: Optional['TreeNode'] = None
 
 
class BinaryTreeWithGenerators:
    """
    Tree that uses generators for iteration.
    
    Generators dramatically simplify iterator implementation:
    - No manual state management
    - No stack/queue data structures
    - Code reads like the recursive algorithm
    """
    
    def __init__(self):
        self.root: Optional[TreeNode] = None
    
    def inorder(self) -> Generator[int, None, None]:
        """
        In-order traversal using a generator.
        
        Compare this to InOrderTreeIterator class:
        - No __init__ with state
        - No stack management
        - No has_next/next methods
        - Just yield when we have a value
        """
        def traverse(node: Optional[TreeNode]) -> Generator[int, None, None]:
            if node is not None:
                yield from traverse(node.left)   # All left values
                yield node.value                  # This value
                yield from traverse(node.right)  # All right values
        
        return traverse(self.root)
    
    def preorder(self) -> Generator[int, None, None]:
        """Pre-order traversal: root, left, right."""
        def traverse(node: Optional[TreeNode]) -> Generator[int, None, None]:
            if node is not None:
                yield node.value
                yield from traverse(node.left)
                yield from traverse(node.right)
        
        return traverse(self.root)
    
    def postorder(self) -> Generator[int, None, None]:
        """Post-order traversal: left, right, root."""
        def traverse(node: Optional[TreeNode]) -> Generator[int, None, None]:
            if node is not None:
                yield from traverse(node.left)
                yield from traverse(node.right)
                yield node.value
        
        return traverse(self.root)
    
    def levelorder(self) -> Generator[int, None, None]:
        """Level-order traversal (BFS)."""
        if self.root is None:
            return
        
        queue = [self.root]
        while queue:
            node = queue.pop(0)
            yield node.value
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    
    def __iter__(self) -> Generator[int, None, None]:
        """Default iteration is in-order."""
        return self.inorder()
 
 
# Even more powerful: generator expressions and comprehensions
def demo_generators():
    tree = BinaryTreeWithGenerators()
    # Set up tree...
    
    # Generator expressions are lazy iterators
    doubled = (x * 2 for x in tree.inorder())
    filtered = (x for x in tree if x > 5)
    
    # Chain iterators together
    from itertools import chain, islice
    
    # First 5 elements from chained traversals
    combined = chain(tree.preorder(), tree.postorder())
    first_five = list(islice(combined, 5))
    
    # Infinite iterator with generator
    def count_forever(start: int = 0) -> Generator[int, None, None]:
        n = start
        while True:
            yield n
            n += 1
    
    # Take first 10 from infinite sequence
    first_ten = list(islice(count_forever(), 10))
    print(f"First 10 naturals: {first_ten}")

Generators: Iterators Made Easy

Summary: The Iterator Pattern Architecture

We've built the complete Iterator Pattern from the ground up. Let's consolidate what we've learned:

Key Takeaways

•Four participants — Iterator (interface), Concrete Iterator (implementation), Aggregate (collection interface), Concrete Aggregate (collection implementation)
•Iterator interface is minimal — has_next(), next(), and optionally reset() and current(). Simplicity enables wide adoption.
•Aggregate provides factory method — create_iterator() returns appropriate iterator without exposing internals
•Same interface, different implementations — ArrayIterator, LinkedListIterator, TreeIterator all satisfy the same interface
•Multiple traversal strategies — One collection can provide multiple iterator types (forward, reverse, filtered, different tree orders)
•Language integration — Most languages build the pattern into their syntax (for loops, comprehensions)
•Generators simplify implementation — Modern approach using yield requires minimal boilerplate

What's next:

Page Complete

2 / 4