Iterator and generators

Walking a collection without exposing how it is stored.

Low-level design conceptBehavioral patterns2 Nov 2026

01The intuition

The problem it solves

A music app keeps a playlist in a list. Another part of the app loops over it with an index. Then the playlist becomes a linked list so that inserting in the middle is cheap, and every loop in the program breaks, because they all did songs[i]. Later a playlist is a tree of folders, and the loops need to be rewritten again.

class Playlist:
    def __init__(self) -> None:
        self.songs: list[str] = []

# elsewhere, in ten places:
i = 0
while i < len(playlist.songs):
    play(playlist.songs[i])
    i += 1

Build it one piece at a time

Step one: agree on two questions the collection can answer no matter how it is stored: is there a next item, and what is it. An object that answers them is an iterator; the loops talk to it, not to the storage.

class SongIterator:
    def __init__(self, songs: list[str]) -> None:
        self._songs = songs
        self._i = 0
    def has_next(self) -> bool:
        return self._i < len(self._songs)
    def next(self) -> str:
        song = self._songs[self._i]
        self._i += 1
        return song

it = playlist.iterator()
while it.has_next():
    play(it.next())

Step two: when the storage changes, only the iterator changes. A tree of folders gets an iterator with a stack; the ten loops are untouched.

class FolderIterator:
    def __init__(self, root: "Folder") -> None:
        self._stack: list = [root]
        self._advance()
    def _advance(self) -> None:          # walk until the top is a song
        while self._stack and isinstance(self._stack[-1], Folder):
            folder = self._stack.pop()
            self._stack.extend(reversed(folder.children))
    def has_next(self) -> bool:
        return bool(self._stack)
    def next(self) -> str:
        song = self._stack.pop()
        self._advance()
        return song

Step three: in Python the same idea is spelled with __iter__ and __next__, and a generator function writes the iterator for you, keeping its place between calls. The laziness matters: nothing is computed until asked, so an infinite or very large source still works.

from typing import Iterator

class Playlist:
    def __iter__(self) -> Iterator[str]:
        stack: list = [self.root]
        while stack:
            node = stack.pop()
            if isinstance(node, Folder):
                stack.extend(reversed(node.children))
            else:
                yield node          # pauses here until the next item is asked for

for song in playlist:
    play(song)

Why it works

The principle: separate walking from storing. The collection owns the data; the iterator owns the position; the loop owns neither. The invariant is that each item is returned exactly once, in a defined order, and next after the end fails clearly rather than repeating. Where it breaks: modifying the collection while iterating (either raise, or take a snapshot, but decide), two loops sharing one iterator by accident, and an iterator that does expensive work in has_next so calling it twice costs double. Interviewers test with "what if next is called without has_next?" and "can two people iterate at once?" Every iterator object carries its own position, so yes, as long as the collection is not mutated underneath.

The trade-off you must say out loud

For a plain list, the built-in loop is already an iterator and writing your own is noise. The pattern earns its keep when storage is unusual, when results are lazy or infinite, or when the walk order is a feature (zigzag, peeking, filtering). The follow-up is almost always a wrapper: write an iterator that takes other iterators and combines them, which is where the problems below start.

Where it shows up in the 100 Google problems

Peeking iterator: wrap any iterator and buffer one item so peek does not consume it.
Zigzag iterator over k lists: a queue of iterators, rotated after each next.
Flattening iterator over nested lists: the folder walk above with a stack of iterators.
Lazy tee: one source, n positions, and a buffer that holds only what the slowest reader has not seen.
Cursor-based pagination API: an iterator whose position is serialised into a token the client sends back.