Iterator Pattern – Traverse Collections Uniformly and Flexibly

1. Introduction

Iterator (also known as Cursor) is a design pattern belonging to the Behavioral Pattern group. This pattern was created to solve a common problem: how do we traverse elements of different collection types without understanding their internal structure?

Imagine you have a TV remote control. Whether your TV is Samsung, LG, or Sony, the remote allows you to change channels the same way: press "Next" for the next channel, press "Previous" to go back. You don't need to know how the TV stores its channel list – the remote has abstracted that entire process. The Iterator Pattern works on the same principle.

This approach adheres to the Single Responsibility Principle (SRP): a class should have only one responsibility. The collection is responsible for storing data, while the Iterator is responsible for providing a way to traverse that data. Thanks to this separation, Iterators can work flexibly with many different collection types.

2. Purpose and Motivation

Problem

Collections are among the most common data types in programming. From simple lists (List, Array) to complex structures like Stack, Tree, and Graph – all need a way to access their elements.

With a simple list, traversing elements is fairly easy – you just need a for loop. But what about a Tree structure? Do you want to traverse depth-first or breadth-first? And with a Graph, how do you ensure you don't revisit nodes you've already traversed?

The problem becomes more complex when:

Each collection type requires different traversal algorithms, forcing client code to "know too much" about internal structures.

Cramming multiple traversal algorithms into a collection class obscures its primary responsibility of data storage.

Your code becomes tightly coupled to specific collection types, making it difficult to extend and maintain.

Solution

The Iterator Pattern proposes an elegant solution: extract the traversal behavior from the collection and encapsulate it in a separate object called an Iterator.

The Iterator encapsulates all traversal details: current position, next element, termination conditions... More importantly, all Iterators implement the same interface. This allows client code to work with any collection type through a unified interface.

Real-World Example:

Imagine you're visiting Rome and want to see all the famous landmarks. You have three options:

Wander on your own: You explore by yourself, potentially revisiting places and missing important sites. This is like writing collection traversal code without a pattern.

Use Google Maps: The app provides a unified way to navigate, telling you where to go next and how far it is. This is the Iterator – a standardized interface helping you "traverse" locations.

Hire a local guide: The guide can customize the route based on your preferences – similar to creating a Custom Iterator for special needs.

All these options help you "traverse" the collection of Rome's landmarks, but with different approaches and flexibility levels.

3. Architecture

The Iterator Pattern consists of the following components:

Iterator Interface: Declares the methods needed to traverse a collection, such as First(), Next(), IsDone(), CurrentItem(). This is the "contract" that all Concrete Iterators must follow.

Concrete Iterator: Implements the methods from the Iterator Interface. Each Concrete Iterator manages its own traversal state (current position, step size...), allowing multiple independent Iterators to traverse the same collection.

Collection Interface (Iterable): Declares the CreateIterator() method to create a compatible Iterator. The return type is the Iterator Interface, not Concrete Iterator – this ensures polymorphism.

Concrete Collection: Implements the Collection Interface, returning an appropriate Concrete Iterator instance when requested by the client.

Client: Uses the Iterator Pattern by requesting an Iterator from the collection, then traverses elements through the unified interface without knowing the collection's internal structure.

4. Pros and Cons

Advantages

Adheres to Single Responsibility Principle (SRP): Storage logic and traversal logic are clearly separated into different classes.

Adheres to Open/Closed Principle (OCP): You can add new collection types or Iterators without affecting existing code.

Supports parallel traversal: Each Iterator has its own state, allowing multiple Iterators to independently traverse the same collection.

Lazy Iteration: In some cases, you can pause traversal and continue later when needed (e.g., yield return in C#).

Disadvantages

Unnecessary overhead: For simple collections like List or Array, using Iterator can be more complex than direct traversal with a for loop.

Increased class count: Each collection type may need one or more Concrete Iterators, increasing codebase complexity.

5. When to Use

The Iterator Pattern is suitable for the following situations:

When collections have complex structures: If you're working with Trees, Graphs, or recursive data structures, Iterator helps hide complexity and provides a simple interface for clients.

When you need to reduce code duplication: Instead of rewriting traversal logic in multiple places, you encapsulate it in an Iterator and reuse it.

When you need a unified interface: If your code needs to work with various collection types (List, Tree, Graph...) in the same way, Iterator is the ideal solution.

When data structures are unknown in advance: If your application needs flexibility with many collection types, programming to the Iterator Interface makes code easier to extend in the future.

6. C# Implementation Example

Below is a complete example of implementing the Iterator Pattern in C#.

Step 1: Create the Item Class

csharp

// Collection Item
public class Item
{
    private string name;
    
    public Item(string name)
    {
        this.name = name;
    }
    
    public string Name
    {
        get { return name; }
    }
}

Step 2: Declare the Iterator Interface

csharp

// Iterator Interface
public interface IAbstractIterator
{
    Item First();
    Item Next();
    bool IsDone { get; }
    Item CurrentItem { get; }
    int Step { get; set; }
}

Step 3: Declare the Collection Interface

csharp

// Iterable Collection Interface
public interface IAbstractCollection
{
    IAbstractIterator CreateIterator();
}

Step 4: Implement the Concrete Collection

csharp

// Concrete Collection
public class Collection : IAbstractCollection
{
    private List<Item> items = new List<Item>();
    
    public IAbstractIterator CreateIterator()
    {
        return new Iterator(this);
    }
    
    public int Count
    {
        get { return items.Count; }
    }
    
    public Item this[int index]
    {
        get { return items[index]; }
        set { items.Add(value); }
    }
}

Step 5: Implement the Concrete Iterator

csharp

// Concrete Iterator
public class Iterator : IAbstractIterator
{
    private Collection collection;
    private int current = 0;
    private int step = 1;
    
    public Iterator(Collection collection)
    {
        this.collection = collection;
    }
    
    public Item First()
    {
        current = 0;
        return collection[current];
    }
    
    public Item Next()
    {
        current += step;
        return !IsDone ? collection[current] : null;
    }
    
    public int Step
    {
        get { return step; }
        set { step = value; }
    }
    
    public Item CurrentItem
    {
        get { return collection[current]; }
    }
    
    public bool IsDone
    {
        get { return current >= collection.Count; }
    }
}

Step 6: Use in Client Code

csharp

public class Program
{
    public static void Main(string[] args)
    {
        // Build the collection
        Collection collection = new Collection();
        for (int i = 0; i <= 8; i++)
        {
            collection[i] = new Item($"Item {i}");
        }
        
        // Create iterator
        IAbstractIterator iterator = collection.CreateIterator();
        
        // Set step to 3 (skip every 2 elements)
        iterator.Step = 3;
        
        Console.WriteLine("Iterating over collection with step 3:");
        for (Item item = iterator.First(); !iterator.IsDone; item = iterator.Next())
        {
            Console.WriteLine(item.Name);
        }
        
        Console.ReadKey();
    }
}
```

**Output:**
```
Iterating over collection with step 3:
Item 0
Item 3
Item 6

7. Related Patterns

Composite: Iterator is often used to traverse recursive structures like Composite Trees.

Factory Method: Can be combined to allow collection subclasses to return different Iterator types.

Memento: Combined with Iterator to save and restore traversal state when needed.

Visitor: Combined with Iterator to perform operations on each element when traversing complex data structures.

If you found this article helpful, explore more in the Design Patterns Series to enhance your programming skills!

References

[1] Refactoring.Guru. https://refactoring.guru/design-patterns

[2] Design Patterns for Dummies, Steve Holzner, PhD

[3] Head First Design Patterns, Eric Freeman

[4] Gang of Four Design Patterns 4.0

[5] Dive into Design Patterns