Iterator

Part of the free Low-Level Design course on LogicWiz, in the chapter: Behavioural patterns III. The class-diagram exercises run in the app.

Iterator: the loop that does not care where orders live

"Your report has three loops for one idea. Why does it need to know where the orders are kept?"

Priya, reading OrderReport

Three loops for one idea

SwiftKart's support team wants a report of a customer's past orders. The orders live in three places, because the app grew in three steps.

  • Old orders sit in an array, Order[].
  • Recent orders sit in an ArrayList, a list that grows when you add to it.
  • The full history sits on a server. You ask for it one page at a time: a batch of orders, say 20. fetchPage(page, size) returns one batch, and an empty list when the pages run out.

Arjun wrote one method for each place:

public class OrderReport {
    public void printFromArray(Order[] orders) {
        for (int i = 0; i < orders.length; i++) {
            System.out.println(orders[i].id());
        }
    }

    public void printFromList(List<Order> orders) {
        for (int i = 0; i < orders.size(); i++) {
            System.out.println(orders.get(i).id());
        }
    }

    public void printFromApi(OrderApi api) {
        int page = 0;
        List<Order> batch = api.fetchPage(page, 20);
        while (!batch.isEmpty()) {
            for (Order o : batch) {
                System.out.println(o.id());
            }
            page++;
            batch = api.fetchPage(page, 20);
        }
    }
}

Each loop does the same job, but each must know how its orders are stored. The array loop counts positions. The list loop asks for size() and get(i). The paged loop keeps a page counter and refills a batch by hand.

That knowledge leaks into every report. If recent orders move to a database, every loop over them must change. A refund report would copy the paged loop, and a bug fixed in one copy would stay in the other.

Arjun's first idea was: "I will return a List<Order> from every source. Then every loop looks the same." That works for the array and the list, but not for the history. The server may hold 40,000 orders. To build one list, you fetch every page before the report prints a line. If the report needs only the latest 20, you fetched almost 40,000 for nothing.

The report needs something smaller: "give me the next order, and tell me when there are no more."

The idea in plain words, and its structure

Think of a library desk. You ask the librarian for "the next book from the history shelf". Sometimes it is on a shelf behind her. Sometimes she orders it from the central store. You never learn which. You keep saying "next" until she says "that is all".

The Iterator pattern works like that desk. A collection gives out a small helper object, the iterator, that hands over the items one at a time and hides how they are stored. The caller asks only two questions: is there another item (hasNext), and what is it (next).

Java has this pattern built in, as two interfaces in java.util. Here they are, simplified:

public interface Iterator<T> {
    boolean hasNext();   // is there another item?
    T next();            // give me the next item and move on
}

public interface Iterable<T> {
    Iterator<T> iterator();   // give me a fresh iterator
}

The <T> means "some type, filled in later", so an Iterator<Order> hands out Order objects. An Iterable<Order> can give you a fresh iterator. The real Iterator also has a remove method, which comes up later.

The for-each loop works on anything Iterable, and the compiler rewrites it into the second form below:

for (Order o : orders) {
    System.out.println(o.id());
}

// The compiler turns it into this:
Iterator<Order> it = orders.iterator();
while (it.hasNext()) {
    Order o = it.next();
    System.out.println(o.id());
}

So to make a paged history work in a for-each loop, implement Iterable. Two details matter. First, iterator() returns a fresh iterator every time, each with its own position, so two loops over one list do not disturb each other. Second, an iterator is used once. When it runs out, ask the collection for a new one.

Where the analogy stops: a librarian can fetch book 7 and then book 2. An iterator walks forward only. If you need order number 7 directly, you want a list with get(7).

The structure. The pattern has four roles:

  • Iterator: the interface with hasNext and next.
  • Concrete iterator: one class per way of storing items, which remembers the position.
  • Iterable: the interface of a collection that can create an iterator.
  • Client: the code that loops, here OrderReport.
classDiagram
  class Iterable {
    <<interface>>
    +iterator() Iterator
  }
  class Iterator {
    <<interface>>
    +hasNext() boolean
    +next() Order
  }
  class OrderReport {
    +print(orders)
  }
  OrderReport ..> Iterable
  OrderReport ..> Iterator
  Iterable <|.. PagedOrderHistory
  Iterator <|.. PageIterator
  PagedOrderHistory ..> PageIterator : creates
  PageIterator --> OrderApi

OrderReport depends only on the two interfaces. Only PageIterator knows a server exists.

Build it: a paged history and a menu tree

Step 1: the types the report works with.

public record Order(int id, String status, long totalPaise) {
    public boolean isCancelled() { return status.equals("CANCELLED"); }
}

public interface OrderApi {
    List<Order> fetchPage(int page, int size);   // empty list when no more pages
}

Money is in paise, hundredths of a rupee.

Step 2: an iterator that fetches pages only when needed.

public class PagedOrderHistory implements Iterable<Order> {
    private final OrderApi api;
    private final int pageSize;

    public PagedOrderHistory(OrderApi api, int pageSize) {
        this.api = api;
        this.pageSize = pageSize;
    }

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

    private class PageIterator implements Iterator<Order> {
        private int nextPage = 0;
        private List<Order> batch = List.of();
        private int position = 0;
        private boolean exhausted = false;

        public boolean hasNext() {
            while (position >= batch.size() && !exhausted) {
                batch = api.fetchPage(nextPage++, pageSize);
                position = 0;
                exhausted = batch.isEmpty();
            }
            return position < batch.size();
        }

        public Order next() {
            if (!hasNext()) throw new NoSuchElementException();
            return batch.get(position++);
        }
    }
}

PageIterator is an inner class: a class written inside another, which can read the outer class's fields. That is how it reaches api and pageSize.

All the work is in hasNext. If the current batch is used up and pages remain, it fetches the next page. An empty page means the server has nothing more.

next calls hasNext first, so the pair is safe to call in any order. When nothing is left, next throws NoSuchElementException, as Java's contract requires.

Step 3: run it and stop early.

OrderApi api = new FakeOrderApi(5);          // 5 orders, ids 1 to 5
PagedOrderHistory history = new PagedOrderHistory(api, 2);

for (Order o : history) {
    System.out.println("order " + o.id());
    if (o.id() == 3) break;
}

FakeOrderApi is a stand-in that prints a line when called. The output:

  fetching page 0
order 1
order 2
  fetching page 1
order 3

Page 2 was never fetched. This is lazy work: nothing happens until the loop asks. A full walk of the five orders fetches pages 0, 1 and 2, and then page 3, which is empty and ends the walk.

Step 4: the report needs one method.

public class OrderReport {
    public void print(Iterable<Order> orders) {
        for (Order o : orders) {
            System.out.println(o.id());
        }
    }
}
// report.print(recentOrdersList);
// report.print(history);
// report.print(Arrays.asList(oldOrdersArray));

Three methods became one. An array is not Iterable, so Arrays.asList wraps it.

A tree is not a line. Priya's next comment was about the app menu, with categories inside categories, the shape from the composite chapter. A recursive method walks the whole tree in one go. An iterator must pause after each item, and recursion keeps its place on a call stack you cannot pause. So we keep the place ourselves in a stack: a list where you add and remove at the same end, so the last item in is the first out.

public class MenuNode {
    private final String name;
    private final List<MenuNode> children = new ArrayList<>();

    public MenuNode(String name) { this.name = name; }

    public MenuNode add(MenuNode child) {
        children.add(child);
        return this;
    }

    public String name() { return name; }
    public List<MenuNode> children() { return Collections.unmodifiableList(children); }
}

public class MenuWalker implements Iterable<MenuNode> {
    private final MenuNode root;

    public MenuWalker(MenuNode root) { this.root = root; }

    @Override
    public Iterator<MenuNode> iterator() {
        return new Walk(root);
    }

    private static class Walk implements Iterator<MenuNode> {
        private final Deque<MenuNode> stack = new ArrayDeque<>();

        Walk(MenuNode root) { stack.push(root); }

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

        public MenuNode next() {
            if (stack.isEmpty()) throw new NoSuchElementException();
            MenuNode node = stack.pop();
            List<MenuNode> kids = node.children();
            for (int i = kids.size() - 1; i >= 0; i--) {
                stack.push(kids.get(i));
            }
            return node;
        }
    }
}

next takes the top node off the stack, then pushes its children in reverse, so the first child ends on top. For Grocery with Dairy (Milk, Curd) and Bakery (Bread), a for-each prints Grocery, Dairy, Milk, Curd, Bakery, Bread. This is depth-first order: finish one branch before the next. A queue instead of a stack (items leave in the order they arrived) gives breadth-first order, one level at a time.

Removing while iterating, and where streams fit

Support wants cancelled orders removed from a list. Arjun wrote this loop:

List<Order> orders = new ArrayList<>(List.of(
    new Order(1, "PLACED", 24000), new Order(2, "CANCELLED", 9000),
    new Order(3, "PLACED", 15000), new Order(4, "CANCELLED", 31000)));

for (Order o : orders) {
    if (o.isCancelled()) {
        orders.remove(o);
    }
}

It compiles, and it crashes:

Exception in thread "main" java.util.ConcurrentModificationException

Here is why. ArrayList keeps a counter of changes to its size. A new iterator copies that counter, and every next() compares the two numbers. If they differ, someone changed the list behind the iterator's back, so its position may be wrong. The iterator throws ConcurrentModificationException instead of returning wrong items. This is fail-fast. The name misleads: nothing ran at the same time. One thread changed the list inside its own loop.

⚠️ Warning: Fail-fast is a best effort, not a guarantee. In a list of four, remove the third item inside a for-each, and the loop ends with no error and never visits the fourth. Run it and see: the cancelled fourth order stays in the list.

The fix is to let the iterator do the removing, because it can update its own counter:

Iterator<Order> it = orders.iterator();
while (it.hasNext()) {
    if (it.next().isCancelled()) {
        it.remove();
    }
}
// or, shorter: orders.removeIf(Order::isCancelled);

remove() deletes the item that next() returned last. PagedOrderHistory does not offer it: the default remove() throws UnsupportedOperationException, which is right for a read-only history on a server.

External and internal iteration, and streams. So far your code drives the loop and asks for each item. That is external iteration, and it lets you stop, skip, remove, or walk two sources together. Internal iteration turns it around: you hand over a piece of code and the collection calls it for every item, as in orders.forEach(...) or a stream. A stream is a one-use chain of steps, such as filter and count, built on a cousin of the iterator called a spliterator. Streams read well for filter, map and count, but they do not replace iterators: you cannot remove through one or reuse it. Because Iterable has a default spliterator() method, and StreamSupport turns a spliterator into a stream, your own history works with streams:

long big = StreamSupport.stream(history.spliterator(), false)
        .limit(3)
        .filter(o -> o.totalPaise() > 10000)
        .count();

This prints 1, because only order 3 costs over 10000 paise. It is lazy too: it fetched pages 0 and 1 only.

When a plain list is enough

Arjun asked: "Should the cart get an iterator too? It has five items." No. When the items are few and already in one list, return a read-only view with Collections.unmodifiableList(items). A custom iterator adds a class and gives nothing back.

Write your own iterator when:

  • the items arrive in pieces, from a server, a file or a database;
  • the structure is not a line, such as a tree, a graph or a grid;
  • you want to change the storage later without touching callers;
  • one collection needs more than one way to walk, such as newest first or by price.

It has costs:

  • State. An iterator holds a position, so each walk needs its own.
  • Changes during a walk. If the collection changes, the iterator may fail.
  • Hidden failures. hasNext cannot declare a checked exception. If the server call inside it fails, the error must leave as a runtime exception, the kind Java does not force callers to catch.

The composite chapter describes the tree, and the iterator walks it.

In interviews you meet this pattern as the library catalogue (books by author, or newest first), feed paging and the file system walk (folders inside folders). In feed paging, the next page loads as the user scrolls, often by a cursor: a token from the server that marks where the next page starts.

Practice: hide where orders live

The starter has OrderReport calling OrderApi directly. Draw an iterator interface and a collection interface that creates it, with a paged and a list-based version of each, so the report names neither.

📌 Summary: An iterator hands out items one at a time and hides how they are stored. Implement Iterable for for-each, fetch lazily, remove through the iterator, and skip the pattern for a small list.

What Arjun learns next

The report is clean. Then the dispatch screen shows a different mess: riders, orders and the screen all call each other directly. Arjun meets the Mediator pattern.

Check your understanding

  1. A report prints the first 20 orders from a server history of 40,000 orders, using a lazy PagedOrderHistory with page size 20. The loop breaks after order 20. How many pages are fetched?
  2. Arjun removes cancelled orders with orders.remove(o) inside a for-each over an ArrayList. What happens, and what is the fix?
  3. A teammate says: "Streams replace iterators, so we never need to write an Iterator." Which job still needs one?
  4. The cart holds five items in an ArrayList. A teammate wants a custom CartIterator class so callers cannot see it is a list. What do you say?