UNC COMP 301 - F26/Lec 9 - Iterator Design Pattern

Overview

Muhammad Sayeed Ghani explains Java's Iterator design pattern as a way to traverse collections while hiding implementation details, focusing on the Iterable and Iterator interfaces, enhanced for-loops, exception behavior, and collection mutation rules. The lecture then develops three custom-iterator strategies—direct traversal, sorted internal copies, and iterator composition—and compares their space and time trade-offs using array lists, sets, maps, and a lazily alphabetized string collection.

Key takeaways

Java's Iterable interface exposes iterator(), while Iterator<T> supplies hasNext() and next(); together they hide whether data comes from an ArrayList, Set, tree, or another collection.
A Map is not directly Iterable because each entry contains a key-value pair, but keySet() and values() expose separately iterable views; keys are unique while values may duplicate.
Built-in collection iterators generally throw ConcurrentModificationException after external structural changes, while Iterator.remove() provides a supported way to remove the most recently returned element.
A cursor-based custom iterator uses O(1) additional space, but retaining the source collection makes ordered traversal difficult and leaves behavior dependent on external mutations.
Cloning and sorting an internal collection simplifies ordered iteration and isolates mutations, but it costs O(n) space and may waste time when only a few results are requested.
The lazy Alphabetizer demonstrates a third trade-off: it preserves O(1) space and can produce only the requested prefix, but its repeated scans lead to O(n²) worst-case time.

Chapters

0:00 Iterator Pattern Introduced Alongside Midterm Scope

Muhammad Sayeed Ghani states that the Thursday midterm excludes the current iterator lecture and the design-pattern section from the previous lecture.
The lecture introduces Java's Iterator design pattern as the first design pattern to be completed before the next pattern after exams.
The main goals are distinguishing Iterable from Iterator, using built-in iterators, and designing custom iterators.

5:00 Iterable Encapsulates Collection Implementation Details

The Iterator pattern lets clients access collection elements without exposing whether the collection is an ArrayList, HashMap, linked list, binary tree, or another structure.
Java collection types such as List, Set, and Queue implement Iterable, which requires an iterator() method.
Iterable is compared with Java's Comparable interface from COMP 210, where implementing classes must provide compareTo().

10:00 Iterator API: hasNext() and next()

Java's Iterator<T> interface primarily provides hasNext(), returning whether an unseen element remains, and next(), returning the next T value.
The iterator encapsulates how the next element is located, allowing client code to avoid array indices, tree traversal logic, or hash-table internals.
The collection supplies an Iterator<T> through its iterator() method, with the iterator's generic type matching the collection's element type.

15:00 Built-In Iterators for Lists, Sets, and Maps

An ArrayList<Integer> can produce an Iterator<Integer> directly through numbers.iterator(), while a TreeSet<Integer> exposes the same iterator-based API.
A Map is not itself Iterable because each entry contains a key-value pair rather than one standalone element.
HashMap keys can be traversed through keySet(), which is a Set, and values through values(), which is a Collection; keys are unique while values may repeat.
Inserting a new value under an existing HashMap key replaces the old value.

20:00 Enhanced For-Loops as Iterator Syntactic Sugar

The explicit while-loop pattern while (iterator.hasNext()) { iterator.next(); } can be replaced by Java's enhanced for-loop.
An enhanced for-loop requires an Iterable aggregate and a loop variable whose type matches the collection's generic element type.
Java internally implements the enhanced for-loop using an iterator and repeated hasNext()/next() calls.
Enhanced for-loops simplify syntax but do not expose a reliable numeric index or guarantee a traversal order for unordered collections such as HashSet.

24:00 Iterator Boundary Errors and NoSuchElementException

Calling next() after hasNext() becomes false raises Java's unchecked NoSuchElementException rather than returning null.
The intended usage pattern checks hasNext() before calling next(), treating an exception as evidence of a programming error.
A client could catch NoSuchElementException to detect exhaustion, but a guarded loop is the preferred design.

28:00 Concurrent Modification and Iterator Removal

Java's built-in ArrayList iterator detects structural changes made to the collection after iterator creation and throws ConcurrentModificationException.
The restriction prevents the iterator's internal position from becoming inconsistent when elements are inserted or removed externally.
Iterator.remove() is a controlled exception: after retrieving an element with next(), the iterator may remove that element without triggering concurrent-modification failure.
Custom iterators are not required to enforce the same policy; their behavior depends on the implementation.

32:00 Independent Iterators Maintain Separate Cursors

Multiple iterators can be created over the same ArrayList without sharing traversal state.
If the first iterator consumes Alice and Bob, a second iterator created on the same list starts independently and can return Alice again.
Each iterator stores its own position, so advancing one iterator does not advance another.

36:00 Custom SimpleIterator with an Array Cursor

A custom SimpleIterator implementing Iterator<String> can encapsulate a String[] passed through its constructor.
A private cursor initialized to 0 identifies the next array position; elements before the cursor have already been returned.
hasNext() compares cursor against the array length, while next() checks hasNext(), saves the current element, increments cursor, and returns the saved value.
Calling next() after the cursor reaches the array length should produce NoSuchElementException.

41:00 Reference Semantics, final Fields, and Direct Traversal Trade-Offs

Declaring the encapsulated array reference final prevents reassignment but does not make the array contents immutable.
The first custom strategy retains a reference to the original collection rather than cloning it, giving O(1) additional space usage.
Direct-reference iterators can accidentally observe external collection changes and are harder to adapt for sorted or otherwise ordered traversal.
A custom iterator should not modify the original collection, even though an implementation could technically do so.

46:00 SortedIterator Uses an Internal Clone

The second strategy creates a sorted copy by cloning the input String[] and sorting the private copy.
The iterator then uses the same cursor, hasNext(), and next() logic as SimpleIterator but traverses the sorted copy.
Cloning changes additional space complexity from O(1) to O(n), where n is the collection size.
The copy isolates both sides: external changes do not affect iteration, and modifications to the internal copy do not affect the source collection.

52:00 Iterator Composition as the Third Custom Strategy

The third strategy builds one iterator on top of another iterator instead of directly traversing the raw collection.
An underlying iterator supplies hasNext() and next(), while a wrapper can filter, transform, or reorder the resulting sequence.
Composition reuses traversal work but can be difficult to implement because the full chain of underlying iterators must exist and interact correctly.
The approach is scheduled for use in Assignment 4 after the midterm.

56:00 Iterator Design Requirements and the Alphabetizer Problem

A custom iterator must track which elements have been seen and which remain, commonly through a cursor or equivalent state fields.
The Alphabetizer example must return an unordered String[] in alphabetical order without modifying the original collection.
Strategy 2 would solve the problem easily by sorting a clone, but the lecture deliberately uses Strategy 1 to preserve O(1) space.
Selection sort is introduced as a conceptual baseline, but its normal implementation swaps elements in the original array, which is prohibited here.

1:01:00 Alphabetizer State: Previous and Candidate Values

The O(1)-space Alphabetizer tracks a last value already returned and a next candidate value that has been selected for return.
The constructor stores the source collection and initializes last and next to null because no element has yet been returned or selected.
To find the next alphabetical element without rearranging the array, the iterator scans the entire collection and compares candidates against the previous output.
The first selection has special handling because last is null and cannot be used directly in compareTo().

1:06:00 Caching hasNext() Results and Short-Circuit Evaluation

The Alphabetizer performs its expensive search in hasNext(), storing the selected element in next so repeated hasNext() calls do not repeat the scan.
next() returns the cached next value and then resets the next field to null, forcing a new search only after consumption.
The candidate-selection loop performs comparisons that ensure the chosen string is greater than the previous result and smaller than competing candidates.
Java's left-to-right short-circuit evaluation prevents compareTo() from being invoked on null when the first condition in an OR expression already succeeds.

1:11:00 Space-Time Trade-Offs Between Iterator Strategies

The O(1)-space Alphabetizer may require O(n²) time because each next element can scan the entire collection using a selection-sort-like process.
The cloned-and-sorted strategy can use a faster library sorting algorithm, commonly O(n log n), but pays O(n) memory and sorts the entire collection up front.
For a huge collection where only the first three alphabetical elements are needed, the lazy O(1)-space strategy can avoid sorting every element and perform roughly three scans.
Muhammad Sayeed Ghani concludes that direct traversal, cloned sorting, and iterator composition each balance implementation difficulty, memory, mutation isolation, ordering, and execution time differently.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Muhammad Sayeed Ghani.