Iterator Pattern

Walk through the items of a collection one at a time without knowing, or depending on, how the collection stores them.

Overview

The Iterator pattern is one of the behavioral patterns in Design Patterns (Gamma, Helm, Johnson and Vlissides, 1994). A collection keeps its items in some structure: an array, a linked list, a tree, a hash table, a page of results from an API. The pattern moves the job of walking that structure out of the collection and out of the caller, into a small object that knows where it is and how to take the next step. The caller asks that object for the next item until there are none left.

The pattern is so useful that most languages built it in. Python's for loop, Java's enhanced for and JavaScript's for...of all call an iterator behind the scenes. Interviewers ask about Iterator to see whether you understand what the loop is doing, whether you can write an iterator for a structure the language does not know (a tree, a graph, a paginated API), and whether you know what goes wrong when a collection changes during a walk.

The problem it solves

Without an iterator, code that walks a collection has to know how the collection is built. A caller that indexes into an array breaks when the collection becomes a linked list; a caller that recurses over a tree cannot be reused for a graph. The collection also has to expose its insides so callers can walk them, which means callers can change them by accident.

Caller knows the structure (index, next pointer, child links) — Caller knows two operations: is there more, and give me the next one
One walking routine per structure, in every caller — One iterator per structure, written once
Collection exposes its internal list or nodes — Collection stays sealed; only the iterator sees inside
Two walks at once need two sets of bookkeeping in the caller — Each iterator holds its own position, so many walks can be in flight

Structure

Iterable (aggregate) — Creates an iterator over its items — iter() — Iterable.iterator()
Iterator — Remembers the position and returns the next item — next(), raises StopIteration at the end — hasNext(), next()
Concrete collection — Owns the items — Playlist — ArrayList, your own class
Concrete iterator — Knows how to step through that one structure — PlaylistIterator — ArrayList's inner iterator

What the language does for you

Python's documentation defines the protocol: a container's iter() returns an iterator; the iterator's next() returns the next item and raises StopIteration when there are none, and must keep raising it on later calls. The iterator's own iter() returns itself, so an iterator can be used wherever an iterable is expected. The Java Language Specification translates an enhanced for over an Iterable into a loop that calls iterator() once, then hasNext() and next() until hasNext() is false.

A runnable example

The playlist never gives out its list. Each for loop gets a fresh iterator, so two loops do not interfere, and an exhausted iterator keeps saying it is done.

Iterable versus iterator

The two words are easy to mix up, and interviewers notice. An iterable is something you can get an iterator from; a list is iterable. An iterator is the object that hands out items and is used up as it goes. Python's glossary makes the difference concrete: passing a list to iter() gives a new iterator each time, so you can loop over the list twice, while looping twice over the same iterator gives nothing the second time, because it is already exhausted.

Example — list, dict, a file object, your class with iter — the object iter(some_list) returns, a generator
Has — iter() — next() and iter() returning itself
Reusable? — Yes, each iter() starts over — No, one pass and it is spent
Holds a position? — No — Yes

Generators: the short way to write one

A Python generator function is a function with yield in it. Calling it returns a generator iterator; each yield hands out one value and pauses, keeping the local variables until the next request. This is the Iterator pattern with the bookkeeping written by the interpreter. Most custom iterators in Python should be generators; write the class form only when the iterator needs public state or several methods.

What you will be able to do

Explain what a for loop does in terms of iter, next and StopIteration, or iterator(), hasNext() and next().
Write an iterator for a structure the language does not walk for you: a tree in sorted order, a graph in breadth-first order, a paginated API.
Tell an iterable from an iterator and say which one you can loop over twice.
Describe what happens when a collection changes during iteration, in Python and in Java, and how to avoid it.
Choose between a generator and an iterator class, and between external and internal iteration.

Interview questions

Write an iterator that returns the values of a binary search tree in sorted order, one at a time.
What happens if you change a collection while iterating over it?
What is the difference between external and internal iteration?
Design an iterator over a paginated API.
Why does the collection create the iterator instead of the caller?