The Iterator Pattern is a fundamental behavioral design pattern that provides a standardized way to access elements of a collection sequentially without exposing its underlying representation. This pattern is crucial for creating flexible, maintainable custom collections that can integrate seamlessly with Java's enhanced for-loops and streaming APIs.

This article explores how to implement the Iterator Pattern for custom collections, demonstrating both traditional and modern approaches in Java.

Understanding the Iterator Pattern

Problem: When you create a custom collection, you want clients to be able to traverse its elements without knowing:

• The collection's internal data structure
• The implementation details of storage
• How elements are organized internally

Solution: The Iterator Pattern provides a uniform interface for traversing different data structures while keeping the traversal logic separate from the collection itself.

Key Benefits:

• Encapsulation: Hides the collection's internal structure
• Flexibility: Multiple traversal algorithms can coexist
• Simplicity: Uniform interface across different collections
• Java Integration: Works with enhanced for-loops

Core Iterator Interfaces in Java

Java provides two key interfaces in java.util:

1. Iterator

public interface Iterator<E> { boolean hasNext(); E next(); default void remove() { /* optional removal */ } // Java 8+ default methods for additional functionality }

2. Iterable

public interface Iterable<T> { Iterator<T> iterator(); // Java 8+ default methods default void forEach(Consumer<? super T> action) { /* ... */ } default Spliterator<T> spliterator() { /* ... */ } }

Basic Implementation: Custom Array Collection

Let's start with a simple custom array-based collection:

import java.util.Iterator; import java.util.NoSuchElementException; public class CustomArray<T> implements Iterable<T> { private T[] elements; private int size; private static final int DEFAULT_CAPACITY = 10; @SuppressWarnings("unchecked") public CustomArray() { this.elements = (T[]) new Object[DEFAULT_CAPACITY]; this.size = 0; } public void add(T element) { if (size == elements.length) { resize(); } elements[size++] = element; } public T get(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); } return elements[index]; } public int size() { return size; } @SuppressWarnings("unchecked") private void resize() { T[] newArray = (T[]) new Object[elements.length * 2]; System.arraycopy(elements, 0, newArray, 0, size); elements = newArray; } // Implementing Iterable interface @Override public Iterator<T> iterator() { return new ArrayIterator(); } // Iterator implementation as inner class private class ArrayIterator implements Iterator<T> { private int currentIndex = 0; @Override public boolean hasNext() { return currentIndex < size; } @Override public T next() { if (!hasNext()) { throw new NoSuchElementException("No more elements in the collection"); } return elements[currentIndex++]; } @Override public void remove() { if (currentIndex == 0) { throw new IllegalStateException("next() must be called before remove()"); } int removeIndex = currentIndex - 1; // Shift elements to fill the gap System.arraycopy(elements, removeIndex + 1, elements, removeIndex, size - removeIndex - 1); elements[--size] = null; // Help garbage collection currentIndex--; } } }

Usage Example:

public class ArrayExample { public static void main(String[] args) { CustomArray<String> array = new CustomArray<>(); array.add("Java"); array.add("Python"); array.add("JavaScript"); array.add("Go"); // Using enhanced for-loop (requires Iterable implementation) System.out.println("Using enhanced for-loop:"); for (String language : array) { System.out.println(language); } // Using explicit iterator System.out.println("\nUsing explicit iterator:"); Iterator<String> iterator = array.iterator(); while (iterator.hasNext()) { String language = iterator.next(); System.out.println(language); if (language.equals("Python")) { iterator.remove(); // Remove current element } } // Using forEach (Java 8+) System.out.println("\nUsing forEach:"); array.forEach(System.out::println); } }

Advanced Implementation: Binary Search Tree Iterator

For more complex data structures, the iterator can implement sophisticated traversal algorithms:

import java.util.Iterator; import java.util.NoSuchElementException; import java.util.Stack; public class BinarySearchTree<T extends Comparable<T>> implements Iterable<T> { private Node root; private int size; private class Node { T data; Node left, right; Node(T data) { this.data = data; } } public void add(T data) { root = addRecursive(root, data); size++; } private Node addRecursive(Node current, T data) { if (current == null) { return new Node(data); } if (data.compareTo(current.data) < 0) { current.left = addRecursive(current.left, data); } else if (data.compareTo(current.data) > 0) { current.right = addRecursive(current.right, data); } return current; } public int size() { return size; } // In-order traversal iterator @Override public Iterator<T> iterator() { return new InOrderIterator(); } // Pre-order traversal iterator public Iterator<T> preOrderIterator() { return new PreOrderIterator(); } // In-order iterator using stack private class InOrderIterator implements Iterator<T> { private Stack<Node> stack = new Stack<>(); private Node current; public InOrderIterator() { current = root; pushLeft(current); } private void pushLeft(Node node) { while (node != null) { stack.push(node); node = node.left; } } @Override public boolean hasNext() { return !stack.isEmpty(); } @Override public T next() { if (!hasNext()) { throw new NoSuchElementException(); } Node node = stack.pop(); pushLeft(node.right); return node.data; } } // Pre-order iterator private class PreOrderIterator implements Iterator<T> { private Stack<Node> stack = new Stack<>(); public PreOrderIterator() { if (root != null) { stack.push(root); } } @Override public boolean hasNext() { return !stack.isEmpty(); } @Override public T next() { if (!hasNext()) { throw new NoSuchElementException(); } Node node = stack.pop(); if (node.right != null) stack.push(node.right); if (node.left != null) stack.push(node.left); return node.data; } } }

Usage Example:

public class TreeExample { public static void main(String[] args) { BinarySearchTree<Integer> tree = new BinarySearchTree<>(); tree.add(50); tree.add(30); tree.add(70); tree.add(20); tree.add(40); tree.add(60); tree.add(80); System.out.println("In-order traversal:"); for (Integer value : tree) { System.out.print(value + " "); } // Output: 20 30 40 50 60 70 80 System.out.println("\n\nPre-order traversal:"); Iterator<Integer> preOrder = tree.preOrderIterator(); while (preOrder.hasNext()) { System.out.print(preOrder.next() + " "); } // Output: 50 30 20 40 70 60 80 } }

Bidirectional Iterator: Custom Linked List

For collections that support bidirectional traversal:

import java.util.Iterator; import java.util.ListIterator; import java.util.NoSuchElementException; public class CustomLinkedList<T> implements Iterable<T> { private Node head, tail; private int size; private class Node { T data; Node next, prev; Node(T data) { this.data = data; } } public void addFirst(T data) { Node newNode = new Node(data); if (head == null) { head = tail = newNode; } else { newNode.next = head; head.prev = newNode; head = newNode; } size++; } public void addLast(T data) { Node newNode = new Node(data); if (tail == null) { head = tail = newNode; } else { tail.next = newNode; newNode.prev = tail; tail = newNode; } size++; } public int size() { return size; } @Override public Iterator<T> iterator() { return new ForwardIterator(); } public Iterator<T> descendingIterator() { return new BackwardIterator(); } public ListIterator<T> listIterator() { return new BidirectionalIterator(); } // Forward-only iterator private class ForwardIterator implements Iterator<T> { private Node current = head; @Override public boolean hasNext() { return current != null; } @Override public T next() { if (!hasNext()) { throw new NoSuchElementException(); } T data = current.data; current = current.next; return data; } } // Backward-only iterator private class BackwardIterator implements Iterator<T> { private Node current = tail; @Override public boolean hasNext() { return current != null; } @Override public T next() { if (!hasNext()) { throw new NoSuchElementException(); } T data = current.data; current = current.prev; return data; } } // Bidirectional iterator implementing ListIterator private class BidirectionalIterator implements ListIterator<T> { private Node nextNode = head; private Node lastReturned = null; private int nextIndex = 0; @Override public boolean hasNext() { return nextIndex < size; } @Override public T next() { if (!hasNext()) { throw new NoSuchElementException(); } lastReturned = nextNode; nextNode = nextNode.next; nextIndex++; return lastReturned.data; } @Override public boolean hasPrevious() { return nextIndex > 0; } @Override public T previous() { if (!hasPrevious()) { throw new NoSuchElementException(); } nextNode = (nextNode == null) ? tail : nextNode.prev; lastReturned = nextNode; nextIndex--; return lastReturned.data; } @Override public int nextIndex() { return nextIndex; } @Override public int previousIndex() { return nextIndex - 1; } @Override public void remove() { if (lastReturned == null) { throw new IllegalStateException(); } // Implementation of remove operation // (simplified for brevity) } @Override public void set(T t) { if (lastReturned == null) { throw new IllegalStateException(); } lastReturned.data = t; } @Override public void add(T t) { throw new UnsupportedOperationException("Add not supported"); } } }

Usage Example:

public class LinkedListExample { public static void main(String[] args) { CustomLinkedList<String> list = new CustomLinkedList<>(); list.addLast("A"); list.addLast("B"); list.addLast("C"); list.addLast("D"); System.out.println("Forward traversal:"); for (String item : list) { System.out.print(item + " "); } System.out.println("\n\nBackward traversal:"); Iterator<String> descending = list.descendingIterator(); while (descending.hasNext()) { System.out.print(descending.next() + " "); } System.out.println("\n\nBidirectional traversal:"); ListIterator<String> listIterator = list.listIterator(); while (listIterator.hasNext()) { System.out.print(listIterator.next() + " "); } while (listIterator.hasPrevious()) { System.out.print(listIterator.previous() + " "); } } }

Thread-Safe Iterator Implementation

For concurrent collections, iterators need special consideration:

import java.util.Iterator; import java.util.NoSuchElementException; import java.util.concurrent.locks.ReentrantReadWriteLock; public class ThreadSafeCollection<T> implements Iterable<T> { private Object[] elements; private int size; private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock(); public ThreadSafeCollection(int capacity) { this.elements = new Object[capacity]; this.size = 0; } public void add(T element) { lock.writeLock().lock(); try { if (size == elements.length) { throw new IllegalStateException("Collection is full"); } elements[size++] = element; } finally { lock.writeLock().unlock(); } } @Override public Iterator<T> iterator() { return new ThreadSafeIterator(); } private class ThreadSafeIterator implements Iterator<T> { private final Object[] snapshot; private int cursor = 0; @SuppressWarnings("unchecked") public ThreadSafeIterator() { lock.readLock().lock(); try { // Create a snapshot for consistent iteration snapshot = new Object[size]; System.arraycopy(elements, 0, snapshot, 0, size); } finally { lock.readLock().unlock(); } } @Override public boolean hasNext() { return cursor < snapshot.length; } @SuppressWarnings("unchecked") @Override public T next() { if (!hasNext()) { throw new NoSuchElementException(); } return (T) snapshot[cursor++]; } } }

Filtering Iterator Pattern

Create specialized iterators that filter elements:

import java.util.Iterator; import java.util.NoSuchElementException; import java.util.function.Predicate; public class FilteredCollection<T> implements Iterable<T> { private T[] elements; private int size; @SuppressWarnings("unchecked") public FilteredCollection(int capacity) { this.elements = (T[]) new Object[capacity]; this.size = 0; } public void add(T element) { if (size < elements.length) { elements[size++] = element; } } @Override public Iterator<T> iterator() { return new ArrayIterator(); } public Iterator<T> filteredIterator(Predicate<T> filter) { return new FilteredIterator(filter); } private class ArrayIterator implements Iterator<T> { private int cursor = 0; @Override public boolean hasNext() { return cursor < size; } @Override public T next() { if (!hasNext()) { throw new NoSuchElementException(); } return elements[cursor++]; } } private class FilteredIterator implements Iterator<T> { private int cursor = 0; private final Predicate<T> filter; private T nextElement; public FilteredIterator(Predicate<T> filter) { this.filter = filter; findNext(); } private void findNext() { while (cursor < size) { T element = elements[cursor++]; if (filter.test(element)) { nextElement = element; return; } } nextElement = null; } @Override public boolean hasNext() { return nextElement != null; } @Override public T next() { if (!hasNext()) { throw new NoSuchElementException(); } T result = nextElement; findNext(); return result; } } }

Usage Example:

public class FilteredExample { public static void main(String[] args) { FilteredCollection<Integer> numbers = new FilteredCollection<>(10); for (int i = 1; i <= 10; i++) { numbers.add(i); } System.out.println("Even numbers:"); Iterator<Integer> evenIterator = numbers.filteredIterator(n -> n % 2 == 0); while (evenIterator.hasNext()) { System.out.print(evenIterator.next() + " "); } System.out.println("\n\nNumbers greater than 5:"); Iterator<Integer> greaterThan5 = numbers.filteredIterator(n -> n > 5); while (greaterThan5.hasNext()) { System.out.print(greaterThan5.next() + " "); } } }

Best Practices for Iterator Implementation

1. Fail-Fast vs. Fail-Safe:

• Fail-Fast: Throw ConcurrentModificationException if collection is modified during iteration
• Fail-Safe: Work on a snapshot of the collection

1. Immutable Iterators: Consider making iterators immutable for thread safety
2. Resource Management: Ensure iterators don't hold resources indefinitely
3. Lazy Evaluation: For large collections, compute elements on-demand
4. State Validation: Check for illegal state transitions in remove() operations

// Example of fail-fast iterator private class FailFastIterator implements Iterator<T> { private int expectedModCount = modCount; private int cursor = 0; private void checkForComodification() { if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } } @Override public boolean hasNext() { checkForComodification(); return cursor < size; } @Override public T next() { checkForComodification(); if (!hasNext()) { throw new NoSuchElementException(); } return elements[cursor++]; } }

Conclusion

The Iterator Pattern is essential for creating professional-grade custom collections in Java. By implementing this pattern, you:

1. Enable Seamless Integration: Your collections work with enhanced for-loops and streaming APIs
2. Maintain Encapsulation: Hide internal data structure details from clients
3. Support Multiple Traversal Strategies: Different iterators for different needs
4. Improve Code Reusability: Standard interface across all collections
5. Enhance Flexibility: Easy to add new traversal algorithms

Whether you're building simple arrays, complex trees, or specialized data structures, implementing the Iterator Pattern ensures your collections are robust, maintainable, and developer-friendly. The pattern's power lies in its simplicity and the standardization it brings to collection traversal in Java.