UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 11.3 Free with a free account
Visiting Every Element of a Collection One at a Time
Data Structures and Algorithms · Chapter 11: Dynamic Lists, Iterators, and the Collections FrameworkSection 11.3 · lesson 46 of 8711 min · free with a free account
Free preview
Create a free account to keep watching
It takes a minute and costs nothing. Your free account unlocks all of Chapter 1 and 3 more lessons of Data Structures and Algorithms.
Lesson complete
Earn the 3 college credits for Data Structures and Algorithms
Enrolling adds a quiz after each lesson, the graded work and the official transcript. Recommended for credit by NCCRS.
Next lesson: A Tour of Java's Pre-Built Collection Tools →← Positional List OperationsNext lesson: A Tour of Java's Pre-Built Collection Tools →
In this lesson
How Java iterators walk lists, sets, maps and custom collections.
- Use hasNext, next and the iterator's remove to visit and delete elements safely
- Explain how fail-fast iterators detect changes and when they miss them
- Predict iteration order for HashSet, LinkedHashSet and TreeSet
- Implement Iterable with an inner-class iterator for a custom collection
Free study notes
Get this lesson's notes by email
The key points and 4 practice questions with answers, in your inbox. One email, free.
One email. Unsubscribe in one click.
Transcript
Everything said in the video, section by section (1,631 words). Read along, or search it.
Opening Question
Collections Without Positions
A set has no first, second or third element you can rely on. A map hands out pairs, not positions. Yet programs constantly need to do something with every element: print them, total them, discard the ones that fail a test. What every collection can do is hand out its elements one at a time. The object that does it is called an iterator. It works the same way for a list, a set, a map, and even a collection you write yourself.
Key Interfaces
Iterable Hands Out an Iterator
Two small interfaces from java util do the work. An Iterable is anything that can hand out an iterator: it has exactly one method, iterator. An Iterator does the walking. Think of it as a cursor sitting between elements. Has next asks whether another element lies ahead, without moving. Next returns that element, and moves the cursor past it. With nothing left, it throws a no such element exception. And remove deletes the element the last next returned. Call it without a fresh next, and it throws an illegal state exception.
Standard Pattern
Ask First, Then Take
The standard pattern asks first, and takes second. Calling next without checking has next is the usual cause of a no such element exception. Here the loop deletes every even number from three, eight, five, six, seven. It calls the iterator's own remove, on the number next just returned. That's the one safe way to delete while looping: one next, at most one remove. The result is three, five, seven. Remove if does the same in one call. And a fresh iterator that calls remove before any next throws an illegal state exception, as would a second remove after one next.
Shorthand
For-Each Hides the Iterator
The for-each loop is a shorthand. For anything Iterable, the compiler rewrites it into exactly that pattern: get an iterator, and loop while has next, taking each element with next. The shorthand has a cost. The iterator is hidden, so there's no variable on which to call remove. That tempts people to call the collection's own remove instead. And that's where trouble begins.
Common Mistake
Removing Inside a For-Each Loop
This loop deletes even numbers through the list's own remove, inside a for-each. The eight is removed, but on the next step, the loop throws a concurrent modification exception. The six is never removed: the list is left as three, five, six, seven. The name is misleading: no second thread is involved. It warns that the collection changed while an iterator was walking it. Collections that stop with an error, rather than keep walking a structure that shifted underneath them, are called fail-fast.
Mechanism
The Saved Change Count
Here's the mechanism. Every collection keeps a change count, which goes up whenever elements are added or removed. This list starts at zero. An iterator saves that count when it's created, and compares it on every call to next. Remove the eight through the list, and the list's count moves from zero to one, while the iterator still expects zero. The next call to next sees the difference, and throws.
Edge Case
Removing the Second From Last
The check lives inside next, and that produces a surprise. The same program tries removing one element of one through five, inside a for-each, at each position in turn. Removing one, two, three or five throws. But removing four, the second from last, throws nothing at all. After four goes, the cursor sits exactly at the new end of the list. Has next answers false, the loop stops quietly, and next, the only method that checks, is never called. So five is simply skipped. A crash is annoying, but a silent skip is worse. That's why the exception is a best-effort check, not a guarantee.
Quick Check
Removing Numbers Over Seven
Quick check. A list holds five, two, eight, three. A for-each loop removes every number over seven, through the list's own remove. Then the list is printed. What happens? Pause and predict. It prints five, two, three, with no exception. Eight is the second from last, so after it's removed, the cursor is at the new end. Has next says false, and the check in next never runs. Three was never even visited, though here that did no harm. An exception is what you'd get if any other element were over seven. And five, two, eight, three would mean the remove never happened.
Safe Deletion
Three Ways to Delete While Looping
So how do you delete safely while looping? Use the iterator's own remove: it deletes, and updates its own saved count. That suits loops that do other work per element too. Use remove if, when you delete everything that matches a condition: one call, and the collection runs the loop. Or collect the unwanted items in a second collection, and remove them after the loop ends, when the decision needs the whole loop first.
Set Order
Hash, Linked and Tree Set Order
A list remembers where each element was placed, so its iterator is predictable. A set promises only that it holds no duplicates. When each element comes out depends on the kind of set. Add banana, apple, cherry, date, elderberry and fig. A hash set gives banana, date, apple, cherry, fig, elderberry: an order you didn't choose. A linked hash set gives them back in insertion order. A tree set gives sorted order. The numbers forty-two, seven, nineteen, three, twenty-five behave the same way. The hash set says nineteen, three, seven, twenty-five, forty-two.
How It Works
Buckets Explain Hash Set Order
That order looks random, but it isn't. Each number goes into a numbered bucket, here its value mod sixteen, and the iterator scans the buckets from first to last. Nineteen and three share bucket three, and nineteen was added first, so it comes out first. Then seven, then twenty-five in bucket nine, and forty-two in bucket ten. So never depend on a hash set's or a hash map's order: adding more elements can rearrange it. For insertion order choose the linked version, and for sorted order, the tree version.
Map Views
Key Set, Values and Entry Set
Maps are visited through three views: key set, values, and entry set. Each view is itself iterable. This map holds pen, ink, pad and tape, with stock counts. The entry iterator removes every entry whose count is zero. Removing through a view's iterator removes the whole pair, so only pen and pad remain. But call the map's own remove inside a for-each over its keys, and it fails exactly as a list does: a concurrent modification exception. A full visit of n elements makes n calls to next, and n plus one to has next, the last one answering false. So the time is proportional to n.
Custom Iterator
Building an Iterable Bag
To let for-each walk a collection of your own, the collection implements Iterable, and its iterator method returns an object that implements Iterator. The example is a bag: an unordered collection that allows repeats, and has no positions. Its iterator is an inner class, declared inside the bag and not static. An inner object carries a hidden link to the bag that made it, so it can read the bag's private array and size directly. And every call to iterator builds a new one with its own cursor, so several loops can run over one bag at once. Next checks the change count, checks that something's left, records which slot it returns, and moves the cursor on. Remove is clever. Order doesn't matter in a bag, so instead of shifting later items left, it copies the last item into the gap, and shrinks the bag. But that moves an unvisited item into a slot the cursor already passed. So remove sets the cursor back to the gap, and the next call returns the moved item. Finally, it bumps the change count, and updates its own saved count, so this iterator stays in step. Trace it on a bag of A, B, C. Next twice gives A and B. Remove copies C into B's slot, and steps the cursor back, so next returns C, and then has next is false. Removing every even number from a bag of one to six visits all six values exactly once, in the order one, two, six, five, three, four. One, five and three are left. And because the bag is Iterable, two nested for-each loops each get their own iterator, and print one-two, one-three and two-three.
Quick Check
Next, Next, Remove, Next on a Bag
Quick check. The same bag holds A, B, C and D. An iterator calls next twice, then remove, then next once more. The program prints what that last next returned, and the bag. What's printed? Pause and predict. It prints D, then A, D, C. Remove deleted B, the last item returned, by copying D, the last item, into B's slot. Then it set the cursor back to that slot, so the next call returned D. C, with A, C, D, would be a list that shifts items left. And C, with A, D, C, forgets that the cursor stepped back, so D would have been skipped.
Checklist
Rules for Writing an Iterator
A short checklist for any iterator you write. Keep a cursor, and keep has next free of side effects. Next must advance the cursor, and throw no such element when nothing's left. Remove is optional. If you support it, delete only the element last returned, and throw illegal state otherwise. And to stay fail-fast, save the change count, and compare it in next.
Key Takeaways
Iterators and Fail-Fast Behavior
To sum up. An Iterable hands out an Iterator, which visits elements with has next and next. For-each is shorthand for an iterator loop, and hides the iterator. Changing the collection directly inside it usually throws a concurrent modification exception, but removing the second from last skips silently. Delete while looping with the iterator's remove, remove if, or by collecting first. And never rely on hash order. A custom iterator is naturally an inner class, with its own cursor.
Think About It
Why the Cursor Steps Back
Something to think about. In the bag iterator, remove sets the cursor back to the gap. If the cursor were left where it was, what would a loop that removes elements miss? And why would no exception warn you?
About Data Structures and Algorithms at UPI Study
Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.
Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →
Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms
Why take it here
Why students take Data Structures and Algorithms with UPI Study
Where the credit goes
Universities that work with NCCRS
Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Thomas Edison State UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks with NCCRS
+many more cooperating universitiesFind my college →Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.
FAQ
Questions students ask us
About Visiting Every Element of a Collection One at a Time
What is the difference between Iterable and Iterator in Java?
Why does removing from a list inside a for-each loop throw ConcurrentModificationException?
How do you safely remove elements from a Java collection while iterating?
Why does a HashSet print elements in a different order than they were added?
About the Data Structures and Algorithms course
How many college credits is Data Structures and Algorithms?
How much does Data Structures and Algorithms cost and what is included?
Which universities accept UPI Study credits?
How long does Data Structures and Algorithms take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 3 credits in Data Structures and Algorithms.
87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
3 credits · NCCRSEnroll →