Iterator Pattern: Traversing Collections Without Exposing Structure

Iterator Pattern

"Provide a way to access the elements of an aggregate object sequentially without exposing its underlying representation." Any time client code needs to walk through "all the items in this collection," it has two choices: reach into the collection's internals directly (an array index, a linked-list node chain, a tree traversal), or ask the collection for a small object whose only job is producing elements one at a time. The Iterator pattern is the second choice — and it's so fundamental that most languages, Java included, bake it into the type system (Iterable, Iterator, the enhanced for loop).

This is one of three patterns covered together in this phase for collection-shaped problems — see also Memento Pattern (capturing state to restore later) and Visitor Pattern (running new operations over a structure's elements).

1. The Problem: Exposing Internal Structure to Traverse It

// VIOLATION: PlaylistLibrary exposes its internal array so callers can loop over it
class PlaylistLibrary {
    private Song[] songs;
    private int count;
 
    // Client is forced to know it's array-backed, know the current count,
    // and iterate correctly (off-by-one errors are the client's problem now)
    Song[] getSongsArray() { return songs; }
    int getCount() { return count; }
}
 
void printAllSongs(PlaylistLibrary library) {
    Song[] raw = library.getSongsArray();
    for (int i = 0; i < library.getCount(); i++) {
        System.out.println(raw[i].getTitle());
    }
}

The moment PlaylistLibrary needs to change its internal representation — say, from an array to a LinkedList for cheaper insertions, or to a lazily-loaded paginated source backed by a database — every piece of client code written against getSongsArray() breaks. The collection's storage decision has leaked into every consumer.

2. Structure

• Iterator — an interface with hasNext() and next() (Java's built-in java.util.Iterator<T>).
• Concrete Iterator — knows how to walk one specific collection's internal structure, and holds the traversal position (a cursor) so multiple iterators over the same collection can run independently.
• Aggregate (Iterable<T>) — an interface with a single iterator() factory method.
• Concrete Aggregate — the actual collection, which knows what it stores but delegates how to traverse it to the iterator it produces.

The key structural insight: the cursor position lives in the iterator, not the collection. That's what lets two threads (or two nested loops) traverse the same collection independently without stepping on each other's position.

3. Full Java Implementation

class Song {
    private final String title;
    Song(String title) { this.title = title; }
    String getTitle() { return title; }
}
 
// Concrete Aggregate — implements Iterable, keeps its storage private
class PlaylistLibrary implements Iterable<Song> {
    private Song[] songs = new Song[10];
    private int count = 0;
 
    void add(Song song) {
        if (count == songs.length) {
            songs = Arrays.copyOf(songs, songs.length * 2); // internal detail, hidden
        }
        songs[count++] = song;
    }
 
    @Override
    public Iterator<Song> iterator() {
        return new PlaylistIterator();
    }
 
    // Concrete Iterator — inner class so it can read the library's private array
    // without exposing that array through a public getter.
    private class PlaylistIterator implements Iterator<Song> {
        private int cursor = 0;
 
        @Override
        public boolean hasNext() {
            return cursor < count;
        }
 
        @Override
        public Song next() {
            if (!hasNext()) throw new NoSuchElementException();
            return songs[cursor++];
        }
    }
}

// Usage — client code never learns it's array-backed
PlaylistLibrary library = new PlaylistLibrary();
library.add(new Song("Clair de Lune"));
library.add(new Song("Take Five"));
library.add(new Song("So What"));
 
// Enhanced for-loop works because PlaylistLibrary implements Iterable<Song> —
// this is the Iterator pattern, syntactic sugar and all.
for (Song song : library) {
    System.out.println(song.getTitle());
}
 
// Two independent iterators over the same library, at different cursor positions:
Iterator<Song> a = library.iterator();
Iterator<Song> b = library.iterator();
a.next(); a.next(); // a is now at index 2
b.next();            // b is still only at index 1 — cursors don't interfere

Switching PlaylistLibrary's backing storage from an array to a LinkedList<Song> tomorrow requires editing exactly one class — PlaylistIterator's cursor logic — and zero changes to any client code that iterates with a for loop.

4. Fail-Fast vs. Fail-Safe Iterators

A critical, frequently-tested detail: what happens if the collection is modified while being iterated?

Fail-fast iterators (Java's ArrayList, HashMap, most java.util.* collections) detect concurrent structural modification and throw ConcurrentModificationException immediately, via a modCount field checked on every next() call. They fail loudly and immediately rather than risk returning inconsistent or corrupted results.

// Fail-fast: throws ConcurrentModificationException
List<String> names = new ArrayList<>(List.of("Alice", "Bob", "Carol"));
for (String name : names) {
    if (name.equals("Bob")) {
        names.remove(name); // structural modification during iteration
    }
} // ConcurrentModificationException thrown on the next hasNext()/next() call

Fail-safe iterators (CopyOnWriteArrayList, ConcurrentHashMap's iterator) instead iterate over a snapshot of the collection taken at iterator-creation time (or tolerate concurrent changes without throwing). They never throw ConcurrentModificationException, but the trade-off is that the iterator may not reflect modifications made after it was created — you might miss an addition or still see a since-removed element.

Iterator<String> it = names.iterator();
while (it.hasNext()) {
    if (it.next().equals("Bob")) {
        it.remove(); // safe — the iterator updates its own modCount tracking
    }
}

5. A Harder Case: Iterating a Tree In-Order

Arrays and linked lists have one obvious traversal order. Trees don't — and this is where Iterator earns its keep, because the traversal algorithm itself is nontrivial and shouldn't be reimplemented by every caller.

class BinarySearchTree<T extends Comparable<T>> implements Iterable<T> {
    private Node<T> root;
 
    private static class Node<T> {
        T value;
        Node<T> left, right;
        Node(T value) { this.value = value; }
    }
 
    void insert(T value) { root = insert(root, value); }
 
    private Node<T> insert(Node<T> node, T value) {
        if (node == null) return new Node<>(value);
        if (value.compareTo(node.value) < 0) node.left = insert(node.left, value);
        else node.right = insert(node.right, value);
        return node;
    }
 
    @Override
    public Iterator<T> iterator() {
        return new InOrderIterator();
    }
 
    // Encapsulates the entire in-order-traversal algorithm — including the
    // fact that it's implemented with an explicit stack rather than recursion,
    // since Iterator.next() must return one element at a time, not all at once.
    private class InOrderIterator implements Iterator<T> {
        private final Deque<Node<T>> stack = new ArrayDeque<>();
 
        InOrderIterator() {
            pushLeftSpine(root);
        }
 
        private void pushLeftSpine(Node<T> node) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
        }
 
        @Override
        public boolean hasNext() {
            return !stack.isEmpty();
        }
 
        @Override
        public T next() {
            if (!hasNext()) throw new NoSuchElementException();
            Node<T> node = stack.pop();
            pushLeftSpine(node.right);
            return node.value;
        }
    }
}

BinarySearchTree<Integer> tree = new BinarySearchTree<>();
for (int n : new int[]{5, 3, 8, 1, 4, 7, 9}) tree.insert(n);
 
for (int value : tree) {
    System.out.print(value + " "); // prints in sorted order: 1 3 4 5 7 8 9
}

Client code never learns the tree is a binary search tree, never sees a Node, and never implements the left-root-right traversal logic itself. A PreOrderIterator or PostOrderIterator could be added later as an alternative iterator()-returning method (e.g. preOrderIterator()) without touching BinarySearchTree's insertion logic or the existing InOrderIterator at all.

6. Iterator and Java Streams / Spliterator

Java 8's Stream API is built on top of Spliterator (a "splittable iterator"), which extends the same core idea — sequential access without exposing structure — with two additions relevant to modern backend code:

• tryAdvance() plays the role of a combined hasNext() + next(), processing one element and returning whether there was one, which suits lambda-based, functional-style consumption better than a two-method interface.
• trySplit() lets a Spliterator divide itself into two Spliterators covering disjoint sub-ranges — the extension that makes parallelStream() possible. A plain Iterator has no notion of splitting; Spliterator was introduced specifically so collections could support parallel traversal while keeping the same "don't expose internal structure" guarantee.

// Every Iterable already gets a default Spliterator via Iterable.spliterator(),
// built automatically on top of the Iterable's own iterator() — so implementing
// Iterator (as BinarySearchTree does above) already makes a class Stream-compatible:
Stream<Integer> stream = StreamSupport.stream(tree.spliterator(), false);
long countAboveFour = stream.filter(n -> n > 4).count();

7. Common Pitfalls

8. When to Use vs. When It's Overkill

9. Iterator, Memento, and Visitor at a Glance

These three patterns often show up in the same "traversal-adjacent" interview cluster because they all operate on structures of elements, but they answer different questions:

10. Real-World Examples

• java.util.Iterator / Iterable — the pattern is a first-class language feature; every enhanced for loop over a List, Set, or custom class implementing Iterable<T> is the Iterator pattern in disguise.
• java.sql.ResultSet — a database cursor is an Iterator over rows that may not all be loaded into memory at once; next() fetches lazily.
• JDBC/Spring Data Stream<T> query results — a Stream returned from a repository method that hasn't materialized a full List is Iterator applied to lazy, potentially unbounded data.
• Pagination APIs — a PageIterator wrapping "fetch next page" HTTP calls behind hasNext()/next() hides network pagination details from the caller entirely.
• Tree/AST traversal — compilers and parsers expose PreOrderIterator, PostOrderIterator variants over the same tree structure so callers can choose traversal order without knowing the tree's internal node representation.

Interview Questions

• What problem does the Iterator pattern solve that a plain getItemsAsList() getter doesn't?
• Where does the traversal cursor (current position) live, and why does that matter for supporting multiple concurrent iterations over the same collection?
• Explain the difference between fail-fast and fail-safe iterators. Give a concrete example of when each would be the right choice in production code.
• Why does Java's fail-fast ConcurrentModificationException explicitly say it shouldn't be relied on for correctness? What should you rely on instead?
• How would you safely remove elements from a List while iterating over it, without triggering ConcurrentModificationException?
• How does Iterable/Iterator in Java relate to the Iterator design pattern conceptually? Is the enhanced for loop "cheating," or is it exactly the pattern?
• How might a Visitor pattern implementation use an Iterator internally when traversing a tree structure?
• Design an iterator over a paginated REST API that lazily fetches the next page only when hasNext()/next() requires it. What state does your iterator need to hold?