Iterator

The Iterator Pattern is a behavioral design pattern that provides a way to access the elements of a collection sequentially without exposing its underlying storage representation (such as lists, trees, hash maps, or complex graph structures). By extracting the traversal state and algorithms into dedicated iterator objects, it decouples client applications from structural data representations.

1. Learning Objectives

• Understand the Single Responsibility Principle by decoupling traversal algorithms from data containers.
• Differentiate between the mechanics of Fail-Fast and Fail-Safe iterators.
• Trace how the JVM optimizes enhanced for-loop syntax sugars into iterator instances.
• Evaluate the memory overhead of maintaining multiple independent traversers on the same collection.
• Implement custom graph-traversal iterators (BFS/DFS) in Java, Python, and modern C++.

2. Problem & Naive Solution

Suppose you are building a profile connection manager for a social networking platform. Profiles are connected in a graph structure representing friendships. Clients need to traverse the friend network to build recommendation lists or display feeds.

The Naive Solution

In a naive implementation, the client class accesses the internal data structures of the social graph directly and implements its own Depth-First Search (DFS) stack routing:

This direct-access model presents serious design flaws:

• Exposed Internal Structure: If you decide to change the internal graph representation from an adjacency list to an adjacency matrix or a database index query, the client code breaks.
• Violates SRP: The client service is bloated with graph traversal routing, queues, and search stacks instead of focusing on rendering feeds.
• Traversal Code Duplication: If another service (e.g. recommendation engine) needs to traverse the graph, it must copy-paste the DFS/BFS stack logic.

3. Issues

Direct client coupling to concrete collections prevents refactoring. Changing storage collections (e.g., from ArrayList to LinkedList or TreeSet) forces rewrites of client loops. Furthermore, running multiple traversals on the same collection simultaneously is impossible if traversal indices are stored directly inside the collection class.

4. Pattern Introduction & UML

The Iterator Pattern solves this by extracting the traversal logic into a separate ProfileIterator interface. The collection (SocialNetwork) exposes a method to create an iterator. The client calls hasNext() and getNext() on the iterator. The iterator manages the internal stack, current index pointer, and visited nodes, shielding the client from the underlying graph structure.

UML: Graph Iterator System

5. Participants

• Iterable Collection (SocialNetwork): Declares the factory method for creating the Iterator.
• Concrete Collection (ConcreteSocialNetwork): Implements the factory method, returning an instance of the concrete iterator configured with reference loops.
• Iterator (ProfileIterator): Declares the iteration interface (hasNext(), getNext()).
• Concrete Iterator (ConcreteDFSIterator): Implements traversal (DFS) and tracks the current search index and stack state.
• Client (FeedDisplayService): Calls the iterator methods to traverse the collection.

6. Theory (Fail-Fast vs. Fail-Safe Iterators)

A key consideration in iterator design is handling concurrent modifications to the collection:

• Fail-Fast Iterators: Throw a ConcurrentModificationException immediately if the collection is structurally modified (items added or deleted) during traversal. - *How*: The collection maintains a modCount modification counter. The iterator copies this counter on instantiation. On every step (next()), it checks if modCount != expectedModCount.
• Fail-Safe (Non-Seismic) Iterators: Traverse a clone of the collection or work on concurrent structures (e.g. CopyOnWriteArrayList). - *How*: They operate on a copy of the collection, allowing modifications without exceptions, but at the cost of higher memory usage.

7. Syntax Explanation

Language-specific constructs for iteration support:

• Java: Standard interfaces java.util.Iterator and java.lang.Iterable enable clean integration with the native enhanced for-loop.
• Python: Overriding __iter__() (returns the iterator object) and __next__() (returns the next value, raising StopIteration when complete) enables native for item in collection: syntax.
• C++: STL iterators require overloading operator functions (operator++, operator*, and operator!=), enabling integration with range-based for loops.

8. Step-by-Step Implementation

1. Step 1: Create the Iterator interface defining methods like hasNext() and getNext().
2. Step 2: Create the IterableCollection interface containing the factory method createIterator().
3. Step 3: Implement the ConcreteCollection class containing the actual storage container.
4. Step 4: Build the ConcreteIterator class, capturing the collection reference and implementing the traversal logic (e.g., stack routing).
5. Step 5: Modify the client to execute traversals by calling factory methods and looping over the returned iterator.

9. Complete Code (Mini Project)

10. Code Walkthrough

Let's walk through the decoupled graph navigation:

• Encapsulated Traversal Algorithms: The DFS stack is stored entirely inside the ConcreteDFSIterator instance. The client code is free of index checks and stack logic.
• Information Hiding: The client does not know how friendships are mapped (adjacency lists, arrays, database queries). It simply iterates over connections.
• Independent Traversals: Because the iterator maintains its own state stack, you can create multiple iterators on the same network graph simultaneously without interference.

11. Execution Flow

1. Client Call: Client calls createFriendsIterator("Alice").
2. Iterator Creation: The collection instantiates ConcreteDFSIterator, loading "Alice" onto its internal stack.
3. Next Check: Client calls iterator.hasNext(). The iterator clears already visited items and checks if its stack is empty.
4. Item Retrieval: Client calls iterator.getNext(). The iterator pops the top item, records it as visited, loads its neighbors onto the stack, and returns the profile ID.

12. Internal Working (Compiler Optimization & Syntactic Sugar)

Iterators are so common that modern languages implement syntactic sugar for them:

• JVM Syntactic Sugar Conversion: When you write a Java enhanced for loop:

13. Complexity Analysis

• Time Complexity: $O(1)$ constant time per step (hasNext(), getNext()). Total traversal takes $O(V + E)$ where $V$ is profiles and $E$ is connections.
• Space Complexity: $O(V)$ space inside the iterator stack and visited set to track graph vertices.

14. Best Practices

• Clean up resources: If your iterator is fetching data from a database or file, implement AutoCloseable (Java) or context managers (Python) to close resources when traversal ends.
• Prefer Fail-Fast Implementation: Check database/collection modification states to prevent hard-to-debug concurrency issues.

15. Common Mistakes

• Modifying Collections Directly During Iteration: Calling collection.remove(item) inside an iterator loop instead of iterator.remove(), which throws ConcurrentModificationException.
• Sharing Iterator Instances: Attempting to share a single iterator object across different client threads, causing race conditions in pointer states.

16. Framework Usage

• Java Collections Iterator: Every class in the Java Collections Framework (ArrayList, HashSet) implements Iterable to support traversal.
• Python iter() and next(): Built-in structures support iterator interfaces automatically.
• C++ STL Iterators: STL algorithms like std::find and std::sort operate entirely on iterators, decoupling algorithms from data containers.

17. Interview Discussion

18. Practice Exercises

• Easy: Write a Python program containing a custom list iterator that traverses elements in reverse.
• Medium: Design a binary search tree (BST) iterator in Java with an in-order traversal route.
• Hard: Build a dynamic paginated database cursor iterator in C++ that loads data chunks on-demand as the user scrolls.

19. Challenge Problem

Design an Inventory Stock Sheet Multi-Traverser. An warehouse inventory system organizes products in a multi-level category hierarchy (e.g. Electronics -> Computers -> Laptops). You must implement an iterator engine that can traverse this inventory using two strategies: Category Depth-First Search (visiting subcategories recursively) and Alphabetical SKU Search (traversing products alphabetically across all categories). Write a solution in Java, Python, or C++ that supports running both traversal strategies polymorphically.

20. Summary & Cheat Sheet

• Iterator decouples traversal logic from structural data representations.
• Enables multiple independent traversals to run on the same collection concurrently.
• Fail-fast iterators throw exceptions on modifications; fail-safe iterators work on copies.
• Modern languages compile enhanced loop structures into iterator calls automatically.

21. Quiz

22. Next Lesson Preview

In the next lesson, we will explore the Observer Pattern. We will learn how to establish a one-to-many subscription model so that when one object changes state, all its dependents are notified automatically!