Iterator Design Pattern | System Design (LLD)

The Iterator Design Pattern is a behavioral design pattern that provides a standard mechanism to access elements of an aggregate object (like a Linked List, Binary Tree, Vector, or Custom Collection) sequentially without exposing its underlying structure or representation. By decoupling the traversal mechanism from the data structure itself, the system preserves core object-oriented design principles—specifically the Single Responsibility Principle (SRP) and the Open-Closed Principle (OCP).

1. The Traversal Problem in Aggregate Data Structures

In software engineering and Data Structures & Algorithms (DSA), applications frequently store and organize collections of data using distinct structural paradigms:

• Contiguous Arrays / Vectors: Traversed sequentially using integer index offsets (e.g., for(int i = 0; i < n; i++)).
• Singly / Doubly Linked Lists: Traversed via pointer traversal from the head node down through next node references (while(temp != nullptr) temp = temp->next;).
• Binary Search Trees / Hierarchical Graphs: Traversed via recursive or iterative depth-first strategies (In-Order, Pre-Order, Post-Order) or breadth-first strategies (Level-Order using Queues).
• Hash Maps / Key-Value Stores: Traversed using bucket entries, keysets, or internal hash table iterators.

The Inherent Problem

If a client component or a domain class needs to traverse a collection, embedding structure-specific loop logic inside the domain class forces that class to know the intimate internal details of how data is stored. If the underlying data structure ever changes (e.g., switching a playlist storage from std::vector to a doubly linked list), every single method handling traversal breaks and requires manual updates.

2. Real-World Analogy & Mental Model: The Music Playlist

Real-Life Analogy

Consider a Music Player Application containing a Playlist class that manages a collection of Song objects.

The core responsibilities of a Playlist domain object are managing business operations on songs:

• Adding a new song to the playlist.
• Removing an existing song.
• Fetching song attributes (Title, Artist, Duration).

However, methods like play_all_songs() or find_song_by_name() require traversing the internal collection of songs.

3. Naive Approach vs. Decoupled Iteration

The Naive Implementation

If the Playlist stores songs internally inside a std::vector<Song>, the developer might write direct vector indexing loops inside play_all_songs():

// Naive approach directly exposing internal storage structure
void play_all_songs() {
    for (size_t i = 0; i < songs.size(); ++i) {
        audio_engine.play(songs[i]);
    }
}

Why the Naive Approach Fails in Production

1. Violation of Single Responsibility Principle (SRP): The Playlist class now carries two distinct responsibilities: managing song domain logic and controlling execution mechanics for collection traversal.
2. Violation of Open-Closed Principle (OCP): If performance requirements dictate changing internal storage from std::vector<Song> to a custom LinkedList<Song> (to achieve $O(1)$ song removals), songs[i] indexing fails. You are forced to enter the class and rewrite play_all_songs(), find_song_by_name(), and every other search function to use pointer-based temp = temp->next loops.

The Iterator Solution

Instead of forcing the domain class to handle traversal, delegate iteration to an independent helper object called an Iterator. The domain class simply provides a standard method—get_iterator()—which returns an iterator configured to step through its elements safely.

4. Architectural Components of the Iterator Pattern

The Iterator Design Pattern separates the system into four primary roles:

1. Iterator<T> (Abstract Interface): Declares the contract for accessing and stepping through elements (has_next(), next()).
2. ConcreteIterator<T>: Implements the Iterator interface for a specific data structure (e.g., LinkedListIterator, BinaryTreeInOrderIterator, PlaylistIterator). Keeps track of the current traversal position.
3. Iterable<T> (Abstract Aggregate Interface): Declares a factory method contract (get_iterator()) returning an Iterator<T>.
4. ConcreteIterable<T>: Implements get_iterator(), instantiating and returning the appropriate ConcreteIterator initialized with its current state.

5. Visualizing Execution Flow

Below is the clean vertical execution sequence when a client requests sequential processing over an aggregate collection:

6. Step-by-Step C++ Implementation

Here is a production-grade, generic C++ implementation demonstrating the Iterator Pattern applied across three distinct collection structures: a Linked List, a Binary Tree (In-Order Traversal), and a Song Playlist.

Step 1: Base Interfaces (Iterator and Iterable)

#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <memory>

// Forward declaration of Iterator interface
template <typename T>
class Iterator {
public:
    virtual ~Iterator() = default;
    virtual bool has_next() = 0;
    virtual T next() = 0;
};

// Forward declaration of Iterable interface
template <typename T>
class Iterable {
public:
    virtual ~Iterable() = default;
    virtual std::unique_ptr<Iterator<T>> get_iterator() = 0;
};

Step 2: Linked List & Linked List Iterator

// 1. Linked List Node Structure
class ListNode {
public:
    int data;
    std::shared_ptr<ListNode> next;

    ListNode(int val) : data(val), next(nullptr) {}
};

// Forward declaration of LinkedListIterator
class LinkedListIterator;

// 2. Concrete Iterable: LinkedList
class LinkedList : class Iterable<int> {
public:
    std::shared_ptr<ListNode> head;

    LinkedList() : head(nullptr) {}

    void append(int val) {
        if (!head) {
            head = std::make_shared<ListNode>(val);
            return;
        }
        std::shared_ptr<ListNode> temp = head;
        while (temp->next) {
            temp = temp->next;
        }
        temp->next = std::make_shared<ListNode>(val);
    }

    std::unique_ptr<Iterator<int>> get_iterator() override;
};

// 3. Concrete Iterator: LinkedListIterator
class LinkedListIterator : public Iterator<int> {
private:
    std::shared_ptr<ListNode> current;

public:
    LinkedListIterator(std::shared_ptr<ListNode> head_node) : current(head_node) {}

    bool has_next() override {
        return current != nullptr;
    }

    int next() override {
        if (!has_next()) {
            throw std::out_of_range("No more elements in LinkedList");
        }
        int val = current->data;
        current = current->next;
        return val;
    }
};

// Deferred method definition for LinkedList
std::unique_ptr<Iterator<int>> LinkedList::get_iterator() {
    return std::make_unique<LinkedListIterator>(head);
}

Step 3: Binary Tree & In-Order Tree Iterator

Iterating over a Binary Tree in-order ($Left \rightarrow Root \rightarrow Right$) step-by-step requires controlled state management. Using an explicit stack inside BinaryTreeInOrderIterator enables controlled step-by-step traversal upon calling next().

// 1. Binary Tree Node Structure
class TreeNode {
public:
    int val;
    std::shared_ptr<TreeNode> left;
    std::shared_ptr<TreeNode> right;

    TreeNode(int data) : val(data), left(nullptr), right(nullptr) {}
};

class BinaryTreeInOrderIterator;

// 2. Concrete Iterable: BinaryTree
class BinaryTree : public Iterable<int> {
public:
    std::shared_ptr<TreeNode> root;

    BinaryTree(std::shared_ptr<TreeNode> root_node) : root(root_node) {}

    std::unique_ptr<Iterator<int>> get_iterator() override;
};

// 3. Concrete Iterator: BinaryTreeInOrderIterator
class BinaryTreeInOrderIterator : public Iterator<int> {
private:
    std::stack<std::shared_ptr<TreeNode>> node_stack;

    void push_all_left(std::shared_ptr<TreeNode> node) {
        while (node != nullptr) {
            node_stack.push(node);
            node = node->left;
        }
    }

public:
    BinaryTreeInOrderIterator(std::shared_ptr<TreeNode> root) {
        push_all_left(root);
    }

    bool has_next() override {
        return !node_stack.empty();
    }

    int next() override {
        if (!has_next()) {
            throw std::out_of_range("No more elements in BinaryTree");
        }
        std::shared_ptr<TreeNode> top_node = node_stack.top();
        node_stack.pop();
        
        int result = top_node->val;
        if (top_node->right) {
            push_all_left(top_node->right);
        }
        return result;
    }
};

// Deferred method definition for BinaryTree
std::unique_ptr<Iterator<int>> BinaryTree::get_iterator() {
    return std::make_unique<BinaryTreeInOrderIterator>(root);
}

Step 4: Domain Model: Song & Playlist Iterator

// 1. Domain Class: Song
class Song {
public:
    std::string title;
    std::string artist;

    Song(std::string t, std::string a) : title(t), artist(a) {}
};

class PlaylistIterator;

// 2. Concrete Iterable: Playlist
class Playlist : public Iterable<Song> {
private:
    std::vector<Song> songs;

public:
    void add_song(const Song& song) {
        songs.push_back(song);
    }

    const std::vector<Song>& get_songs() const {
        return songs;
    }

    std::unique_ptr<Iterator<Song>> get_iterator() override;
};

// 3. Concrete Iterator: PlaylistIterator
class PlaylistIterator : public Iterator<Song> {
private:
    const std::vector<Song>& song_list;
    size_t index;

public:
    PlaylistIterator(const std::vector<Song>& list) : song_list(list), index(0) {}

    bool has_next() override {
        return index < song_list.size();
    }

    Song next() override {
        if (!has_next()) {
            throw std::out_of_range("No more songs in Playlist");
        }
        return song_list[index++];
    }
};

// Deferred method definition for Playlist
std::unique_ptr<Iterator<Song>> Playlist::get_iterator() {
    return std::make_unique<PlaylistIterator>(songs);
}

7. Complete System Execution & Walkthrough

Below is a complete executable program consuming all three collections uniformly using the Iterator Pattern interface.

int main() {
    std::cout << "========================================" << std::endl;
    std::cout << " 1. TRAVERSING LINKED LIST VIA ITERATOR " << std::endl;
    std::cout << "========================================" << std::endl;
    
    LinkedList list;
    list.append(10);
    list.append(20);
    list.append(30);

    std::unique_ptr<Iterator<int>> list_it = list.get_iterator();
    while (list_it->has_next()) {
        std::cout << "LinkedList Node Value: " << list_it->next() << std::endl;
    }

    std::cout << "\n========================================" << std::endl;
    std::cout << " 2. TRAVERSING BINARY TREE (IN-ORDER)   " << std::endl;
    std::cout << "========================================" << std::endl;

    // Constructs BST:
    //      20
    //     /  \
    //    10   30
    auto root = std::make_shared<TreeNode>(20);
    root->left = std::make_shared<TreeNode>(10);
    root->right = std::make_shared<TreeNode>(30);

    BinaryTree tree(root);
    std::unique_ptr<Iterator<int>> tree_it = tree.get_iterator();
    while (tree_it->has_next()) {
        std::cout << "Tree Node Value (In-Order): " << tree_it->next() << std::endl;
    }

    std::cout << "\n========================================" << std::endl;
    std::cout << " 3. TRAVERSING PLAYLIST VIA ITERATOR    " << std::endl;
    std::cout << "========================================" << std::endl;

    Playlist my_playlist;
    my_playlist.add_song(Song("Admirin' You", "Karan Aujla"));
    my_playlist.add_song(Song("Husn", "Anuv Jain"));

    std::unique_ptr<Iterator<Song>> playlist_it = my_playlist.get_iterator();
    while (playlist_it->has_next()) {
        Song current_song = playlist_it->next();
        std::cout << "Playing Song: \"" << current_song.title 
                  << "\" by " << current_song.artist << std::endl;
    }

    return 0;
}

Execution Output

8. Tabular Synthesis: Direct Traversal vs. Iterator Pattern

9. Advanced Practical Edge Cases & Homework Challenge

Advanced Concept: Controlled State vs. Recursive Traversal

When implementing tree or graph iterators, beginners often try using recursion. However, standard recursive function calls run to completion and lock the thread stack, preventing step-by-step traversal control.

Key Rule: Iterators must maintain state incrementally. Each invocation of next() should evaluate exactly one step. To achieve this on non-linear data structures like trees, store state explicitly using data structures like std::stack or std::queue inside the Iterator class instance.

Practical Engineering Homework Challenge

Extend the base Iterator<T> interface to support Bidirectional Traversal (traversing both forward and backward through collections):

1. Update the Iterator<T> contract with two additional methods:
   • virtual bool has_previous() = 0;
   • virtual T previous() = 0;
2. Implement a DoublyLinkedListIterator or BidirectionalPlaylistIterator supporting backward traversal.
3. Refactoring Design Option: Decide whether to add has_previous() / previous() directly to Iterator<T> or create a derived BidirectionalIterator<T> : public Iterator<T> interface to avoid violating the Interface Segregation Principle (ISP) for forward-only data structures.

10. Summary and Key Takeaways

• Decoupling Core Logic: The Iterator pattern isolates traversal mechanics from collection storage, enforcing the Single Responsibility Principle.
• Uniform Interface: Provides a consistent access protocol (has_next(), next()) across completely different underlying data structures.
• Future-Proof Refactoring: Changing an internal storage format (e.g., swapping a std::vector for a LinkedList or std::map) requires updating only the collection's specific iterator, keeping all client processing logic intact.
• Stateful Isolation: Independent iterator instances allow multiple clients to traverse the same aggregate collection simultaneously without state collision.
• Language Integration: Standard language runtime facilities—including C++ STL iterators (std::vector<T>::iterator), Java java.util.Iterator, and Python generators/iterators—are built directly on the principles of this design pattern.