Notes
The problem
Here is the pain. An orders API returns results in pages of three, with a token that points to the next page. The monthly statement wants the total of all orders, but it has to fetch pages, loop over each page and follow tokens. Every report and every export copies this loop. If the API switches from tokens to page numbers, every caller breaks. The storage details have leaked into the client.
String token = null;
do {
OrderPage page = api.fetch(token);
for (Order o : page.items())
total += o.amount();
token = page.nextToken();
} while (token != null);
// copied into every report,
// every export, every search The idea
The idea: the collection does not expose its insides. Instead it hands out a small cursor object, the iterator, that answers two questions. Is there another item? And, give me the next one. How the items are really stored, in an array, a tree or pages on a server, stays hidden behind the cursor. Each loop gets its own cursor, so two loops can walk the same collection at the same time.
- the collection hands out
- a cursor object
- the cursor answers two
- questions:
- is there another item?
- give me the next item
- how items are stored stays
- hidden behind the cursor
The Java contract
Java builds this in. Iterable, in java dot lang, has one method, iterator, which returns a fresh iterator. Iterator, in java dot util, has has next and next. Next must throw a no such element exception when nothing is left. Remove is optional: its default implementation throws an unsupported operation exception. Any class that implements Iterable can be used in a for each loop.
interface Iterable<T> {
Iterator<T> iterator();
}
interface Iterator<E> {
boolean hasNext();
E next(); // NoSuchElementException
// when nothing is left
default void remove() {
throw new UnsupportedOperation...
}
} Participants
The participants with our names. Monthly statement is the client. Order history is the aggregate: it implements Iterable of order. Order page iterator is the concrete iterator: it implements Iterator and is the only class that knows about pages and tokens. Order API is the hidden data source. The client never sees the API, never sees a page and never sees a token.
The aggregate
Order history is tiny. It holds the API and implements one method. Every call to iterator returns a brand new order page iterator. That detail matters. If it returned the same iterator each time, a second loop would start where the first one stopped, or two loops would fight over one cursor. A fresh iterator per call means each loop has its own position.
final class OrderHistory
implements Iterable<Order> {
private final OrderApi api;
@Override
public Iterator<Order> iterator() {
return new OrderPageIterator(api);
}
} The iterator
The concrete iterator keeps three things: an iterator over the current page, the next token and a flag that says whether it has started. Has next loops while the current page is used up. If there is no next token, it returns false. Otherwise it fetches the next page and moves on. The while loop also skips empty pages safely. Next simply calls has next, throws if it is false, and returns the next order.
public boolean hasNext() {
while (!current.hasNext()) {
if (started && token == null)
return false;
OrderPage p = api.fetch(token);
started = true; token = p.nextToken();
current = p.items().iterator();
}
return true;
} One run
Watch one run. The statement wants the first order above four hundred. The for each loop asks order history for an iterator, then calls has next. The iterator fetches page one, hands out three orders, then fetches page two. Order O five, worth four hundred and seventy five, matches and the loop breaks. Pages three and four are never requested. The iterator is lazy: it loads only what the client actually reads.
For-each in disguise
The for each loop is just sugar. For any Iterable, the compiler asks for an iterator and then loops while has next is true, calling next each time. Arrays are the exception: for an array, the compiler writes a normal index loop. So the moment order history implements Iterable, every caller gets the short, clean loop for free, and none of them know that pages exist.
for (Order o : history) { ... }
// roughly compiles to:
Iterator<Order> it = history.iterator();
while (it.hasNext()) {
Order o = it.next();
...
}
// arrays use an index loop instead A tree iterator
Iterators shine on trees. A food menu has categories inside categories: drinks holds coffee and tea, and snacks holds sandwiches. Recursion would visit them all at once, but an iterator must hand out one node per call. The trick is an explicit stack. Next pops one category, pushes its children in reverse order so the first child comes out first, and returns the popped one. Has next is simply: is the stack non empty.
var stack = new ArrayDeque<MenuCategory>();
public MenuCategory next() {
if (stack.isEmpty())
throw new NoSuchElementException();
MenuCategory c = stack.pop();
List<MenuCategory> kids = c.children();
for (int i = kids.size() - 1; i >= 0; i--)
stack.push(kids.get(i));
return c;
} Fail-fast
Now fail-fast. Array list keeps a modification count. Its iterator remembers the count it started with, and if the list changes behind its back, the next call to next throws a concurrent modification exception. Removing an item inside a for each loop is the classic way to hit it. Use the iterator's own remove method, or remove if. Note that fail-fast is best effort, not a guarantee, so never rely on it for correctness.
for (String t : tags)
if (t.equals("new"))
tags.remove(t); // next() throws
// safe ways:
Iterator<String> it = tags.iterator();
while (it.hasNext())
if (it.next().equals("old")) it.remove();
tags.removeIf(t -> t.equals("old")); Other behaviours
Not every iterator fails fast. Array list and hash map do. Copy on write array list gives a snapshot iterator: it walks the array as it was when the iterator was created, and never throws. Concurrent hash map gives a weakly consistent iterator: it never throws a concurrent modification exception and may or may not show changes made during the walk. Know which one you have before you share a collection between threads.
- fail-fast: ArrayList, HashMap
- throw on outside changes
- snapshot: CopyOnWriteArrayList
- walks the array as it was
- when the iterator was made
- weakly consistent:
- ConcurrentHashMap, never
- throws, may or may not
- show later changes
When to use it
Write a custom iterator when the data is not a plain list: a tree, pages from a server, lines in a big file. It also helps when data should load lazily, or when you want several walk orders, like depth first and breadth first. Skip it when your data already lives in a list. Returning an unmodifiable view or a copy of that list is simpler, and it already comes with an iterator.
- use it when:
- storage is not a simple list
- (tree, pages, file, stream)
- data should load lazily
- you need several walk orders
- skip it when:
- a List is already enough:
- just return an unmodifiable
- view or a copy
Neighbours
Compare it with its neighbours. Composite is about building a tree of parts. Iterator is about walking such a tree. Visitor runs a different operation for each kind of element, and often uses an iterator to reach them. Java streams use internal iteration, where the library drives the loop. An iterator is external iteration: the caller drives the loop, and can pause or stop whenever it wants.
- Composite: builds the tree,
- iterator walks it
- Visitor: runs an operation
- per element type
- Stream: internal iteration,
- the library drives the loop
- Iterator: external iteration,
- the caller drives the loop
- and can stop at any time
In LLD interviews
In interviews it appears in two ways. Machine coding problems with feeds, search results or a file system need a lazy walk over pages or folders. And there are classic iterator questions: flatten a nested list, walk a binary search tree in order using a stack, build a peeking iterator that can look at the next item without consuming it, or alternate between several lists in round robin order.
- paged API or feed reader
- file system: list a folder
- tree one entry at a time
- flatten a nested list
- iterator over a binary
- search tree, in order
- peeking iterator: look at
- next without moving
- round-robin over many lists
Common mistakes
Common mistakes. A has next that moves the cursor, so calling it twice skips an item. Calling has next many times in a row must be safe. A next that returns null at the end instead of throwing no such element exception. Returning the same iterator from every call. Sharing one iterator between threads without a lock, since most iterators are not thread safe. And returning the internal list, which defeats the whole point.
- hasNext() with side effects:
- calling it twice skips items
- next() past the end returns
- null instead of throwing
- one shared iterator for
- every loop
- one iterator used by two
- threads with no lock
- exposing the internal list