Iterator Pattern - Providing Sequential Access Without Exposing Internal Structure
Learning Objectives: By the end of this lesson, you will be able to:
- Understand the Iterator pattern and how it provides unified access to different data structures
- Implement external and internal iterators with proper encapsulation
- Apply Iterator pattern to custom collections, tree traversals, and streaming data
- Design robust iterators that handle concurrent modification and provide fail-fast behavior
- Create specialized iterators for filtering, transformation, and complex traversal strategies
1. Welcome and Introduction (5 minutes)
Icebreaker Activity
Think about reading a book page by page, listening to songs in a playlist, or browsing photos in an album. In each case, you’re accessing items one at a time in sequence, but you don’t need to know how the book pages are bound, how the playlist is stored, or how photos are organized on disk. How would you design a system that allows uniform sequential access to different types of collections?
Lesson Overview
- Duration: 120 minutes
- Prerequisites: Object-oriented programming, understanding of collections and data structures
- Materials Needed: Development environment with Java, Python, or JavaScript support
2. Learning Objectives and Session Outline (5 minutes)
What We’ll Cover Today:
- Iterator Fundamentals - Understanding external vs internal iterators and their trade-offs
- Implementation Patterns - Building iterators for different data structures and traversal methods
- Fail-Fast Behavior - Handling concurrent modifications and ensuring iterator consistency
- Advanced Iterators - Filtering, transformation, lazy evaluation, and streaming
- Real-world Applications - Database cursors, file processing, tree traversal, pagination
- Performance Considerations - Memory efficiency, lazy loading, and optimization strategies
Success Criteria:
By the end of this session, you should be able to implement iterators for custom data structures and choose appropriate iterator patterns for different scenarios.
3. Foundation Knowledge (15-20 minutes)
Core Concepts
What is the Iterator Pattern?
The Iterator pattern provides a way to access elements of a collection sequentially without exposing the underlying representation. It encapsulates the traversal logic and provides a uniform interface for accessing different types of collections.
Real-World Analogy: Think of a remote control for a TV or music player. The remote provides “next channel,” “previous channel,” “next song,” “previous song” buttons without you needing to understand how channels or songs are stored or organized internally. The interface is consistent regardless of the underlying storage mechanism.
Why This Matters: Iterator pattern separates collection traversal from the collection’s internal structure, allowing you to change how data is stored without affecting client code that traverses the data.
External vs Internal Iterators
- External Iterator: Client controls iteration (hasNext(), next() pattern)
- Internal Iterator: Collection controls iteration (forEach with callback pattern)
Key Components
- Iterator Interface: Defines methods for traversing a collection
- Concrete Iterator: Implements traversal for a specific collection
- Aggregate Interface: Defines method for creating iterators
- Concrete Aggregate: Implements the collection and iterator creation
Key Terminology
- Current Position: Iterator’s current location in the collection
- Fail-Fast: Iterator detects concurrent modifications and throws exceptions
- Lazy Evaluation: Elements are computed on-demand during iteration
- Streaming: Processing elements one at a time without loading entire collection
- Cursor: Another term for iterator, especially in database contexts
- Bidirectional Iterator: Supports both forward and backward traversal
4. Detailed Explanation and Examples (25-30 minutes)
Understanding Iterator Pattern Structure
The Iterator pattern is essential when:
- You need to traverse different types of collections uniformly
- You want to hide the internal structure of complex data types
- You need multiple simultaneous traversals of the same collection
- You want to provide different traversal strategies for the same data
- You need to implement lazy evaluation or streaming processing
Practical Applications
Iterator pattern is commonly used for:
- Database Systems: Result set cursors, query result iteration
- File Processing: Line-by-line reading, streaming large files
- Tree Structures: Depth-first, breadth-first, pre-order, post-order traversals
- Web APIs: Pagination, infinite scrolling, batched data processing
- Game Development: Entity iteration, spatial partitioning traversal
- UI Frameworks: Widget tree traversal, event propagation
Common Misconceptions
-
Misconception: Iterator pattern is only for linear collections Reality: Can iterate over any data structure including trees, graphs, and hierarchical data
-
Misconception: All iterators must support removal Reality: Some iterators are read-only and don’t support modification operations
5. Live Coding Demonstration (20-25 minutes)
Example 1: Custom Collection with Multiple Iterator Types
// Iterator interface
interface Iterator<T> {
boolean hasNext();
T next();
void remove();
void reset();
}
// Bidirectional iterator interface
interface BidirectionalIterator<T> extends Iterator<T> {
boolean hasPrevious();
T previous();
}
// Custom collection: Circular Buffer
class CircularBuffer<T> implements Iterable<T> {
private T[] buffer;
private int head;
private int tail;
private int size;
private int capacity;
private int modificationCount;
@SuppressWarnings("unchecked")
public CircularBuffer(int capacity) {
this.capacity = capacity;
this.buffer = (T[]) new Object[capacity];
this.head = 0;
this.tail = 0;
this.size = 0;
this.modificationCount = 0;
}
public void add(T item) {
buffer[tail] = item;
tail = (tail + 1) % capacity;
if (size < capacity) {
size++;
} else {
head = (head + 1) % capacity; // Overwrite oldest element
}
modificationCount++;
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == capacity;
}
public int size() {
return size;
}
public int getCapacity() {
return capacity;
}
public int getModificationCount() {
return modificationCount;
}
// Default iterator (forward)
@Override
public Iterator<T> iterator() {
return new ForwardIterator();
}
// Reverse iterator
public Iterator<T> reverseIterator() {
return new ReverseIterator();
}
// Bidirectional iterator
public BidirectionalIterator<T> bidirectionalIterator() {
return new BiDirectionalIterator();
}
// Forward Iterator Implementation
private class ForwardIterator implements Iterator<T> {
private int currentIndex;
private int elementsReturned;
private int expectedModCount;
private boolean canRemove;
public ForwardIterator() {
this.currentIndex = head;
this.elementsReturned = 0;
this.expectedModCount = modificationCount;
this.canRemove = false;
}
@Override
public boolean hasNext() {
checkForComodification();
return elementsReturned < size;
}
@Override
public T next() {
checkForComodification();
if (!hasNext()) {
throw new NoSuchElementException("No more elements");
}
T element = buffer[currentIndex];
currentIndex = (currentIndex + 1) % capacity;
elementsReturned++;
canRemove = true;
return element;
}
@Override
public void remove() {
checkForComodification();
if (!canRemove) {
throw new IllegalStateException("remove() can only be called after next()");
}
// For simplicity, we'll mark as null instead of actually removing
// Real implementation would shift elements
int removeIndex = (currentIndex - 1 + capacity) % capacity;
buffer[removeIndex] = null;
canRemove = false;
expectedModCount = ++modificationCount;
}
@Override
public void reset() {
this.currentIndex = head;
this.elementsReturned = 0;
this.expectedModCount = modificationCount;
this.canRemove = false;
}
private void checkForComodification() {
if (modificationCount != expectedModCount) {
throw new ConcurrentModificationException("Collection modified during iteration");
}
}
}
// Reverse Iterator Implementation
private class ReverseIterator implements Iterator<T> {
private int currentIndex;
private int elementsReturned;
private int expectedModCount;
private boolean canRemove;
public ReverseIterator() {
this.currentIndex = (tail - 1 + capacity) % capacity;
this.elementsReturned = 0;
this.expectedModCount = modificationCount;
this.canRemove = false;
}
@Override
public boolean hasNext() {
checkForComodification();
return elementsReturned < size;
}
@Override
public T next() {
checkForComodification();
if (!hasNext()) {
throw new NoSuchElementException("No more elements");
}
T element = buffer[currentIndex];
currentIndex = (currentIndex - 1 + capacity) % capacity;
elementsReturned++;
canRemove = true;
return element;
}
@Override
public void remove() {
checkForComodification();
if (!canRemove) {
throw new IllegalStateException("remove() can only be called after next()");
}
int removeIndex = (currentIndex + 1) % capacity;
buffer[removeIndex] = null;
canRemove = false;
expectedModCount = ++modificationCount;
}
@Override
public void reset() {
this.currentIndex = (tail - 1 + capacity) % capacity;
this.elementsReturned = 0;
this.expectedModCount = modificationCount;
this.canRemove = false;
}
private void checkForComodification() {
if (modificationCount != expectedModCount) {
throw new ConcurrentModificationException("Collection modified during iteration");
}
}
}
// Bidirectional Iterator Implementation
private class BiDirectionalIterator implements BidirectionalIterator<T> {
private int currentIndex;
private int position; // Logical position in the collection
private int expectedModCount;
private boolean canRemove;
private boolean lastMoveWasNext;
public BiDirectionalIterator() {
this.currentIndex = head;
this.position = 0;
this.expectedModCount = modificationCount;
this.canRemove = false;
this.lastMoveWasNext = true;
}
@Override
public boolean hasNext() {
checkForComodification();
return position < size;
}
@Override
public boolean hasPrevious() {
checkForComodification();
return position > 0;
}
@Override
public T next() {
checkForComodification();
if (!hasNext()) {
throw new NoSuchElementException("No more elements");
}
T element = buffer[currentIndex];
currentIndex = (currentIndex + 1) % capacity;
position++;
canRemove = true;
lastMoveWasNext = true;
return element;
}
@Override
public T previous() {
checkForComodification();
if (!hasPrevious()) {
throw new NoSuchElementException("No previous elements");
}
currentIndex = (currentIndex - 1 + capacity) % capacity;
position--;
T element = buffer[currentIndex];
canRemove = true;
lastMoveWasNext = false;
return element;
}
@Override
public void remove() {
checkForComodification();
if (!canRemove) {
throw new IllegalStateException("remove() can only be called after next() or previous()");
}
int removeIndex = lastMoveWasNext ?
(currentIndex - 1 + capacity) % capacity : currentIndex;
buffer[removeIndex] = null;
if (!lastMoveWasNext) {
position--;
}
canRemove = false;
expectedModCount = ++modificationCount;
}
@Override
public void reset() {
this.currentIndex = head;
this.position = 0;
this.expectedModCount = modificationCount;
this.canRemove = false;
this.lastMoveWasNext = true;
}
private void checkForComodification() {
if (modificationCount != expectedModCount) {
throw new ConcurrentModificationException("Collection modified during iteration");
}
}
}
}
Example 2: Tree Iterator with Different Traversal Strategies
// Tree Node
class TreeNode<T> {
T data;
List<TreeNode<T>> children;
TreeNode<T> parent;
public TreeNode(T data) {
this.data = data;
this.children = new ArrayList<>();
this.parent = null;
}
public void addChild(TreeNode<T> child) {
children.add(child);
child.parent = this;
}
public void removeChild(TreeNode<T> child) {
children.remove(child);
child.parent = null;
}
public boolean isLeaf() {
return children.isEmpty();
}
public boolean isRoot() {
return parent == null;
}
// Getters
public T getData() { return data; }
public List<TreeNode<T>> getChildren() { return new ArrayList<>(children); }
public TreeNode<T> getParent() { return parent; }
}
// Tree with multiple iterator strategies
class Tree<T> {
private TreeNode<T> root;
private int size;
private int modificationCount;
public Tree(T rootData) {
this.root = new TreeNode<>(rootData);
this.size = 1;
this.modificationCount = 0;
}
public TreeNode<T> getRoot() {
return root;
}
public int size() {
return size;
}
public void addNode(TreeNode<T> parent, T data) {
TreeNode<T> newNode = new TreeNode<>(data);
parent.addChild(newNode);
size++;
modificationCount++;
}
public boolean removeNode(TreeNode<T> node) {
if (node == root) {
return false; // Cannot remove root
}
if (node.parent != null) {
node.parent.removeChild(node);
size -= countNodes(node);
modificationCount++;
return true;
}
return false;
}
private int countNodes(TreeNode<T> node) {
int count = 1;
for (TreeNode<T> child : node.children) {
count += countNodes(child);
}
return count;
}
public int getModificationCount() {
return modificationCount;
}
// Depth-First Pre-order Iterator
public Iterator<T> depthFirstIterator() {
return new DepthFirstIterator();
}
// Breadth-First Iterator
public Iterator<T> breadthFirstIterator() {
return new BreadthFirstIterator();
}
// Leaf-only Iterator
public Iterator<T> leafIterator() {
return new LeafIterator();
}
// Level-order Iterator (with level information)
public Iterator<LevelNode<T>> levelOrderIterator() {
return new LevelOrderIterator();
}
// Depth-First Pre-order Iterator Implementation
private class DepthFirstIterator implements Iterator<T> {
private Stack<TreeNode<T>> stack;
private int expectedModCount;
public DepthFirstIterator() {
this.stack = new Stack<>();
this.expectedModCount = modificationCount;
if (root != null) {
stack.push(root);
}
}
@Override
public boolean hasNext() {
checkForComodification();
return !stack.isEmpty();
}
@Override
public T next() {
checkForComodification();
if (!hasNext()) {
throw new NoSuchElementException("No more elements");
}
TreeNode<T> current = stack.pop();
// Add children in reverse order for correct DFS order
List<TreeNode<T>> children = current.getChildren();
for (int i = children.size() - 1; i >= 0; i--) {
stack.push(children.get(i));
}
return current.getData();
}
@Override
public void remove() {
throw new UnsupportedOperationException("Remove not supported for tree iterator");
}
@Override
public void reset() {
this.stack.clear();
this.expectedModCount = modificationCount;
if (root != null) {
stack.push(root);
}
}
private void checkForComodification() {
if (modificationCount != expectedModCount) {
throw new ConcurrentModificationException("Tree modified during iteration");
}
}
}
// Breadth-First Iterator Implementation
private class BreadthFirstIterator implements Iterator<T> {
private Queue<TreeNode<T>> queue;
private int expectedModCount;
public BreadthFirstIterator() {
this.queue = new LinkedList<>();
this.expectedModCount = modificationCount;
if (root != null) {
queue.offer(root);
}
}
@Override
public boolean hasNext() {
checkForComodification();
return !queue.isEmpty();
}
@Override
public T next() {
checkForComodification();
if (!hasNext()) {
throw new NoSuchElementException("No more elements");
}
TreeNode<T> current = queue.poll();
// Add all children to queue
for (TreeNode<T> child : current.getChildren()) {
queue.offer(child);
}
return current.getData();
}
@Override
public void remove() {
throw new UnsupportedOperationException("Remove not supported for tree iterator");
}
@Override
public void reset() {
this.queue.clear();
this.expectedModCount = modificationCount;
if (root != null) {
queue.offer(root);
}
}
private void checkForComodification() {
if (modificationCount != expectedModCount) {
throw new ConcurrentModificationException("Tree modified during iteration");
}
}
}
// Leaf Iterator Implementation
private class LeafIterator implements Iterator<T> {
private Stack<TreeNode<T>> stack;
private TreeNode<T> nextLeaf;
private int expectedModCount;
public LeafIterator() {
this.stack = new Stack<>();
this.expectedModCount = modificationCount;
if (root != null) {
stack.push(root);
findNextLeaf();
}
}
@Override
public boolean hasNext() {
checkForComodification();
return nextLeaf != null;
}
@Override
public T next() {
checkForComodification();
if (!hasNext()) {
throw new NoSuchElementException("No more leaf elements");
}
T data = nextLeaf.getData();
findNextLeaf();
return data;
}
private void findNextLeaf() {
nextLeaf = null;
while (!stack.isEmpty() && nextLeaf == null) {
TreeNode<T> current = stack.pop();
if (current.isLeaf()) {
nextLeaf = current;
} else {
// Add children in reverse order
List<TreeNode<T>> children = current.getChildren();
for (int i = children.size() - 1; i >= 0; i--) {
stack.push(children.get(i));
}
}
}
}
@Override
public void remove() {
throw new UnsupportedOperationException("Remove not supported for leaf iterator");
}
@Override
public void reset() {
this.stack.clear();
this.expectedModCount = modificationCount;
if (root != null) {
stack.push(root);
findNextLeaf();
}
}
private void checkForComodification() {
if (modificationCount != expectedModCount) {
throw new ConcurrentModificationException("Tree modified during iteration");
}
}
}
// Level-order with level information
static class LevelNode<T> {
T data;
int level;
public LevelNode(T data, int level) {
this.data = data;
this.level = level;
}
public T getData() { return data; }
public int getLevel() { return level; }
@Override
public String toString() {
return String.format("LevelNode{data=%s, level=%d}", data, level);
}
}
private class LevelOrderIterator implements Iterator<LevelNode<T>> {
private Queue<LevelNode<TreeNode<T>>> queue;
private int expectedModCount;
public LevelOrderIterator() {
this.queue = new LinkedList<>();
this.expectedModCount = modificationCount;
if (root != null) {
queue.offer(new LevelNode<>(root, 0));
}
}
@Override
public boolean hasNext() {
checkForComodification();
return !queue.isEmpty();
}
@Override
public LevelNode<T> next() {
checkForComodification();
if (!hasNext()) {
throw new NoSuchElementException("No more elements");
}
LevelNode<TreeNode<T>> current = queue.poll();
TreeNode<T> node = current.getData();
int level = current.getLevel();
// Add children with incremented level
for (TreeNode<T> child : node.getChildren()) {
queue.offer(new LevelNode<>(child, level + 1));
}
return new LevelNode<>(node.getData(), level);
}
@Override
public void remove() {
throw new UnsupportedOperationException("Remove not supported for level-order iterator");
}
@Override
public void reset() {
this.queue.clear();
this.expectedModCount = modificationCount;
if (root != null) {
queue.offer(new LevelNode<>(root, 0));
}
}
private void checkForComodification() {
if (modificationCount != expectedModCount) {
throw new ConcurrentModificationException("Tree modified during iteration");
}
}
}
}
Example 3: Filtering and Transforming Iterators
// Filtering Iterator
class FilteringIterator<T> implements Iterator<T> {
private Iterator<T> sourceIterator;
private Predicate<T> filter;
private T nextElement;
private boolean hasNextElement;
public FilteringIterator(Iterator<T> sourceIterator, Predicate<T> filter) {
this.sourceIterator = sourceIterator;
this.filter = filter;
this.hasNextElement = false;
findNext();
}
@Override
public boolean hasNext() {
return hasNextElement;
}
@Override
public T next() {
if (!hasNext()) {
throw new NoSuchElementException("No more filtered elements");
}
T result = nextElement;
findNext();
return result;
}
private void findNext() {
hasNextElement = false;
while (sourceIterator.hasNext()) {
T candidate = sourceIterator.next();
if (filter.test(candidate)) {
nextElement = candidate;
hasNextElement = true;
break;
}
}
}
@Override
public void remove() {
sourceIterator.remove();
}
@Override
public void reset() {
sourceIterator.reset();
hasNextElement = false;
findNext();
}
}
// Transforming Iterator
class TransformingIterator<T, R> implements Iterator<R> {
private Iterator<T> sourceIterator;
private Function<T, R> transformer;
public TransformingIterator(Iterator<T> sourceIterator, Function<T, R> transformer) {
this.sourceIterator = sourceIterator;
this.transformer = transformer;
}
@Override
public boolean hasNext() {
return sourceIterator.hasNext();
}
@Override
public R next() {
if (!hasNext()) {
throw new NoSuchElementException("No more elements to transform");
}
T sourceElement = sourceIterator.next();
return transformer.apply(sourceElement);
}
@Override
public void remove() {
sourceIterator.remove();
}
@Override
public void reset() {
sourceIterator.reset();
}
}
// Combining Iterator (for multiple collections)
class CombiningIterator<T> implements Iterator<T> {
private List<Iterator<T>> iterators;
private int currentIteratorIndex;
@SafeVarargs
public CombiningIterator(Iterator<T>... iterators) {
this.iterators = Arrays.asList(iterators);
this.currentIteratorIndex = 0;
moveToNextValidIterator();
}
@Override
public boolean hasNext() {
return currentIteratorIndex < iterators.size() &&
iterators.get(currentIteratorIndex).hasNext();
}
@Override
public T next() {
if (!hasNext()) {
throw new NoSuchElementException("No more elements in combined iterators");
}
T result = iterators.get(currentIteratorIndex).next();
if (!iterators.get(currentIteratorIndex).hasNext()) {
currentIteratorIndex++;
moveToNextValidIterator();
}
return result;
}
private void moveToNextValidIterator() {
while (currentIteratorIndex < iterators.size() &&
!iterators.get(currentIteratorIndex).hasNext()) {
currentIteratorIndex++;
}
}
@Override
public void remove() {
if (currentIteratorIndex < iterators.size()) {
iterators.get(currentIteratorIndex).remove();
}
}
@Override
public void reset() {
for (Iterator<T> iterator : iterators) {
iterator.reset();
}
currentIteratorIndex = 0;
moveToNextValidIterator();
}
}
// Pagination Iterator
class PaginationIterator<T> implements Iterator<T> {
private List<T> data;
private int pageSize;
private int currentPage;
private int currentIndex;
public PaginationIterator(List<T> data, int pageSize) {
this.data = data;
this.pageSize = pageSize;
this.currentPage = 0;
this.currentIndex = 0;
}
@Override
public boolean hasNext() {
return currentIndex < data.size();
}
@Override
public T next() {
if (!hasNext()) {
throw new NoSuchElementException("No more elements");
}
return data.get(currentIndex++);
}
public List<T> nextPage() {
List<T> page = new ArrayList<>();
int pageStart = currentPage * pageSize;
int pageEnd = Math.min(pageStart + pageSize, data.size());
for (int i = pageStart; i < pageEnd; i++) {
page.add(data.get(i));
}
currentPage++;
return page;
}
public boolean hasNextPage() {
return currentPage * pageSize < data.size();
}
public int getCurrentPage() {
return currentPage;
}
public int getTotalPages() {
return (int) Math.ceil((double) data.size() / pageSize);
}
@Override
public void remove() {
throw new UnsupportedOperationException("Remove not supported for pagination iterator");
}
@Override
public void reset() {
currentPage = 0;
currentIndex = 0;
}
}
Example 4: Usage Demonstrations
public class IteratorPatternDemo {
public static void demonstrateCircularBuffer() {
System.out.println("=== Circular Buffer Iterator Demo ===");
CircularBuffer<String> buffer = new CircularBuffer<>(5);
// Add elements
buffer.add("First");
buffer.add("Second");
buffer.add("Third");
buffer.add("Fourth");
buffer.add("Fifth");
buffer.add("Sixth"); // This will overwrite "First"
System.out.println("Forward iteration:");
Iterator<String> forward = buffer.iterator();
while (forward.hasNext()) {
System.out.println(" " + forward.next());
}
System.out.println("\nReverse iteration:");
Iterator<String> reverse = buffer.reverseIterator();
while (reverse.hasNext()) {
System.out.println(" " + reverse.next());
}
System.out.println("\nBidirectional iteration:");
BidirectionalIterator<String> bidirectional = buffer.bidirectionalIterator();
// Go forward 3 steps
System.out.println("Forward 3 steps:");
for (int i = 0; i < 3; i++) {
if (bidirectional.hasNext()) {
System.out.println(" " + bidirectional.next());
}
}
// Go backward 2 steps
System.out.println("Backward 2 steps:");
for (int i = 0; i < 2; i++) {
if (bidirectional.hasPrevious()) {
System.out.println(" " + bidirectional.previous());
}
}
}
public static void demonstrateTreeIterators() {
System.out.println("\n=== Tree Iterator Demo ===");
// Build a tree structure
Tree<String> tree = new Tree<>("Root");
TreeNode<String> root = tree.getRoot();
tree.addNode(root, "Child1");
tree.addNode(root, "Child2");
tree.addNode(root, "Child3");
TreeNode<String> child1 = root.getChildren().get(0);
TreeNode<String> child2 = root.getChildren().get(1);
tree.addNode(child1, "Grandchild1");
tree.addNode(child1, "Grandchild2");
tree.addNode(child2, "Grandchild3");
TreeNode<String> grandchild1 = child1.getChildren().get(0);
tree.addNode(grandchild1, "GreatGrandchild1");
System.out.println("Depth-First traversal:");
Iterator<String> dfs = tree.depthFirstIterator();
while (dfs.hasNext()) {
System.out.println(" " + dfs.next());
}
System.out.println("\nBreadth-First traversal:");
Iterator<String> bfs = tree.breadthFirstIterator();
while (bfs.hasNext()) {
System.out.println(" " + bfs.next());
}
System.out.println("\nLeaf-only traversal:");
Iterator<String> leaves = tree.leafIterator();
while (leaves.hasNext()) {
System.out.println(" " + leaves.next());
}
System.out.println("\nLevel-order with levels:");
Iterator<Tree.LevelNode<String>> levelOrder = tree.levelOrderIterator();
while (levelOrder.hasNext()) {
Tree.LevelNode<String> levelNode = levelOrder.next();
System.out.println(" Level " + levelNode.getLevel() + ": " + levelNode.getData());
}
}
public static void demonstrateFilteringAndTransforming() {
System.out.println("\n=== Filtering and Transforming Iterator Demo ===");
CircularBuffer<Integer> numbers = new CircularBuffer<>(10);
for (int i = 1; i <= 10; i++) {
numbers.add(i);
}
// Filter even numbers
System.out.println("Even numbers:");
Iterator<Integer> evenNumbers = new FilteringIterator<>(
numbers.iterator(),
n -> n % 2 == 0
);
while (evenNumbers.hasNext()) {
System.out.println(" " + evenNumbers.next());
}
// Transform numbers to their squares
System.out.println("\nSquared numbers:");
Iterator<Integer> squaredNumbers = new TransformingIterator<>(
numbers.iterator(),
n -> n * n
);
while (squaredNumbers.hasNext()) {
System.out.println(" " + squaredNumbers.next());
}
// Combine filtering and transforming
System.out.println("\nSquares of even numbers:");
Iterator<Integer> filtered = new FilteringIterator<>(numbers.iterator(), n -> n % 2 == 0);
Iterator<Integer> transformed = new TransformingIterator<>(filtered, n -> n * n);
while (transformed.hasNext()) {
System.out.println(" " + transformed.next());
}
}
public static void demonstratePagination() {
System.out.println("\n=== Pagination Iterator Demo ===");
List<String> largeDataset = new ArrayList<>();
for (int i = 1; i <= 23; i++) {
largeDataset.add("Item " + i);
}
PaginationIterator<String> paginator = new PaginationIterator<>(largeDataset, 5);
System.out.println("Total pages: " + paginator.getTotalPages());
while (paginator.hasNextPage()) {
List<String> page = paginator.nextPage();
System.out.println("Page " + paginator.getCurrentPage() + ": " + page);
}
}
public static void main(String[] args) {
demonstrateCircularBuffer();
demonstrateTreeIterators();
demonstrateFilteringAndTransforming();
demonstratePagination();
}
}
6. Hands-On Practice (30-40 minutes)
Exercise 1: Basic Practice (10 minutes)
Objective: Implement a basic iterator for a custom linked list
Instructions:
- Create a simple LinkedList class with Node inner class
- Implement an iterator that supports hasNext(), next(), and remove()
- Add fail-fast behavior for concurrent modifications
- Test iteration and removal operations
Starter Code:
class CustomLinkedList<T> implements Iterable<T> {
private Node<T> head;
private int size;
private int modificationCount;
private static class Node<T> {
T data;
Node<T> next;
Node(T data) {
this.data = data;
}
}
// TODO: Implement add, remove, iterator methods
}
Exercise 2: Intermediate Challenge (15 minutes)
Objective: Build a matrix iterator with different traversal patterns
Requirements:
- Create a 2D matrix class with row-major and column-major iterators
- Implement diagonal iterator (both main and anti-diagonal)
- Add spiral iterator (clockwise from outside to inside)
- Support boundary checking and proper hasNext()/next() behavior
Hints:
- Consider using different index calculation strategies for each traversal
- Think about how to handle rectangular (non-square) matrices
- Plan the iteration boundaries carefully for spiral traversal
Exercise 3: Creative Application (15 minutes)
Objective: Design a playlist iterator with advanced features
Challenge: Create a music playlist iterator that supports:
- Normal sequential playback
- Shuffle mode (random order without repeats)
- Repeat modes (repeat all, repeat one)
- Skip behavior based on user preferences
- Smart playlist features (skip songs under certain duration, etc.)
Extension Ideas:
- Add crossfade iterator that overlaps songs
- Implement mood-based filtering
- Support dynamic playlist modification during iteration
7. Common Pitfalls and Troubleshooting (10 minutes)
Frequent Mistakes
-
Problem: Iterator state becomes inconsistent after collection modification Cause: Not implementing proper fail-fast behavior Solution: Track modification count and check in hasNext()/next()
-
Problem: hasNext() modifies iterator state Cause: Implementing lazy evaluation incorrectly in hasNext() Solution: Use separate state variables and compute next element in advance
-
Problem: Memory leaks in iterators holding references to large collections Cause: Iterator keeps reference to entire collection Solution: Use weak references or implement proper cleanup
Debugging Tips
- Log iterator state (current position, modification count) for debugging
- Implement comprehensive toString() methods for iterator state
- Use assertions to validate iterator invariants
- Test with edge cases like empty collections and single-element collections
8. Best Practices and Professional Tips (5 minutes)
Industry Standards
- Implement fail-fast behavior for collections that can be modified during iteration
- Follow naming conventions (hasNext, next, remove are standard)
- Document iterator behavior clearly, especially regarding modification
- Consider thread safety for concurrent environments
Design Principles
- Keep iterators lightweight - avoid expensive operations in hasNext()
- Make iterators stateless when possible - easier to reason about and test
- Implement lazy evaluation for expensive computations
- Provide reset capability when it makes sense
Performance Considerations
- Optimize for common access patterns - sequential access should be fast
- Use appropriate data structures for backing storage
- Consider caching for expensive iterator operations
- Profile iterator performance especially for large datasets
Next Steps in Your Learning Journey
- Study Stream APIs as modern alternatives to traditional iteration
- Learn Reactive Streams for asynchronous and backpressure-aware iteration
- Explore Generator functions in languages that support them
- Investigate Database cursor patterns for large dataset iteration
9. Summary and Review (5 minutes)
Key Takeaways
- Iterator pattern provides uniform access to different collection types
- Encapsulates traversal logic and hides internal collection structure
- Supports multiple simultaneous iterations of the same collection
- Enables lazy evaluation and streaming for efficient processing
Quick Review Questions
- What’s the difference between external and internal iterators?
- When would you implement a custom iterator instead of using built-in ones?
- How do you handle concurrent modifications in iterator implementations?
For Instructors
Teaching Tips
- Start with simple linear collections before complex tree structures
- Show fail-fast behavior in action with concurrent modification examples
- Demonstrate multiple iterators on the same collection simultaneously
- Compare with modern stream APIs to show evolution of the pattern
- Use visual aids to show different traversal patterns on trees
Common Student Questions
- “Why not just use for-each loops?” - Explain custom traversal strategies and complex data structures
- “When do I need custom iterators?” - Discuss cases where built-in iterators aren’t sufficient
- “How do streams relate to iterators?” - Show how streams build on iterator concepts
Assessment Ideas
- Implementation challenge: Create iterator for specific data structure (graph, priority queue)
- Performance comparison: Compare different traversal strategies for the same data
- Refactoring exercise: Convert loop-based traversal code to use iterators
Adaptation Notes
- Beginner focus: Emphasize the basic hasNext()/next() pattern before advanced features
- Advanced students: Discuss concurrent iterators, parallel iteration, and performance optimization
- Language-specific: Show language-specific iterator features (Python generators, JavaScript iterables)
- Time management: Tree iterator examples can be simplified or extended based on available time