Iterator Pattern

The Iterator pattern moves the traversal state — a cursor position into a collection — out of the collection and into a separate, short-lived object, so client code walks elements through a fixed hasNext()/next() contract while the collection keeps its internal layout (array, linked list, tree, hash buckets) completely private.

The pattern has four roles. The Iterator interface declares the traversal protocol (hasNext(), next()). A ConcreteIterator holds a reference to one collection plus its own cursor (e.g. an integer index) and knows how to advance it. The Aggregate interface declares createIterator(). A ConcreteAggregate (the collection) implements it by handing back a fresh iterator bound to itself. The key consequence: because the cursor lives in the iterator, you can have several independent walks over the same collection at once, and the collection class never grows traversal methods.

Traced walk over a real collection

Build collection = ["Dune", "Sapiens", "Hyperion"], then run the while (it.hasNext()) print(it.next()) loop. The iterator's only state is cursor, starting at 0. hasNext() tests cursor < size (size = 3); next() reads array[cursor] then post-increments.

The client never touched array, never wrote an index, never called size(). Swap BookCollection for a tree-backed collection and the loop is byte-for-byte identical — only the ConcreteIterator's next() changes.

External vs internal iterators

There are two ways to drive the cursor, and the grader was right that the original page never named them:

• External (active) iterator — the client pulls: it owns the loop and decides when to call next(). This is the classic GoF form shown above (and Java's java.util.Iterator). You get full control: pause, peek, run two collections in lockstep, break early.
• Internal (passive) iterator — the collection pushes: you hand it a function and it drives the walk, calling you back for each element. This is List.forEach(action), Ruby's each, or a Stream. Less control, but no off-by-one risk and no exposed cursor.

A useful test: if you ever need to advance two sequences in step (merge two sorted lists), you need external iterators — an internal forEach can't pause one walk while it advances the other.

The fail-fast mechanism (what was missing)

The original page listed "iterator invalidation" and "concurrent modification" as cons but never explained how a real iterator detects them. The standard technique is a modification counter. The collection keeps an integer modCount that it increments on every structural change (add/remove). When you create an iterator, it snapshots that value as expectedModCount. On every next(), the iterator re-checks: if collection.modCount != expectedModCount, something mutated the collection mid-walk and the cursor may now point at the wrong slot or past the end — so it throws ConcurrentModificationException immediately rather than silently skipping or duplicating an element. "Fail-fast" means it fails loudly at the next access, not later as corrupted output.

Reference implementation (Java)

This is the page's existing code, kept because it is correct — note the iterator is a private inner class so only createIterator() can hand one out, and the cursor lives in the iterator, not the collection.

import java.util.ArrayList;
import java.util.List;

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

interface Iterator {
    boolean hasNext();
    Book next();
}

class BookCollection {
    private final List<Book> books = new ArrayList<>();

    void addBook(Book book) { books.add(book); }
    int size()             { return books.size(); }
    Book get(int i)        { return books.get(i); }

    Iterator createIterator() { return new BookIterator(); }

    // Private inner class: cursor state is encapsulated here, not in the list.
    private class BookIterator implements Iterator {
        private int cursor = 0;
        public boolean hasNext() { return cursor < size(); }
        public Book next()       { return hasNext() ? get(cursor++) : null; }
    }
}

public class Solution {
    public static void main(String[] args) {
        BookCollection c = new BookCollection();
        c.addBook(new Book("Dune"));
        c.addBook(new Book("Sapiens"));
        c.addBook(new Book("Hyperion"));
        Iterator it = c.createIterator();
        while (it.hasNext()) System.out.println(it.next().title);
    }
}

The same shape in Go

Go has no generics-free Iterator interface in the stdlib idiom historically, so the cursor-in-a-struct form is explicit and reads cleanly. (Go 1.23+ also offers range-over-func, the internal-iterator form.)

package main

import "fmt"

type Book struct{ Title string }

type BookCollection struct{ books []Book }

func (c *BookCollection) Add(b Book) { c.books = append(c.books, b) }

// Iterator carries its own cursor, bound to one collection.
type BookIterator struct {
    c      *BookCollection
    cursor int
}

func (c *BookCollection) Iterator() *BookIterator { return &BookIterator{c: c} }

func (it *BookIterator) HasNext() bool { return it.cursor < len(it.c.books) }

func (it *BookIterator) Next() Book {
    b := it.c.books[it.cursor]
    it.cursor++
    return b
}

func main() {
    c := &BookCollection{}
    c.Add(Book{"Dune"})
    c.Add(Book{"Sapiens"})
    c.Add(Book{"Hyperion"})
    for it := c.Iterator(); it.HasNext(); {
        fmt.Println(it.Next().Title)
    }
}

Why a naive Go version is wrong: if you make Iterator() return the iterator by value and then call HasNext()/Next() on copies (value receivers), each call mutates a copy and cursor never advances — an infinite loop. The cursor must live behind a pointer receiver so all calls share one struct.

Pitfalls

• Mutating the collection mid-walk. for (Book b : books) if (b.title.equals("Sapiens")) books.remove(b); throws ConcurrentModificationException via the modCount check above. The fix is to remove through the iterator (it.remove()), which updates expectedModCount in lockstep, or to collect-then-remove after the loop.
• Snapshot vs live semantics. Fail-fast iterators are not a thread-safety guarantee — they are a best-effort bug detector. For genuine concurrency use a copy-on-write or weakly-consistent collection (e.g. CopyOnWriteArrayList, ConcurrentHashMap), whose iterators traverse a snapshot and never throw, but may miss the very latest writes.
• Single-use iterators. Most iterators are forward-only and exhausted after one pass; calling next() past the end returns null (this page's version) or throws NoSuchElementException (Java's). Returning null silently is a footgun — prefer throwing so a logic bug surfaces immediately.
• Cursor invalidation by index shift. Even within a single thread, removing element i from an array-backed collection shifts everything after it down one slot; an index-based cursor then skips the next element. This is exactly why modification during traversal must be funnelled through the iterator.
• Leaking the backing store. If next() returns a reference into a mutable internal array, callers can mutate the collection's storage through it. Return immutable elements or defensive copies when that matters.

When to use it — and when not to

Reach for an explicit Iterator when: the collection's internal structure is non-trivial (tree, graph, paged/lazy source) and you must hide it; you need multiple traversal orders (in-order, pre-order, filtered, reverse) over the same data; you want several independent simultaneous walks; or elements are produced lazily/streamed (DB cursor, file lines, network pages) and you must not materialise them all at once.

Trade-offs vs named alternatives:

• vs a plain index loop (for i in 0..n). The index loop is zero-overhead and obvious, but it hard-codes "this is an array with random access by position." It can't traverse a linked list or tree, breaks the moment the storage changes, and forces every caller to know the layout. Choose the iterator when the storage is hidden or non-indexable; keep the index loop for a small, private, array-backed list you fully own.
• vs an internal iterator / Stream / forEach. Streams give you composable map/filter/reduce and remove off-by-one and cursor-leak bugs entirely — at the cost of control (no early-pausing, no lockstep merge, harder step-through debugging) and some allocation/latency overhead. Choose the external Iterator when you need fine-grained control of the walk (merge two sorted streams, peek, resume); prefer a Stream/forEach for declarative bulk transforms where you just want "do X to each."
• vs exposing the collection directly (returning the internal List). Direct exposure is the cheapest but couples every caller to your representation and lets them mutate your innards. The iterator costs one extra class and a layer of indirection to buy that encapsulation.

Concrete decision: a paginated REST client returning users 100 at a time. An index loop is impossible (you don't have all users). A Stream works only if the language gives you lazy stream-from-pages plumbing. The natural fit is an external UserIterator whose hasNext() fetches the next page when the current buffer empties — the caller writes while (it.hasNext()) process(it.next()) and never knows pages exist. Choose the explicit iterator here; prefer a Stream only if you already have lazy-pagination support and don't need to pause mid-walk.

Takeaways

• The whole point is relocating cursor state from the collection into a separate object, so traversal is decoupled from representation and multiple independent walks are possible.
• External iterators (client pulls via next()) give control and enable lockstep merges; internal iterators (forEach/Stream, collection pushes) trade control for safety and brevity.
• Fail-fast is a modCount snapshot compared on every next() — a bug detector, not a concurrency mechanism. For real concurrency use weakly-consistent or copy-on-write collections.
• Skip it for a small private array you fully own; reach for it for hidden, non-indexable, or lazily-produced data.

Sources: Gamma, Helm, Johnson & Vlissides, Design Patterns: Elements of Reusable Object-Oriented Software (1994), Iterator chapter (external vs internal iterators, robust iterators). Java SE documentation for java.util.Iterator, Iterable.forEach, and the fail-fast / modCount contract of ArrayList and HashMap; java.util.concurrent weakly-consistent iterators (ConcurrentHashMap, CopyOnWriteArrayList). Go language spec, range-over-func (Go 1.23). Re-authored and deepened for this guide: added the external/internal iterator distinction, an explicit modCount fail-fast mechanism with a sequence diagram, a corrected Go implementation with a value-vs-pointer-receiver bug note, a traced walk, and a selection / trade-offs section.

Numeric fail-fast trace

Had the removal gone through it.remove(), the iterator would bump both modCount and expectedModCount together, so step 4 would pass.

Interview drills

Q1. Why separate the Iterator from the Collection?
Multiple simultaneous, independent traversals over one collection; the collection hides its structure; and client loops read identically across List, Set, and custom trees.

Q2. External vs internal iterator — the trade-off?
External (client pulls via next()) gives full control: pause, peek, break early, advance two sequences in lockstep. Internal (forEach/Stream, collection pushes) is simpler and removes off-by-one and cursor-leak bugs, but you lose that control and cannot pause one walk to advance another.

Q3. How does fail-fast actually work, and is it thread-safety?
Every structural change bumps modCount; the iterator snapshots it as expectedModCount and re-checks on each next(), throwing on mismatch. It is a best-effort bug detector, not a concurrency guarantee — for real concurrency use a weakly-consistent or copy-on-write collection.