What problem does the Iterator design pattern solve, and what does "without exposing the underlying representation" mean in its intent?
answer
- sequential access, representation hidden
- aggregate hands out a cursor
- hasNext / next — one protocol, many structures
- traversal state lives outside the collection
- createIterator() is a factory method
basics
~20 sIterator gives a standard way to walk a collection's elements one at a time. The collection hands you a small cursor object with "is there more?" and "give me the next one" operations, so you never touch its internal array, nodes, or indexes.
solid answer
~50 sIterator's intent is: provide sequential access to the elements of an aggregate object without exposing its underlying representation. Two participants matter: the aggregate (the collection) and the iterator (a cursor holding the current position). Callers program against the iterator interface (`hasNext`/`next`, or `moveNext`/`current`), so identical loop code works over an array, a linked list, a hash table, a tree, or a lazily produced stream. Benefits: (1) encapsulation — internals such as bucket arrays or node links stay private and can be changed without breaking clients; (2) uniformity — one traversal protocol across many structures, which enables generic algorithms; (3) single responsibility — the collection stores, the iterator traverses; (4) multiplicity — several independent iterators can traverse the same collection at once, each with its own position, and one aggregate can expose several traversal orders (forward, reverse, in-order, level-order).
code
pseudocode · 13 linesinterface Iterator<T> { hasNext(): bool; next(): T }
class LinkedBag<T> {
private head: Node<T> // internals stay private
iterator(): Iterator<T> = object : Iterator<T> {
private var cur = head // position lives HERE, not in the bag
hasNext() = cur != null
next() = { val v = cur.value; cur = cur.next; v }
}
}
// One client loop works for LinkedBag, ArrayBag, TreeBag, FileLines...
fun printAll(it: Iterator<T>) { while (it.hasNext()) print(it.next()) }go deeper
State the intent in one sentence and give the hasNext/next protocol plus one concrete example (walking a list and a tree with the same loop).
Name the participants (aggregate, concrete iterator), explain why the concrete iterator is nested, and give at least two payoffs: change freedom and multiple simultaneous/alternative traversals.
Tie it to SRP and OCP, mention that iterators can be lazy/virtual (files, cursors, infinite sequences), and note the costs: allocation, loss of random access, hidden per-element cost.
Frame it as an API boundary decision — which traversal contract you publish (one-shot vs repeatable, ordered vs unordered, lazy vs materialized) constrains every consumer for years, and discuss when a bulk or push-based API is the better published contract.
## The problem Suppose you have three ways of storing a bag of items: - a **contiguous array** — elements sit next to each other, addressed by an integer index; - a **linked list** — each element holds a pointer to the next one, no indexes at all; - a **hash table** — elements are scattered across buckets, with gaps and possibly chains. If client code walks these directly, it must know each shape: `for i in 0..n-1 { a[i] }` for the array, `node = head; while node != null { node = node.next }` for the list, and a nested bucket-then-chain loop for the hash table. Two bad consequences follow. First, every client is **coupled to the internal representation** — the day you switch a list to a tree for performance, every loop in the codebase breaks. Second, the collection must **publish its internals** (the backing array, the head node) just so clients can walk it, which destroys encapsulation. ## The pattern The Gang of Four intent is literally: *"Provide a way to access the elements of an aggregate object sequentially without exposing its underlying representation."* Terms: - **Aggregate** (a.k.a. collection, container): the object that owns the elements. - **Iterator** (a.k.a. cursor, enumerator): a separate small object that knows *where you currently are* in a traversal and how to advance. Classic structure: - `Aggregate` declares `createIterator()`. - `Iterator` declares the traversal protocol. Common shapes: - **two-method**: `hasNext()` → boolean, `next()` → element (Java, many others); - **advance-then-read**: `moveNext()` → boolean, then read `current` (C#, C++ input iterators via `++` and `*`); - **sentinel-returning**: `next()` returns element-or-"done" marker (Python raises `StopIteration`, Go's `for range` uses a two-value form, Rust returns `Option<T>`). All three encode the same two capabilities: *is there another element?* and *give it to me and move on*. ``` interface Iterator<T> { hasNext(): bool; next(): T } interface Aggregate<T> { iterator(): Iterator<T> } function printAll(a: Aggregate<T>) { it = a.iterator() while (it.hasNext()) print(it.next()) } ``` `printAll` compiles once and works for every aggregate ever written. That is the payoff. ## What "without exposing the underlying representation" buys you 1. **Change freedom.** Swap an array for a skip list, add an index, re-shard a tree — clients that only see `hasNext/next` do not recompile or rewrite. This is the Open/Closed Principle applied to data structures. 2. **Invariant safety.** If clients had the backing array, they could write past the logical size, or mutate a key that a hash table uses for bucket placement, corrupting it. The iterator exposes only reads (plus, in some libraries, a *sanctioned* `remove()`). 3. **Traversal order becomes a first-class choice.** A tree can expose `inOrderIterator()`, `preOrderIterator()`, `levelOrderIterator()`. The structure is one thing; the walk is another. Same data, several iterators. 4. **Virtual sequences.** The "aggregate" need not hold elements at all. An iterator can produce lines from a file, rows from a database cursor, pages from an HTTP API, or the infinite sequence of Fibonacci numbers. Clients cannot tell the difference — sequential access is the whole contract. 5. **Single Responsibility Principle.** The collection's job is storage and invariants; iteration state (position, stack of visited nodes, current bucket) lives in the iterator. Keeping the cursor out of the collection is what makes concurrent, independent traversals possible. ## Participants and how implementations differ - **Concrete iterators are usually inner/nested classes** of the aggregate, so they can legally touch private fields while outsiders cannot. This is the standard resolution of the tension "hide internals, yet the iterator needs them." - **Iterators may be objects, functions, or language constructs.** A generator/coroutine (`yield`) is a compiler-generated iterator: the compiler turns your traversal function into a state machine holding the position. Conceptually identical, far less boilerplate. - **Robustness varies.** A *robust* iterator keeps working correctly when the aggregate changes underneath it; most real libraries do not promise that and instead detect and fail (see fail-fast semantics) or iterate a snapshot. ## Costs and when it is overkill - Extra object per traversal (allocation, indirection) — measurable only in ultra-hot loops; many runtimes escape-analyze it away. - For a plain array where random access matters (binary search, reverse walk, index arithmetic), an index is simpler and more capable; Iterator deliberately narrows you to sequential access. - Iterator exposes elements one at a time, which can hide the cost of the traversal (an innocuous loop over a remote sequence can issue N network calls). ## Related patterns - **Composite**: iterators are the standard way to flatten a recursive tree into a linear walk. - **Factory Method**: `createIterator()` is a factory method; the aggregate decides the concrete iterator class. - **Visitor**: use when you need type-specific behavior per element kind rather than uniform sequential access. - **Memento**: sometimes used so an iterator can capture aggregate state without breaking encapsulation.
- If the iterator must read the collection's private fields, hasn't encapsulation already been broken?No — the concrete iterator is normally a nested/inner class of the aggregate, so it is inside the encapsulation boundary and may touch private state, while the type published to clients is only the narrow `Iterator` interface. Encapsulation is about what *outsiders* can reach.
- Can one collection expose more than one iterator type?Yes, and that is a main benefit. A tree can offer in-order, pre-order and level-order iterators; a list can offer forward and reverse. The structure stays one class; each traversal policy is its own small iterator, added without modifying the collection's storage code.
- Does the aggregate have to actually contain the elements?No. The contract is only sequential access, so an iterator can generate values lazily — file lines, database cursor rows, API pages, or an infinite arithmetic sequence. Clients cannot distinguish stored from computed elements, which is precisely why the abstraction is powerful.
An iterator is a bookmark, not the book. The bookmark knows only "where I am" and "turn the page"; it never needs to know whether the pages are bound, on a scroll, or streamed to a screen — and you can put several bookmarks in the same book at once.
saying these in an interview costs you the question
- Saying Iterator's purpose is "to loop over arrays faster" — it is about decoupling and encapsulation, and it usually costs a little performance versus a raw index.
- Putting the current position inside the collection (a `next()` on the collection itself) — that allows only one traversal at a time and breaks nested or concurrent loops.
- Claiming you need Iterator only for lists; trees, graphs, hash tables, files and remote paginated sources benefit more.
- Confusing Iterator with Iterable/Aggregate: the iterable can be traversed many times, the iterator is one live position and is usually single-use.
- Assuming iteration order is always defined — for hash-based collections the order is unspecified and may change between versions or runs.