How to Implement the Iterator Pattern Using Java Generics

The Iterator pattern provides a uniform way to traverse collections without exposing internal structure, and Java generics make it type-safe and reusable across any element type.

The Iterator pattern decouples client code from collection implementations by defining a standard traversal interface. In the iluwatar/java-design-patterns repository, this pattern is realized through a generic Iterator<T> contract that enables both list-based and tree-based collections to be traversed with compile-time type safety.

The Generic Iterator Interface

At the core of the implementation is the Iterator<T> interface defined in iterator/src/main/java/com/iluwatar/iterator/Iterator.java. This minimal contract declares two essential operations:

• boolean hasNext() – checks if additional elements exist
• T next() – returns the next element with generic type T

By parameterizing the interface with type T, the same contract supports any element type—from Item objects in a treasure chest to TreeNode<Integer> values in a binary search tree—without casting or runtime type errors.

List-Based Implementation with Filtering

The repository demonstrates a concrete aggregate implementation in iterator/src/main/java/com/iluwatar/iterator/list/TreasureChest.java. This class maintains an internal List<Item> but never exposes it directly. Instead, it provides a factory method that returns a filtered iterator:

public Iterator<Item> iterator(ItemType itemType) {
    return new TreasureChestItemIterator(this, itemType);
}

The TreasureChestItemIterator class in iterator/src/main/java/com/iluwatar/iterator/list/TreasureChestItemIterator.java implements Iterator<Item> and encapsulates three key fields: a reference to the TreasureChest, the current cursor position, and the ItemType filter. During traversal, next() advances the cursor and returns only items matching the specified type, demonstrating how iterators can encapsulate complex traversal logic without burdening the client.

TreasureChest chest = new TreasureChest();
Iterator<Item> potionIter = chest.iterator(ItemType.POTION);

while (potionIter.hasNext()) {
    Item potion = potionIter.next();
    System.out.println(potion);
}

Tree-Based Implementation with O(h) Space

For hierarchical data, the repository provides BstIterator<T> in iterator/src/main/java/com/iluwatar/iterator/bst/BstIterator.java. This generic iterator performs in-order traversal of a binary search tree using O(h) auxiliary space, where h is the tree height. It achieves this efficiency by maintaining an ArrayDeque<TreeNode<T>> stack that stores only the leftmost path from the root.

The iterator relies on TreeNode<T> defined in iterator/src/main/java/com/iluwatar/iterator/bst/TreeNode.java, which provides generic value, left, and right fields. The BstIterator constructor and next() method invoke pushPathToNextSmallest to lazily populate the stack, ensuring memory usage scales with tree depth rather than total node count.

TreeNode<Integer> root = new TreeNode<>(8);
root.insert(3);
root.insert(10);
root.insert(1);

Iterator<TreeNode<Integer>> bstIter = new BstIterator<>(root);

while (bstIter.hasNext()) {
    TreeNode<Integer> node = bstIter.next();
    System.out.println(node.getVal());
}

Client Decoupling in Practice

The App.java file in iterator/src/main/java/com/iluwatar/iterator/App.java demonstrates the primary benefit of this pattern: client code depends solely on the Iterator<T> abstraction. Whether traversing a filtered list or an in-order tree sequence, the client invokes identical hasNext() and next() calls without knowledge of the underlying data structure. This uniformity allows new collection types to be added—such as graphs or linked lists—by simply implementing the generic iterator interface, requiring zero changes to existing client code.

Summary

• Type Safety: The generic Iterator<T> interface ensures that next() returns the correct type without casting, as implemented in Iterator.java.
• Encapsulation: TreasureChest hides its internal List<Item> and exposes only the iterator, while TreasureChestItemIterator encapsulates filtering logic.
• Memory Efficiency: BstIterator<T> achieves O(h) space complexity for tree traversal using a stack-based approach with pushPathToNextSmallest.
• Decoupling: Client code in App.java operates against the generic interface, remaining agnostic to whether the collection is a list or a binary search tree.

Frequently Asked Questions

What advantages do Java generics provide when implementing the Iterator pattern?

Java generics eliminate the need for runtime casting and reduce ClassCastException risks. By defining Iterator<T> with a type parameter, the compiler enforces that next() returns exactly the expected type, making the pattern safer and more readable across different collection implementations in the java-design-patterns repository.

How does the BST iterator maintain O(h) space complexity?

BstIterator<T> uses an ArrayDeque<TreeNode<T>> to store only the leftmost path from the current node to the root, which requires at most h stack frames where h is the tree height. The pushPathToNextSmallest method lazily pushes nodes onto this stack only when traversing to the next element, rather than loading the entire tree into memory at initialization.

Can filtering logic be added to any iterator without modifying the aggregate?

Yes. The repository demonstrates this in TreasureChestItemIterator, which accepts an ItemType filter in its constructor and applies it during traversal. Because the iterator maintains its own cursor state and filtering criteria, the aggregate (TreasureChest) remains unchanged while different iterators can provide different views of the same data.

How does the Iterator pattern improve code maintainability?

By depending only on the Iterator<T> interface, client code in App.java remains stable even when underlying collection implementations change. Adding a new collection type requires only creating a new iterator class that implements the generic interface, following the open/closed principle and preventing ripple effects throughout the codebase.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}