The Iterator Pattern is a behavioral design pattern that provides a way to access the elements of an aggregate object sequentially without exposing its underlying representation. It decouples algorithms from containers, allowing you to traverse different data structures using a common interface.
Core Concept
The Iterator Pattern separates the responsibility of accessing and traversing elements from the collection itself. This allows you to iterate through collections without knowing their internal structure, whether it’s a list, tree, graph, or any other complex data structure.
Key Components
┌─────────────────┐ ┌─────────────────┐
│ Iterator │ │ Aggregate │
│ (Interface) │ │ (Interface) │
├─────────────────┤ ├─────────────────┤
│ + has_next() │ │ + iterator() │
│ + next() │ └─────────────────┘
└─────────────────┘ △
△ │
│ │
┌─────────────────┐ ┌─────────────────┐
│ ConcreteIterator│ │ConcreteAggregate│
├─────────────────┤ ├─────────────────┤
│ + has_next() │◄───┤ + iterator() │
│ + next() │ │ + add_item() │
│ - current_index │ │ - items[] │
└─────────────────┘ └─────────────────┘
The pattern involves four main participants:
- Iterator Interface: Defines the interface for accessing and traversing elements
- Concrete Iterator: Implements the iterator interface and keeps track of current position
- Aggregate Interface: Defines interface for creating iterator objects
- Concrete Aggregate: Implements the aggregate interface and returns appropriate iterator
Benefits
The Iterator Pattern provides several advantages:
- Uniform Interface: Provides a consistent way to traverse different types of collections
- Encapsulation: Hides the internal structure of the collection from clients
- Multiple Traversals: Supports multiple simultaneous traversals of the same collection
- Simplified Collection Interface: Collections don’t need to expose traversal methods
- Polymorphism: Different iterators can implement different traversal algorithms
When to Use
Consider using the Iterator Pattern when:
- You need to access elements of a collection without exposing its internal structure
- You want to support multiple ways of traversing the same collection
- You need a uniform interface for traversing different types of collections
- You want to reduce coupling between collection classes and algorithms that operate on them
Example 1: Custom Book Collection Iterator
This example demonstrates a basic implementation of the Iterator Pattern for a book collection:This example shows the fundamental structure of the Iterator Pattern. The BookCollection class manages a collection of books internally, but clients can traverse it using the BookIterator without knowing how the books are stored. The iterator maintains its own position state, allowing multiple independent traversals of the same collection.
from abc import ABC, abstractmethod
from typing import List, Optional, Any
class Iterator(ABC):
"""Abstract iterator interface"""
@abstractmethod
def has_next(self) -> bool:
"""Check if there are more elements to iterate"""
pass
@abstractmethod
def next(self) -> Any:
"""Get the next element in the iteration"""
pass
class Aggregate(ABC):
"""Abstract aggregate interface"""
@abstractmethod
def create_iterator(self) -> Iterator:
"""Create and return an iterator for this aggregate"""
pass
class Book:
"""Simple book class to demonstrate the pattern"""
def __init__(self, title: str, author: str) -> None:
self.title = title
self.author = author
def __str__(self) -> str:
return f"'{self.title}' by {self.author}"
class BookIterator(Iterator):
"""Concrete iterator for book collections"""
def __init__(self, books: List[Book]) -> None:
self._books: List[Book] = books
self._position: int = 0
def has_next(self) -> bool:
"""Check if there are more books to iterate through"""
return self._position < len(self._books)
def next(self) -> Book:
"""Get the next book in the collection"""
if not self.has_next():
raise StopIteration("No more books in the collection")
book = self._books[self._position]
self._position += 1
return book
class BookCollection(Aggregate):
"""Concrete aggregate that holds a collection of books"""
def __init__(self) -> None:
self._books: List[Book] = []
def add_book(self, book: Book) -> None:
"""Add a book to the collection"""
self._books.append(book)
def create_iterator(self) -> BookIterator:
"""Create and return an iterator for this book collection"""
return BookIterator(self._books)
def get_count(self) -> int:
"""Get the total number of books in the collection"""
return len(self._books)
def main():
"""Demonstrate the Iterator Pattern with a book collection"""
# Create a book collection
library = BookCollection()
# Add some books
library.add_book(Book("The Great Gatsby", "F. Scott Fitzgerald"))
library.add_book(Book("To Kill a Mockingbird", "Harper Lee"))
library.add_book(Book("1984", "George Orwell"))
library.add_book(Book("Pride and Prejudice", "Jane Austen"))
print(f"Library contains {library.get_count()} books:")
print("=" * 50)
# Create an iterator and traverse the collection
iterator = library.create_iterator()
# Iterate through all books
while iterator.has_next():
book = iterator.next()
print(f"📖 {book}")
print("=" * 50)
print("Finished iterating through the library!")
# Demonstrate multiple independent iterators
print("\nDemonstrating multiple iterators:")
print("-" * 35)
iterator1 = library.create_iterator()
iterator2 = library.create_iterator()
# Read first two books with iterator1
print("Iterator 1 - First two books:")
for _ in range(2):
if iterator1.has_next():
print(f" {iterator1.next()}")
# Read first book with iterator2
print("Iterator 2 - First book:")
if iterator2.has_next():
print(f" {iterator2.next()}")
# Continue with iterator1
print("Iterator 1 - Remaining books:")
while iterator1.has_next():
print(f" {iterator1.next()}")
if __name__ == "__main__":
main()
Key points in this implementation:
- The
Iteratorabstract class defines the interface that all iterators must follow BookIteratorimplements the concrete iteration logic, tracking its current positionBookCollectionserves as the aggregate that creates iterators- Multiple iterators can operate independently on the same collection
- The collection’s internal structure is completely hidden from clients
Example 2: Tree Structure Iterator with Different Traversal Strategies
This example demonstrates a more advanced use case where the Iterator Pattern enables different traversal strategies for the same data structure:This advanced example demonstrates how the Iterator Pattern can provide multiple ways to traverse the same data structure. The BinaryTree class can create different iterators based on the requested traversal strategy, each implementing a different algorithm while maintaining the same interface.
from abc import ABC, abstractmethod
from typing import List, Optional, Any, Deque
from collections import deque
from enum import Enum
class TraversalType(Enum):
"""Enumeration of supported traversal types"""
DEPTH_FIRST = "depth_first"
BREADTH_FIRST = "breadth_first"
IN_ORDER = "in_order"
class Iterator(ABC):
"""Abstract iterator interface"""
@abstractmethod
def has_next(self) -> bool:
"""Check if there are more elements to iterate"""
pass
@abstractmethod
def next(self) -> Any:
"""Get the next element in the iteration"""
pass
class TreeNode:
"""Node class for binary tree structure"""
def __init__(self, value: int) -> None:
self.value: int = value
self.left: Optional['TreeNode'] = None
self.right: Optional['TreeNode'] = None
def __str__(self) -> str:
return str(self.value)
class DepthFirstIterator(Iterator):
"""Iterator for depth-first traversal (pre-order)"""
def __init__(self, root: Optional[TreeNode]) -> None:
self._stack: List[TreeNode] = []
if root:
self._stack.append(root)
def has_next(self) -> bool:
"""Check if there are more nodes to visit"""
return len(self._stack) > 0
def next(self) -> TreeNode:
"""Get the next node in depth-first order"""
if not self.has_next():
raise StopIteration("No more nodes to traverse")
# Pop current node from stack
current = self._stack.pop()
# Add children to stack (right first, then left for correct order)
if current.right:
self._stack.append(current.right)
if current.left:
self._stack.append(current.left)
return current
class BreadthFirstIterator(Iterator):
"""Iterator for breadth-first traversal (level-order)"""
def __init__(self, root: Optional[TreeNode]) -> None:
self._queue: Deque[TreeNode] = deque()
if root:
self._queue.append(root)
def has_next(self) -> bool:
"""Check if there are more nodes to visit"""
return len(self._queue) > 0
def next(self) -> TreeNode:
"""Get the next node in breadth-first order"""
if not self.has_next():
raise StopIteration("No more nodes to traverse")
# Remove current node from queue
current = self._queue.popleft()
# Add children to queue
if current.left:
self._queue.append(current.left)
if current.right:
self._queue.append(current.right)
return current
class InOrderIterator(Iterator):
"""Iterator for in-order traversal (left, root, right)"""
def __init__(self, root: Optional[TreeNode]) -> None:
self._stack: List[TreeNode] = []
self._current: Optional[TreeNode] = root
def has_next(self) -> bool:
"""Check if there are more nodes to visit"""
return self._current is not None or len(self._stack) > 0
def next(self) -> TreeNode:
"""Get the next node in in-order sequence"""
if not self.has_next():
raise StopIteration("No more nodes to traverse")
# Go to the leftmost node
while self._current:
self._stack.append(self._current)
self._current = self._current.left
# Current must be None at this point, so pop from stack
self._current = self._stack.pop()
result = self._current
# Move to right subtree
self._current = self._current.right
return result
class BinaryTree:
"""Binary tree aggregate that can create different types of iterators"""
def __init__(self) -> None:
self.root: Optional[TreeNode] = None
def insert(self, value: int) -> None:
"""Insert a value into the binary search tree"""
if self.root is None:
self.root = TreeNode(value)
else:
self._insert_recursive(self.root, value)
def _insert_recursive(self, node: TreeNode, value: int) -> None:
"""Helper method for recursive insertion"""
if value < node.value:
if node.left is None:
node.left = TreeNode(value)
else:
self._insert_recursive(node.left, value)
else:
if node.right is None:
node.right = TreeNode(value)
else:
self._insert_recursive(node.right, value)
def create_iterator(self, traversal_type: TraversalType) -> Iterator:
"""Create an iterator based on the specified traversal type"""
if traversal_type == TraversalType.DEPTH_FIRST:
return DepthFirstIterator(self.root)
elif traversal_type == TraversalType.BREADTH_FIRST:
return BreadthFirstIterator(self.root)
elif traversal_type == TraversalType.IN_ORDER:
return InOrderIterator(self.root)
else:
raise ValueError(f"Unknown traversal type: {traversal_type}")
def print_tree_structure(root: Optional[TreeNode], prefix: str = "", is_last: bool = True) -> None:
"""Helper function to print tree structure visually"""
if root is not None:
print(prefix + ("└── " if is_last else "├── ") + str(root.value))
# Determine the new prefix for children
extension = " " if is_last else "│ "
# Print children
if root.left is not None or root.right is not None:
if root.right is not None:
print_tree_structure(root.right, prefix + extension, root.left is None)
if root.left is not None:
print_tree_structure(root.left, prefix + extension, True)
def main():
"""Demonstrate different tree traversal strategies using iterators"""
# Create and populate a binary search tree
tree = BinaryTree()
values = [50, 30, 70, 20, 40, 60, 80, 10, 25, 35, 45]
print("Building binary search tree with values:", values)
for value in values:
tree.insert(value)
print("\nTree structure:")
print("=" * 40)
print_tree_structure(tree.root)
# Demonstrate different traversal strategies
traversal_types = [
(TraversalType.DEPTH_FIRST, "Depth-First (Pre-order)"),
(TraversalType.BREADTH_FIRST, "Breadth-First (Level-order)"),
(TraversalType.IN_ORDER, "In-Order (Sorted)")
]
for traversal_type, description in traversal_types:
print(f"\n{description} Traversal:")
print("-" * 30)
iterator = tree.create_iterator(traversal_type)
result = []
while iterator.has_next():
node = iterator.next()
result.append(str(node.value))
print(" → ".join(result))
# Demonstrate multiple independent iterators
print("\nDemonstrating multiple independent iterators:")
print("-" * 45)
df_iterator = tree.create_iterator(TraversalType.DEPTH_FIRST)
bf_iterator = tree.create_iterator(TraversalType.BREADTH_FIRST)
print("Alternating between Depth-First and Breadth-First:")
for i in range(4): # Show first 4 elements from each
if df_iterator.has_next() and bf_iterator.has_next():
df_node = df_iterator.next()
bf_node = bf_iterator.next()
print(f" DF: {df_node.value}, BF: {bf_node.value}")
if __name__ == "__main__":
main()
Key features of this implementation:
- Strategy Integration: The pattern works seamlessly with the Strategy pattern to provide different traversal algorithms
- Complex Data Structures: Shows how the pattern handles non-linear data structures like trees
- Multiple Algorithms: Each iterator implements a completely different traversal algorithm (depth-first, breadth-first, in-order)
- Independent State: Multiple iterators can traverse the same tree simultaneously with different strategies
- Encapsulation: The tree’s internal structure remains hidden while providing flexible access patterns
The Iterator Pattern proves especially valuable when working with complex data structures where you need multiple ways to access the data. It provides a clean, consistent interface regardless of the underlying complexity of the traversal algorithm.