Iterators

This chapter is about iterators. An iterator is an object that visits the elements of a data structure one at a time, and it is what lets Java’s enhanced for loop work on a Set.

After reading this chapter, you should be able to:

• Make a data structure work in an enhanced for loop by implementing Iterable<T> and writing its iterator, with hasNext() and next(), for an array-backed and a node-backed structure
• Distinguish Iterable from Iterator, and explain why each call to iterator() starts an independent traversal
• Choose between a static nested class and an inner class based on whether the class needs its enclosing instance
• Analyze an iteration as $O(n)$ time and $O(1)$ auxiliary space
• Test an iterator in the shared abstract SetTest for element coverage, empty sets, exhaustion, and independent traversals
• Explain why adding or removing an element during an iteration breaks an iterator that tracks its position with a cursor or a current node
• Make an iterator fail fast with a modCount, so it throws ConcurrentModificationException when the set changes during the iteration

You can download the accompanying code for this chapter: starter and solution.

Sections

1. Visiting Every Element
2. Making a Set Iterable
3. Borrowing an Iterator
4. Writing the ArraySet Iterator
5. Tracing the ArraySet Iterator
6. The Cost of Iterating
7. Iterable and Iterator
8. The LinkedSet Iterator
9. Inner Classes and Static Nested Classes
10. Testing the Iterator
11. Modifying a Set While Iterating
12. Failing Fast