Behavioral Pattern

Iterator Pattern

Walk the elements of a collection one at a time without exposing how the collection stores them — and run several walks over the same collection at once.

The Problem It Solves

A collection has two jobs that pull in opposite directions: store the elements, and let callers visit them. The moment a caller writes for (int i = 0; i < list.size(); i++), it has learned that the storage is indexable — and you can no longer swap the array for a linked list, a B-tree or a paged API without breaking every call site.

Iterator moves the traversal into a separate object that holds the cursor. The collection answers one question — give me something that walks you — and the caller never learns the shape underneath.

Because the cursor lives in the iterator rather than in the collection, two traversals can run at the same time without interfering. That is the part a currentIndex field on the collection itself cannot do, and it is usually the point of the interview question.

The Four Roles

Role	Responsibility	In the Java example
Iterator	Declares `hasNext()` / `next()`	`SongIterator`
Concrete Iterator	Holds the cursor and knows how to advance it	the anonymous classes
Aggregate	Declares a factory method for iterators	`Playlist`
Concrete Aggregate	Owns the storage, returns a matching iterator	`AlbumPlaylist`

Implementation

Three languages, three realistic shapes: two independent cursors over one array, a lazily paged API, and a tree walked three different ways.

// Iterator Pattern — Playlist with shuffle and in-order traversal

import java.util.*;

// ─── Iterator interface ───────────────────────────────────────
interface SongIterator {
    boolean hasNext();
    Song next();
}

class Song {
    final String title;
    Song(String title) { this.title = title; }
}

// ─── Aggregate interface ──────────────────────────────────────
interface Playlist {
    SongIterator iterator();      // in-order
    SongIterator shuffleIterator(); // a second, independent traversal
}

// ─── Concrete Aggregate ───────────────────────────────────────
class AlbumPlaylist implements Playlist {
    // The storage is private on purpose: callers never learn it is an array.
    private final Song[] songs;
    private int size = 0;

    AlbumPlaylist(int capacity) { this.songs = new Song[capacity]; }

    void add(Song s) { songs[size++] = s; }

    public SongIterator iterator() {
        return new SongIterator() {
            private int cursor = 0;
            public boolean hasNext() { return cursor < size; }
            public Song next() {
                if (!hasNext()) throw new NoSuchElementException();
                return songs[cursor++];
            }
        };
    }

    public SongIterator shuffleIterator() {
        List<Integer> order = new ArrayList<>();
        for (int i = 0; i < size; i++) order.add(i);
        Collections.shuffle(order);

        return new SongIterator() {
            private int cursor = 0;
            public boolean hasNext() { return cursor < order.size(); }
            public Song next() {
                if (!hasNext()) throw new NoSuchElementException();
                return songs[order.get(cursor++)];
            }
        };
    }
}

// ─── Client ───────────────────────────────────────────────────
public class App {
    public static void main(String[] args) {
        AlbumPlaylist album = new AlbumPlaylist(3);
        album.add(new Song("Kun Faya Kun"));
        album.add(new Song("Nadaan Parinde"));
        album.add(new Song("Phir Se Ud Chala"));

        // Two traversals running at once, each with its own cursor.
        SongIterator inOrder = album.iterator();
        SongIterator shuffled = album.shuffleIterator();

        while (inOrder.hasNext()) System.out.println("[play]    " + inOrder.next().title);
        while (shuffled.hasNext()) System.out.println("[shuffle] " + shuffled.next().title);
    }
}

Internal vs External Iterators

Feature	External	Internal
Who drives	The caller, via `next()`	The collection, via a callback
Example	`Iterator`, `for...of`	`forEach`, `map`
Early exit	Just stop calling `next()`	Needs a sentinel or an exception
Two at once	Yes — each has its own cursor	Not directly

When to Use

Hiding the storage

The collection is a tree, a ring buffer or a sharded map, and callers should not have to care which.

Several traversal orders

In-order, pre-order and level-order over one tree, each as its own iterator rather than three methods returning lists.

Lazy or infinite sequences

Paged API results, a log file larger than memory, or a generated stream — the next element is produced only when asked for.

Skip it when

A plain list and a for loop do the job. Wrapping an ArrayList in a hand-written iterator buys nothing.

In the Interview

Design a BST iterator with O(1) average next() and O(h) memory. The classic follow-up. Keep an explicit stack of left-spine nodes instead of flattening the tree into a list, which would cost O(n) memory up front.
What happens if the collection changes mid-traversal? Java's answer is fail-fast: the iterator compares a modCount it captured at creation and throws ConcurrentModificationException. The alternative is a snapshot iterator, which never throws but can serve stale elements.
Why not just return the internal list? Because the caller can then mutate it, and because every call site is now coupled to that exact type.
Where have you used it? Flatten a nested iterator, build a peeking iterator, or merge k sorted streams — all three are Iterator questions wearing a DSA costume.

What's Next?

Continue with other Behavioral patterns:

Or put it to work: solve Binary Search Tree Iterator · take an LLD mock interview