LOW-LEVEL DESIGN · BEHAVIORAL PATTERNS · BEHAVIORAL · 40 OF 48

Iterator Pattern in Java: Iterable, Fail-Fast and Custom Iterators

The Iterator pattern in Java: walk a collection one element at a time without seeing how it is stored. Covers Iterator and Iterable, how for-each uses them, a lazy iterator over paged API results, a depth-first iterator over a tree, fail-fast behaviour and ConcurrentModificationException, safe removal, and where it appears in LLD interviews.

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
  43. 43
  44. 44
  45. 45
  46. 46
  47. 47
  48. 48
1 / 17

Press play to hear the narration, or step through at your own pace. The Java example is below.

Java example

One file, Java 17, 211 lines, with a small main() demo. Save it as PagedIteratorDemo.java, then run javac PagedIteratorDemo.java && java PagedIteratorDemo.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.ConcurrentModificationException;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

/**
 * Iterator: walk a collection one item at a time without knowing how it is stored.
 * Two custom iterators: one over paged API results, one over a tree.
 */
public class PagedIteratorDemo {

    public static void main(String[] args) {
        FakeOrderApi api = new FakeOrderApi(10, 3);   // 10 orders, 3 per page

        // BEFORE: every caller juggles pages and tokens itself.
        int naiveTotal = 0;
        String token = null;
        do {
            OrderPage page = api.fetch(token);
            for (Order o : page.items()) {
                naiveTotal += o.amount();
            }
            token = page.nextToken();
        } while (token != null);
        System.out.println("Before: total " + naiveTotal + " (caller handled " + api.calls() + " pages)");

        // AFTER: the caller sees an Iterable and a for-each loop.
        OrderHistory history = new OrderHistory(api);
        api.resetCalls();
        int total = 0;
        for (Order o : history) {
            total += o.amount();
        }
        System.out.println("After:  total " + total + " (" + api.calls()
                + " pages fetched, caller saw none)");

        // Lazy: stop early and later pages are never fetched.
        api.resetCalls();
        for (Order o : history) {
            if (o.amount() > 400) {
                System.out.println("First order above 400: " + o
                        + " after " + api.calls() + " page fetches");
                break;
            }
        }

        // Tree iterator: depth-first, one category per call to next().
        MenuCategory menu = new MenuCategory("Menu", List.of(
                new MenuCategory("Drinks", List.of(
                        new MenuCategory("Coffee", List.of()),
                        new MenuCategory("Tea", List.of()))),
                new MenuCategory("Snacks", List.of(
                        new MenuCategory("Sandwiches", List.of())))));
        List<String> names = new ArrayList<>();
        for (MenuCategory c : menu) {
            names.add(c.name());
        }
        System.out.println("Depth-first: " + names);

        // Fail-fast: changing the list behind the iterator's back.
        List<String> tags = new ArrayList<>(List.of("new", "sale", "old", "gift"));
        try {
            for (String t : tags) {
                if (t.equals("new")) {
                    tags.remove(t);
                }
            }
        } catch (ConcurrentModificationException e) {
            System.out.println("Fail-fast: ConcurrentModificationException, list is now " + tags);
        }
        // Safe removal through the iterator itself.
        Iterator<String> it = tags.iterator();
        while (it.hasNext()) {
            if (it.next().equals("old")) {
                it.remove();
            }
        }
        System.out.println("Safe remove: " + tags);
    }
}

record Order(String id, int amount) {
    @Override
    public String toString() {
        return id + "=" + amount;
    }
}

record OrderPage(List<Order> items, String nextToken) { }

/** The hidden data source. A null token means "first page". */
interface OrderApi {
    OrderPage fetch(String token);
}

final class FakeOrderApi implements OrderApi {
    private final List<Order> all = new ArrayList<>();
    private final int pageSize;
    private int calls;

    FakeOrderApi(int count, int pageSize) {
        for (int i = 1; i <= count; i++) {
            all.add(new Order("O-" + i, 100 + 75 * i));
        }
        this.pageSize = pageSize;
    }

    @Override
    public OrderPage fetch(String token) {
        calls++;
        int start = token == null ? 0 : Integer.parseInt(token);
        int end = Math.min(start + pageSize, all.size());
        String next = end < all.size() ? String.valueOf(end) : null;
        return new OrderPage(List.copyOf(all.subList(start, end)), next);
    }

    int calls() {
        return calls;
    }

    void resetCalls() {
        calls = 0;
    }
}

/** Aggregate: hands out a fresh iterator on every call. */
final class OrderHistory implements Iterable<Order> {
    private final OrderApi api;

    OrderHistory(OrderApi api) {
        this.api = api;
    }

    @Override
    public Iterator<Order> iterator() {
        return new OrderPageIterator(api);
    }
}

/** Concrete iterator: the only class that knows about pages and tokens. */
final class OrderPageIterator implements Iterator<Order> {
    private final OrderApi api;
    private Iterator<Order> current = Collections.emptyIterator();
    private String token;
    private boolean started;

    OrderPageIterator(OrderApi api) {
        this.api = api;
    }

    @Override
    public boolean hasNext() {
        while (!current.hasNext()) {            // also skips empty pages
            if (started && token == null) {
                return false;
            }
            OrderPage page = api.fetch(token);  // load lazily, one page at a time
            started = true;
            token = page.nextToken();
            current = page.items().iterator();
        }
        return true;
    }

    @Override
    public Order next() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        return current.next();
    }
}

/** A tree that can be walked with a for-each loop. */
record MenuCategory(String name, List<MenuCategory> children) implements Iterable<MenuCategory> {
    @Override
    public Iterator<MenuCategory> iterator() {
        return new DepthFirstWalker(this);
    }
}

/** Depth-first iterator using an explicit stack instead of recursion. */
final class DepthFirstWalker implements Iterator<MenuCategory> {
    private final Deque<MenuCategory> stack = new ArrayDeque<>();

    DepthFirstWalker(MenuCategory root) {
        stack.push(root);
    }

    @Override
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    @Override
    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--) {   // reverse, so the first child pops first
            stack.push(kids.get(i));
        }
        return c;
    }
}

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.

Paging leaks into callers
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.

Iterator
  • 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.

java.lang / java.util
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.

OrderHistory
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.

OrderPageIterator
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.

What for-each becomes
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.

DepthFirstWalker.next()
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.

Fail-fast
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.

Iterator flavours
  • 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 / skip it
  • 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.

How it differs
  • 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.

Where it shows up
  • 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.

Avoid these
  • 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

Interview questions

What problem does the Iterator pattern solve?

It lets a client go through the elements of a collection without knowing how they are stored. The collection hands out an iterator object, so its internal structure can change without breaking the code that loops over it.

What is the difference between Iterable and Iterator in Java?

Iterable is something that can be walked: it has one method, iterator, which returns a new Iterator. Iterator is the cursor that does the walking with hasNext and next. Implementing Iterable lets a class be used in a for-each loop.

What does fail-fast mean for an iterator?

A fail-fast iterator, like the one from ArrayList or HashMap, detects that the collection was structurally changed by something other than the iterator and throws ConcurrentModificationException on the next call. It is best effort, so it should only be used to find bugs, not to make code correct.

How do you remove elements safely while iterating a list?

Use the iterator explicitly and call its remove method after next, or use Collection.removeIf with a condition. Calling list.remove inside a for-each loop changes the list behind the iterator and usually causes ConcurrentModificationException.

How are ConcurrentHashMap and CopyOnWriteArrayList iterators different?

CopyOnWriteArrayList returns a snapshot iterator that walks the array as it was when the iterator was created and never throws. ConcurrentHashMap returns a weakly consistent iterator that never throws ConcurrentModificationException and may or may not reflect changes made during the walk.

How would you write an iterator over a binary tree?

Keep an explicit stack instead of recursion. For depth-first order, pop a node in next, push its children so the left one comes out first, and return the node; hasNext checks whether the stack is empty. An in-order iterator pushes the left spine and moves to the right subtree after each pop.

Why should hasNext have no visible side effects?

Callers may call hasNext several times before calling next. If hasNext advances the cursor, items get skipped. It may prepare or cache data, like fetching the next page, but calling it repeatedly must give the same answer and keep the position.

What is the difference between external and internal iteration?

With external iteration, like an Iterator, the caller controls the loop and can pause or stop at any time. With internal iteration, like forEach or a Stream pipeline, the library runs the loop and calls your code for each element.