InterviewKata
Design patterns · 20 of 26 · Objects talking

Iterator

An iterator lets code walk a collection one element at a time without knowing how it's stored. This page wraps Pedal's paged trips service in an iterable trip history, so screens write a plain loop and pages are fetched only as far as the loop goes.

1. The pain

A Pedal member can have hundreds of trips. The trips service returns them a page at a time, newest first. Three screens use them: this month's total minutes, "your longest ride", and a CSV export. Each screen wrote its own loop over pages: ask for page 0, loop over its trips, ask for page 1, stop when a page comes back short or empty.

The export's copy of the loop stopped one page early when the last page was full. The monthly total fetched every page even though it only needed the first two. And when the service switched from page numbers to "continue from this cursor", all three screens had to change.

2. The idea in one picture

A library's "next book, please" counter lets you work through a long reading list without seeing the stacks. The librarian fetches from the back room in trolley loads as you go; you just keep asking for the next one, and stop when you've found what you need. If the library reorganises its storage, your request doesn't change.

Iterator lets code walk a collection one element at a time without knowing how it's stored. TripHistory is iterable: screens write for trip in history. Behind that, its iterator fetches the next page only when the loop needs it, and stops at the end. If a screen stops early, no more pages are fetched.

Most languages build the pattern in. Python's for calls __iter__ and __next__, and a generator (yield) writes the iterator for you; TypeScript has Symbol.iterator and generators; Java has Iterable and Iterator. The pattern is still worth knowing by name, because you write your own when the storage is unusual: pages, cursors, trees, files.

3. The roles

RoleIts jobIn Pedal
IteratorGives the next element and says when there are no more.The generator inside TripHistory.__iter__; Java's anonymous Iterator<Trip>
Iterable (aggregate)Creates a fresh iterator for each loop.TripHistory
Underlying storageHowever the elements are really kept.TripApi.page(number, size)
ClientLoops without knowing about pages.The monthly-total, longest-ride and export screens

4. Before and after

The monthly total both ways (Python sketch; the full program is in section 5).

Without the pattern

def october_total(api):
    total, n = 0, 0
    while True:
        page = api.page(n, 3)
        if not page:
            break
        for t in page:
            if t.month != "October":
                return total
            total += t.minutes
        n += 1
    # copied, slightly differently,
    # into two other screens

With it

class TripHistory:
    def __iter__(self):
        n = 0
        while page := self.api.page(n, self.size):
            yield from page
            n += 1

total = 0
for t in TripHistory(api):
    if t.month != "October":
        break
    total += t.minutes
The next changeWithout the patternWith it
The service moves from page numbers to cursorsThree screens' loops changeOnly TripHistory.__iter__ changes
A new "rides over 30 minutes" screenA fourth copy of the paging loopA plain for loop or filter
Stop fetching when the answer is foundEach loop must remember toAutomatic: pages are fetched only as the loop asks

How elements are stored is the collection's business; how they're used is the caller's. The iterator is the line between them.

5. The code

TripHistory fetches pages from a fake trips service only as the loop needs them. The October total stops after two pages; finding the first long ride needs one; reading everything needs a final empty request to find the end.

from __future__ import annotations
from dataclasses import dataclass
from typing import Iterator

MINUTES = [14, 32, 8, 21, 40, 9, 12, 18, 25, 7, 30, 11]     # T-12 (newest) ... T-1 (oldest)


@dataclass
class Trip:
    trip_id: str
    month: str
    minutes: int


class TripApi:
    """Stands in for the trips service: returns one page at a time, newest first, and counts calls."""

    def __init__(self) -> None:
        self.trips = [Trip(f"T-{12 - i}", "October" if i < 4 else "September", m) for i, m in enumerate(MINUTES)]
        self.pages_fetched = 0

    def page(self, number: int, size: int) -> list[Trip]:
        self.pages_fetched += 1
        return self.trips[number * size:(number + 1) * size]


class TripHistory:
    """The iterable collection: callers loop over trips; pages are fetched only when the loop needs them."""

    def __init__(self, api: TripApi, page_size: int = 3) -> None:
        self.api, self.page_size = api, page_size

    def __iter__(self) -> Iterator[Trip]:
        number = 0
        while True:
            page = self.api.page(number, self.page_size)
            if not page:
                return
            yield from page
            if len(page) < self.page_size:
                return
            number += 1


if __name__ == "__main__":
    api = TripApi()
    october = []
    for trip in TripHistory(api):                 # newest first, so stop at the first older trip
        if trip.month != "October":
            break
        october.append(trip)
    print("October trips: " + ", ".join(f"{t.trip_id} ({t.minutes} min)" for t in october))
    print(f"October total: {sum(t.minutes for t in october)} min | pages fetched: {api.pages_fetched} of 4")

    api = TripApi()
    first_long = next(t for t in TripHistory(api) if t.minutes > 30)
    print(f"first trip over 30 minutes: {first_long.trip_id} | pages fetched: {api.pages_fetched}")

    api = TripApi()
    print(f"all trips: {sum(1 for _ in TripHistory(api))} | page requests: {api.pages_fetched} (the last comes back empty)")
const MINUTES = [14, 32, 8, 21, 40, 9, 12, 18, 25, 7, 30, 11];   // T-12 (newest) ... T-1 (oldest)

interface Trip { tripId: string; month: string; minutes: number; }

// Stands in for the trips service: returns one page at a time, newest first, and counts calls.
class TripApi {
  readonly trips: Trip[] = MINUTES.map((m, i) => ({ tripId: `T-${12 - i}`, month: i < 4 ? "October" : "September", minutes: m }));
  pagesFetched = 0;
  page(n: number, size: number): Trip[] { this.pagesFetched++; return this.trips.slice(n * size, (n + 1) * size); }
}

// The iterable collection: callers loop over trips; pages are fetched only when the loop needs them.
class TripHistory implements Iterable<Trip> {
  constructor(private readonly api: TripApi, private readonly pageSize = 3) {}
  *[Symbol.iterator](): Iterator<Trip> {
    for (let n = 0; ; n++) {
      const page = this.api.page(n, this.pageSize);
      if (!page.length) return;
      yield* page;
      if (page.length < this.pageSize) return;
    }
  }
}

let api = new TripApi();
const october: Trip[] = [];
for (const trip of new TripHistory(api)) {   // newest first, so stop at the first older trip
  if (trip.month !== "October") break;
  october.push(trip);
}
console.log("October trips: " + october.map((t) => `${t.tripId} (${t.minutes} min)`).join(", "));
console.log(`October total: ${october.reduce((s, t) => s + t.minutes, 0)} min | pages fetched: ${api.pagesFetched} of 4`);

api = new TripApi();
let firstLong: Trip | undefined;
for (const t of new TripHistory(api)) if (t.minutes > 30) { firstLong = t; break; }
console.log(`first trip over 30 minutes: ${firstLong!.tripId} | pages fetched: ${api.pagesFetched}`);

api = new TripApi();
let count = 0;
for (const _ of new TripHistory(api)) { void _; count++; }
console.log(`all trips: ${count} | page requests: ${api.pagesFetched} (the last comes back empty)`);
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

public class Main {
    static final int[] MINUTES = {14, 32, 8, 21, 40, 9, 12, 18, 25, 7, 30, 11};   // T-12 (newest) ... T-1 (oldest)

    record Trip(String tripId, String month, int minutes) {}

    // Stands in for the trips service: returns one page at a time, newest first, and counts calls.
    static class TripApi {
        final List<Trip> trips = new ArrayList<>();
        int pagesFetched;
        TripApi() { for (int i = 0; i < MINUTES.length; i++) trips.add(new Trip("T-" + (12 - i), i < 4 ? "October" : "September", MINUTES[i])); }
        List<Trip> page(int n, int size) {
            pagesFetched++;
            return trips.subList(Math.min(n * size, trips.size()), Math.min((n + 1) * size, trips.size()));
        }
    }

    // The iterable collection: callers loop over trips; pages are fetched only when the loop needs them.
    static class TripHistory implements Iterable<Trip> {
        private final TripApi api;
        private final int pageSize;
        TripHistory(TripApi api, int pageSize) { this.api = api; this.pageSize = pageSize; }

        public Iterator<Trip> iterator() {
            return new Iterator<>() {
                private int pageNumber = 0, index = 0;
                private List<Trip> page = null;
                private boolean done = false;

                public boolean hasNext() {
                    if (done) return false;
                    if (page == null || index == page.size()) {
                        if (page != null && page.size() < pageSize) { done = true; return false; }
                        page = api.page(pageNumber++, pageSize);
                        index = 0;
                        if (page.isEmpty()) { done = true; return false; }
                    }
                    return true;
                }

                public Trip next() {
                    if (!hasNext()) throw new NoSuchElementException();
                    return page.get(index++);
                }
            };
        }
    }

    public static void main(String[] args) {
        TripApi api = new TripApi();
        List<Trip> october = new ArrayList<>();
        for (Trip trip : new TripHistory(api, 3)) {   // newest first, so stop at the first older trip
            if (!trip.month().equals("October")) break;
            october.add(trip);
        }
        List<String> parts = new ArrayList<>();
        int total = 0;
        for (Trip t : october) { parts.add(t.tripId() + " (" + t.minutes() + " min)"); total += t.minutes(); }
        System.out.println("October trips: " + String.join(", ", parts));
        System.out.println("October total: " + total + " min | pages fetched: " + api.pagesFetched + " of 4");

        api = new TripApi();
        Trip firstLong = null;
        for (Trip t : new TripHistory(api, 3)) if (t.minutes() > 30) { firstLong = t; break; }
        System.out.println("first trip over 30 minutes: " + firstLong.tripId() + " | pages fetched: " + api.pagesFetched);

        api = new TripApi();
        int count = 0;
        for (Iterator<Trip> it = new TripHistory(api, 3).iterator(); it.hasNext(); it.next()) count++;
        System.out.println("all trips: " + count + " | page requests: " + api.pagesFetched + " (the last comes back empty)");
    }
}

Output (the same in all three languages)

October trips: T-12 (14 min), T-11 (32 min), T-10 (8 min), T-9 (21 min)
October total: 75 min | pages fetched: 2 of 4
first trip over 30 minutes: T-11 | pages fetched: 1
all trips: 12 | page requests: 5 (the last comes back empty)

6. Try it

How many pages does it take?

Twelve trips, newest first: the four in bold are from October. Pick a question and a page size, and see which pages the iterator fetched.

Page size

Solid outline: a page that was fetched. Shaded: a trip the loop actually read.

7. When not to use it

What you get

  • Storage hidden: pages, cursors or trees look like a simple sequence.
  • Lazy: work is done only as far as the loop goes.
  • One loop to get right: paging logic lives in one place.
  • Works with the language: for, filter, map and friends just work.

What you pay

  • One pass, forward only: an iterator can't usually go back or be restarted.
  • Hidden cost: a harmless-looking loop may make network calls.
  • Changes during iteration: if the collection changes mid-loop, results can skip or repeat.
  • Debugging laziness: work happens later than the line that set it up.
If…Use instead
The data is small and already in memoryA plain list
You need different operations over each node of a structure21 Visitor
You must walk a tree of mixed node typesIterator over a 10 Composite
Callers need random access or counts up frontLoad into a list, or offer a separate count call

8. How it goes wrong

Reusing a spent iteratorLooping twice over the same iterator gives nothing the second time. Loop over the iterable, which makes a fresh iterator each time.
Changing the collection while loopingAdding or removing elements mid-loop can skip or repeat items. Collect changes and apply them after.
Hiding expensive workA for loop that quietly makes 400 network calls surprises everyone. Name it clearly or expose page size.
Off-by-one at the endStopping when a page is short misses the empty-page case, and vice versa. Write the end condition once, in the iterator.

9. Remember it and say it

Memory hook: "Next one, please"Ask for the next element; the collection fetches it however it likes.
How this hook works: what “Next one, please” means

What the slogan means, phrase by phrase

“Next”
__next__() / next().
“one”
One element at a time.
“please”
The collection decides how to get it.

Why this picture fits: A library counter hides the stacks: you ask for the next book; they fetch from storage in batches.

The story → the concept

The libraryThe code
The counterTripHistory
A trolley load from the backOne page from TripApi
Your reading listThe for loop
Stopping when you've found itbreak: later pages never fetched

Watch it on an example

  1. The October loop asks for trips; the iterator fetches page 1 (T-12 to T-10).
  2. It needs a fourth trip, so it fetches page 2 (T-9 to T-7).
  3. T-8 is from September; the loop breaks. Pages 3 and 4 are never fetched.

The trap it saves you from

Paging logic copied into every screen, each with its own end-of-data bug.

It still works when…

Yes: database cursors, file lines, API pagination helpers and tree walkers are all iterators.

In an interview or code review

10. Check yourself

What does an iterator hide from the caller?

Pages, cursors or trees all look like a sequence.

The October loop breaks at T-8. How many pages were fetched (page size 3)?

Pages 3 and 4 are never requested.

The service switches to cursors. What changes?

Callers keep their for loops.

You loop twice over the same Python generator object. What happens the second time?

Loop over the iterable to get a fresh iterator.

In Python, what writes an iterator for you?

yield from page hands out a page's trips one by one.

11. Go deeper

ResourceWhy
10 CompositeIterating a tree of zones and stations.
Python glossary: generatorIterators written with yield.
MDN: iteration protocolsHow JavaScript and TypeScript iterate.
Wikipedia: Iterator patternInternal and external iterators.