The **iterator [design pattern](https://www.educative.io/answers/design-patterns-in-java)** is mainly used to separate a data structure from their iteration or traversal. Instead of writing the traversal code inside the data structure's class (e.g., [ArrayList](https://www.educative.io/answers/what-is-an-arraylist-in-java), [HashMap](https://www.educative.io/blog/what-is-a-hashmap-in-java), etc.), a new hierarchy of iterators is created and then connected to the hierarchy of data structures.

# Parts of the pattern

1. The **Container hierarchy** contains the data structures. While the abstract parent class (or [interface](https://www.educative.io/answers/what-is-a-java-interface)) has the abstract method `getIterator()`, each concrete child class provides its own implementation of `getIterator()` and returns the appropriate iterator. This is an example of the factory design pattern.

2. The **Iterator hierarchy** contains an abstract parent class (or interface) ​similar to the *container hierarchy*, which declares the most common traversal methods (like `hasNext()`, `next()`, `currentItem()`, etc.).​ These methods are implemented by each concrete child class.

# UML diagram

# Implementation

In the code below, a class for `LinkedList` has been implemented. This class can only add elements in the list and can *not* remove them since it is sufficient to demonstrate the traversal with an `Iterator` object.

#include <iostream>

using namespace std;

struct Node{
    Node* next;
    int value;
    Node(int i){
        next = nullptr;
        value = i;
    }
};

class Iterator;

// Abstract Container class:
class Container{
    // Abstract methods:
private:
    virtual Iterator* getIterator() = 0;
public:
    virtual Node* getHead() = 0;
};

// Abstract Iterator class:
class Iterator{
protected:
    int index;
    Node* ptr;
public:
    Iterator(Container* c){
        ptr = c->getHead();
    }
    
    // Abstract methods:
    virtual bool hasNext() = 0;
    virtual void next() = 0;
    virtual Node* currentItem() = 0;
};

// Concrete ListIterator:
class ListIterator: public Iterator{
public:
    ListIterator(Container* c):Iterator(c){}
    bool hasNext(){
        return ptr != nullptr;
    }
    void next(){
        if(hasNext()){
            ptr = ptr->next;
        }
        else{
            ptr = nullptr;
            cout << "Reached end of list." << endl;
        }
    }
    Node* currentItem(){
        return ptr;
    }
};

// Concrete LinkedList Container:
class LinkedList: public Container{
private:
    Node* head;
    int size;
public:
    LinkedList(){
        head = nullptr;
        size = 0;
    }
    void add(int i){
        if(head == nullptr){
            // Set the head when adding the first element:
            head = new Node(i);
        }
        else{
            Node* ptr = head;
            for(int i = 0; i < size - 1; i++)
                ptr = ptr->next;
        
            ptr->next = new Node(i);
        }
     
        // Increment size after adding the element:
        size++;
    }
    Iterator* getIterator(){
        // Return ListIterator:
        return new ListIterator(this);
    }
    Node* getHead(){
        return head;
    }
};

int main(){
    // Create a new list:
    LinkedList* list = new LinkedList();
    list->add(10);
    list->add(20);
    list->add(30);
    list->add(40);
    
    // Get iterator of the LinkedList:
    Iterator* i = list->getIterator();
    
    // Use the iterator to traverse the list:
    while(i->hasNext()){
        // Print value of current node:
        cout << i->currentItem()->value << endl;
        
        // Go to next node:
        i->next();
    }
    
    return 0;
}


What is the iterator design pattern?

Parts of the pattern

UML diagram

Implementation