Iterator Design Pattern: Traversing Collections

You’re building a collection that stores data in a custom tree structure. You want to iterate over all elements, but exposing the internal structure would break encapsulation. The Iterator pattern provides a way to access elements of a collection sequentially without exposing its underlying representation.

Problem

Consider a custom collection that stores items in a specific way:

public class CustomCollection
{
    private int[] _items = new int[100];
    private int _count = 0;

    public void Add(int item)
    {
        _items[_count++] = item;
    }

    public int GetItem(int index)
    {
        return _items[index];
    }

    public int Count => _count;
}

To iterate, clients need to know about the internal array structure:

var collection = new CustomCollection();
collection.Add(1);
collection.Add(2);
collection.Add(3);

// Client needs to know about internal structure
for (int i = 0; i < collection.Count; i++)
{
    Console.WriteLine(collection.GetItem(i));
}

This breaks encapsulation. What if the internal structure changes? What if you want to iterate a tree or linked list differently?

Solution

The Iterator pattern provides a way to access elements of a collection sequentially without exposing its underlying representation.

Definition: The Iterator pattern lets you traverse elements of a collection without exposing its underlying representation (list, stack, tree, etc.).

The pattern separates the traversal logic from the collection, allowing different traversal algorithms to be applied to the same collection.

Pseudocode

Collection (IAggregate)
    ↓ creates
Iterator (IIterator)
    ↓ implemented by
ConcreteIterator
    ↓ traverses
ConcreteCollection

Examples

Here’s a complete, runnable C# implementation:

using System;
using System.Collections;
using System.Collections.Generic;

// Iterator interface
public interface IIterator<T>
{
    bool HasNext();
    T Next();
    void Reset();
}

// Aggregate interface
public interface IAggregate<T>
{
    IIterator<T> CreateIterator();
}

// Concrete collection
public class NumberCollection : IAggregate<int>
{
    private int[] _numbers;

    public NumberCollection(int[] numbers)
    {
        _numbers = numbers;
    }

    public IIterator<int> CreateIterator()
    {
        return new NumberIterator(_numbers);
    }
}

// Concrete iterator
public class NumberIterator : IIterator<int>
{
    private int[] _numbers;
    private int _position = 0;

    public NumberIterator(int[] numbers)
    {
        _numbers = numbers;
    }

    public bool HasNext()
    {
        return _position < _numbers.Length;
    }

    public int Next()
    {
        if (!HasNext())
        {
            throw new InvalidOperationException("No more elements");
        }
        return _numbers[_position++];
    }

    public void Reset()
    {
        _position = 0;
    }
}

// Usage
class Program
{
    static void Main()
    {
        var numbers = new int[] { 1, 2, 3, 4, 5 };
        var collection = new NumberCollection(numbers);
        var iterator = collection.CreateIterator();

        Console.WriteLine("Iterating through collection:");
        while (iterator.HasNext())
        {
            Console.WriteLine(iterator.Next());
        }

        // Reset and iterate again
        Console.WriteLine("\nIterating again:");
        iterator.Reset();
        while (iterator.HasNext())
        {
            Console.WriteLine(iterator.Next());
        }
    }
}

Output:

Iterating through collection:
1
2
3
4
5

Iterating again:
1
2
3
4
5

Real-World Example: Binary Tree Iterator

// Tree node
public class TreeNode
{
    public int Value { get; set; }
    public TreeNode Left { get; set; }
    public TreeNode Right { get; set; }

    public TreeNode(int value)
    {
        Value = value;
    }
}

// Tree collection
public class BinaryTree : IAggregate<int>
{
    private TreeNode _root;

    public BinaryTree(TreeNode root)
    {
        _root = root;
    }

    public IIterator<int> CreateIterator()
    {
        return new InOrderIterator(_root);
    }
}

// In-order iterator (left, root, right)
public class InOrderIterator : IIterator<int>
{
    private Stack<TreeNode> _stack = new Stack<TreeNode>();
    private TreeNode _current;

    public InOrderIterator(TreeNode root)
    {
        _current = root;
        while (_current != null)
        {
            _stack.Push(_current);
            _current = _current.Left;
        }
        if (_stack.Count > 0)
        {
            _current = _stack.Pop();
        }
    }

    public bool HasNext()
    {
        return _current != null || _stack.Count > 0;
    }

    public int Next()
    {
        if (!HasNext())
        {
            throw new InvalidOperationException("No more elements");
        }

        var node = _current;
        _current = _current.Right;

        while (_current != null)
        {
            _stack.Push(_current);
            _current = _current.Left;
        }

        if (_stack.Count > 0)
        {
            _current = _stack.Pop();
        }
        else
        {
            _current = null;
        }

        return node.Value;
    }

    public void Reset()
    {
        _stack.Clear();
        // Reinitialize (simplified)
    }
}

// Usage
var root = new TreeNode(4)
{
    Left = new TreeNode(2)
    {
        Left = new TreeNode(1),
        Right = new TreeNode(3)
    },
    Right = new TreeNode(6)
    {
        Left = new TreeNode(5),
        Right = new TreeNode(7)
    }
};

var tree = new BinaryTree(root);
var iterator = tree.CreateIterator();

Console.WriteLine("In-order traversal:");
while (iterator.HasNext())
{
    Console.Write(iterator.Next() + " ");
}
// Output: 1 2 3 4 5 6 7

C# Built-in Iterator Support

C# provides built-in iterator support through IEnumerable and yield:

public class CustomCollection : IEnumerable<int>
{
    private int[] _items;

    public CustomCollection(int[] items)
    {
        _items = items;
    }

    public IEnumerator<int> GetEnumerator()
    {
        foreach (var item in _items)
        {
            yield return item;
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

// Usage with foreach
var collection = new CustomCollection(new int[] { 1, 2, 3, 4, 5 });
foreach (var item in collection)
{
    Console.WriteLine(item);
}

Applications

Enterprise Use Cases:

1. Collection Traversal: Iterating over custom data structures
2. Database Result Sets: Iterating over query results
3. File System Navigation: Traversing directory trees
4. Tree Structures: Different traversal orders (pre-order, in-order, post-order)
5. Graph Algorithms: Breadth-first and depth-first traversal
6. Filtered Iteration: Iterating over filtered subsets
7. Lazy Evaluation: Generating elements on-demand
8. Parallel Iteration: Iterating over collections in parallel

Benefits:

• Supports multiple traversal algorithms for the same collection
• Simplifies collection interfaces
• Allows multiple iterators to traverse the same collection simultaneously
• Follows Single Responsibility Principle—separates traversal logic
• Follows Open/Closed Principle—easy to add new iterators

When to Use:

• You need to traverse complex data structures
• You want to hide collection implementation details
• You need multiple traversal algorithms
• You want to provide a uniform interface for different collections
• You need to support lazy evaluation

C# Implementation Notes:

• C# provides IEnumerable<T> and IEnumerator<T> interfaces
• Use yield return for simple iterator implementation
• foreach loop uses iterators automatically
• LINQ operations work with iterators

Key Insight: The Iterator pattern separates the traversal logic from the collection. This allows you to change how you traverse a collection without changing the collection itself, and enables multiple traversal algorithms for the same data structure.