Iterator

Iterator separates how you walk a collection from how the collection stores its elements. It is so thoroughly absorbed into modern languages — for…of, generators, streams, IEnumerable — that most engineers use it dozens of times a day without naming it.

It is worth studying anyway, because two of its consequences show up constantly in production code: laziness, and what happens when the collection changes underneath you.

The problem it solves

Without it, every caller must know the storage:

// Array
for (let i = 0; i < list.length; i++) use(list[i]);

// Linked list
for (let node = head; node; node = node.next) use(node.value);

// Tree
walk(root, use);

Change the storage and every caller changes. With an iterator the caller says only "give me the next one", and the collection decides what that means.

classDiagram
    class Iterable {
        <<interface>>
        +iterator() Iterator
    }
    class Iterator {
        <<interface>>
        +next() Item
        +hasNext() bool
    }
    class TreeCollection {
        +iterator() Iterator
    }
    class DepthFirstIterator {
        -stack: Node[]
        +next() Item
        +hasNext() bool
    }
    Iterable <|.. TreeCollection
    Iterator <|.. DepthFirstIterator
    TreeCollection ..> DepthFirstIterator : creates

A collection may offer several iterators. A tree can hand out depth-first, breadth-first and leaves-only iterators — same data, different traversals, none of them the collection's own business to hard-code.

Laziness is the interesting part

An iterator does not have to have the elements yet. It only has to produce the next one when asked, which means it can represent a sequence that is expensive, infinite, or not fully known.

function* readLines(file) {
  let buffer = '';
  for (const chunk of file.chunks()) {
    buffer += chunk;
    let i;
    while ((i = buffer.indexOf('\n')) >= 0) {
      yield buffer.slice(0, i);
      buffer = buffer.slice(i + 1);
    }
  }
  if (buffer) yield buffer;
}

for (const line of readLines(hugeFile)) {
  if (line.includes('ERROR')) { console.log(line); break; }
}

A 40 GB file is never in memory, and the loop stops reading as soon as it finds what it wanted. The eager version — read all lines into an array, then filter — is a different program with a different memory profile, and the two look nearly identical in source.

That is the practical payoff: laziness composes. filter, map and take over a lazy sequence do one pass and stop early; over eager collections they build an intermediate array at every step.

The invalidation trap

Modifying a collection while iterating it is the pattern's classic bug, and the behaviours differ dangerously between languages.

for (const item of items) {
  if (item.expired) items.splice(items.indexOf(item), 1);   // skips elements
}

Removing an element shifts everything after it down, so the iterator's next position skips one. The loop appears to work — it removes some expired items — which is far worse than crashing, because the bug is silent and data-dependent.

Three defensible approaches:

• Fail fast. Detect modification and throw. Loud, immediate, and it is what several standard libraries do.
• Iterate a snapshot. Copy first, then mutate the original. Simple and correct; costs a copy.
• Build a new collection. items = items.filter(i => !i.expired). Usually the clearest, and it sidesteps the question entirely.

Silently skipping is the only unacceptable outcome, and it is what the naive code above does.

Pagination is Iterator over a network

An API returning a page and a cursor is exactly this pattern with a network between next() calls, and it inherits every consideration above plus a few of its own.

• Laziness is mandatory. Nobody materialises ten million rows.
• The underlying data changes between pages. Offset-based pagination will skip or duplicate rows when items are inserted or deleted mid-traversal — the invalidation trap, distributed. Cursor-based pagination over a stable sort key is the fix.
• The iterator holds server state or does not. A cursor encoding a position is stateless and survives restarts; a server-side cursor is more powerful and must be expired.
• Cleanup has no guarantee. A client that stops paging never tells you, so any server-side resource needs a timeout.

When you would write one by hand

Almost never for ordinary collections — the language's own facilities are better. The cases that remain:

• A custom traversal order over a structure you own, especially a tree with several meaningful orders.
• An expensive or remote sequence you want to expose as an ordinary loop: paginated API results, database cursors, streamed files.
• An infinite or generated sequence — retry backoff intervals, identifiers, simulation steps.
• Hiding a composite structure, so callers walk a tree of nested collections as one flat sequence.

Check your understanding

Common mistakes

Mutating a collection while iterating it. The silent-skip variant is the dangerous one.

Letting a lazy sequence escape the scope owning its resource. The file handle or connection stays open until something disposes it.

Breaking out of a lazy loop without cleanup. Early termination is the point; leaking the resource is not.

Offset pagination over changing data. Rows are skipped and duplicated, and the report is quietly wrong.

Writing an iterator where the language has one. Generators and built-in protocols are better in every respect.

Iterators that expose internal nodes. Yielding a linked-list node rather than its value re-couples callers to the storage the pattern was hiding.

Assuming an iterator is restartable. Most are single-pass, and passing one to two consumers gives the second an empty sequence.

Practice

items = items.filter((i) => !i.expired);

Key takeaways

• Iterator separates traversal from storage, so callers do not depend on how a collection holds its elements, and one collection can offer several orders.
• Laziness is the interesting consequence: bounded memory, infinite sequences, genuine early termination, and one-pass composition of map/filter/take.
• A lazy sequence holds resources open. Do not let it escape the scope that owns them, and honour the disposal path on early exit.
• Never mutate a collection while iterating it. Silently skipping elements is the worst outcome and the most likely one.
• Build a new collection instead — correct by construction, and the allocation almost never matters.
• Pagination is Iterator over a network, and offset-based paging inherits the invalidation trap. Use cursors over a stable sort key.
• A paginated iterator must throw rather than end silently when a page fails, or partial results look like complete ones.

Further reading

• Erich Gamma, Richard Helm, Ralph Johnson and John Vlissides, Design Patterns: Elements of Reusable Object-Oriented Software (Addison-Wesley, 1994).
• Barbara Liskov and John Guttag, Program Development in Java (Addison-Wesley, 2000) — iteration abstractions and their specifications.
• Joshua Bloch, Effective Java, third edition (Addison-Wesley, 2018) — the for-each loop and concurrent modification.
• Martin Fowler, Patterns of Enterprise Application Architecture (Addison-Wesley, 2002).
• Philip Wadler, "Deforestation: Transforming Programs to Eliminate Trees" (Theoretical Computer Science, 1990) — why lazy composition avoids intermediate collections.