Part 9 — Iterators Deep Dive¶

This topic is frequently combined with questions about ArrayList, HashMap, and concurrency.

Typical interview questions:

• What is an Iterator?
• What is modCount?
• What is a fail-fast iterator?
• What is the difference between fail-fast and fail-safe?
• Why does ConcurrentModificationException occur?
• Can you safely remove elements while iterating?

1. Why Do We Need an Iterator?¶

Suppose we have:

List<String> list = List.of("Java", "Python", "Go");

Without an iterator:

for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

Works for ArrayList.

But what about:

• HashSet
• TreeSet
• HashMap
• LinkedHashSet

They don't support index-based access.

A common traversal mechanism was needed.

That mechanism is the Iterator.

2. Iterable Hierarchy¶

Iterable
    │
Collection
    │
List
Set
Queue

Iterable defines one important method:

Iterator<E> iterator();

This enables:

for (String s : list) {
    System.out.println(s);
}

The enhanced for loop internally uses an Iterator.

3. Iterator Interface¶

public interface Iterator<E> {

    boolean hasNext();

    E next();

    void remove();
}

Three core methods.

4. hasNext()¶

Checks whether another element exists.

Example:

Iterator<String> it = list.iterator();

while (it.hasNext()) {
    System.out.println(it.next());
}

5. next()¶

Returns the next element.

Example:

Iterator<Integer> it = list.iterator();

System.out.println(it.next());

Output:

10

Calling next() after the iterator is exhausted throws:

NoSuchElementException

6. remove()¶

Removes the last element returned by next().

Example:

Iterator<Integer> it = list.iterator();

while (it.hasNext()) {

    Integer value = it.next();

    if (value % 2 == 0) {
        it.remove();
    }
}

This is the correct way to remove elements during iteration.

7. What Happens Internally?¶

Suppose:

ArrayList

0 1 2 3

A B C D

Iterator:

cursor = 0

Call:

next();

Returns:

A

Cursor becomes:

1

8. Enhanced for Loop¶

Code:

for (String s : list) {
    System.out.println(s);
}

Compiler roughly converts it to:

Iterator<String> it = list.iterator();

while (it.hasNext()) {
    String s = it.next();
    System.out.println(s);
}

This is why iterator rules also apply to enhanced for loops.

9. modCount¶

Interview favorite.

Collections such as ArrayList maintain:

transient int modCount;

Every structural modification increments it.

Example:

list.add("Java");

Internally:

modCount++

10. Expected Modification Count¶

When an iterator is created:

Iterator<String> it = list.iterator();

The iterator stores:

expectedModCount = modCount

11. Fail-Fast Iterator¶

During iteration:

it.next();

Internally:

expectedModCount == modCount ?

If:

Yes

Continue.

Otherwise:

ConcurrentModificationException

12. Example¶

List<Integer> list = new ArrayList<>();

list.add(1);
list.add(2);
list.add(3);

for (Integer i : list) {

    list.remove(i);
}

Throws:

ConcurrentModificationException

Why?

The iterator detects that the collection was structurally modified outside the iterator.

13. Correct Removal¶

Iterator<Integer> it = list.iterator();

while (it.hasNext()) {

    Integer i = it.next();

    if (i == 2) {
        it.remove();
    }
}

Safe.

Reason:

The iterator updates its own bookkeeping (expectedModCount) after a successful remove().

14. Fail-Fast vs Fail-Safe¶

Fail-Fast¶

Examples:

• ArrayList
• HashMap
• HashSet
• TreeMap

Behavior:

Modification

↓

ConcurrentModificationException

Fail-Safe¶

Examples:

• CopyOnWriteArrayList
• ConcurrentHashMap (its iterators are weakly consistent, not true fail-safe)

Behavior:

Iteration

↓

Uses snapshot or weakly consistent view

↓

No ConcurrentModificationException

15. CopyOnWriteArrayList¶

Example:

CopyOnWriteArrayList<Integer> list =
    new CopyOnWriteArrayList<>();

Iterator:

Snapshot

↓

Iterate over old array

Meanwhile:

list.add(100);

No exception.

The iterator continues over the original snapshot.

16. Weakly Consistent Iterators¶

ConcurrentHashMap iterators:

• Do not throw ConcurrentModificationException.
• May reflect some updates made after iteration begins.
• Are not snapshot iterators.

Interview correction:

Many candidates incorrectly call them "fail-safe." The JDK documentation describes them as weakly consistent.

17. ListIterator¶

Extends Iterator.

Additional features:

ListIterator<E>

Supports:

• Forward traversal
• Backward traversal
• Add
• Set
• Previous index

Methods:

previous()

hasPrevious()

add()

set()

18. Example¶

ListIterator<String> it =
    list.listIterator();

while (it.hasNext()) {
    System.out.println(it.next());
}

while (it.hasPrevious()) {
    System.out.println(it.previous());
}

Can move in both directions.

19. Enumeration¶

Legacy interface.

Methods:

hasMoreElements()

nextElement()

Used by:

Vector

Hashtable

No remove operation.

Modern Java code generally uses Iterator.

20. Iterator vs ListIterator¶

21. Iterator vs Enumeration¶

22. Why ConcurrentModificationException?¶

Example:

for (Integer i : list) {

    list.add(100);
}

Process:

Iterator created

↓

expectedModCount = 3

↓

list.add()

↓

modCount = 4

↓

Iterator checks

↓

Mismatch

↓

ConcurrentModificationException

23. Does ConcurrentModificationException Mean Multiple Threads?¶

No.

Single thread:

for (Integer i : list) {
    list.remove(i);
}

Still throws.

The exception indicates an unexpected structural modification during iteration, not necessarily multiple threads.

24. HashMap Iterator¶

Iterator<Map.Entry<K,V>> it =
        map.entrySet().iterator();

Recommended traversal:

while (it.hasNext()) {

    Map.Entry<K,V> entry = it.next();

    System.out.println(
        entry.getKey() + " " +
        entry.getValue()
    );
}

25. Safe Removal From HashMap¶

Iterator<Map.Entry<Integer,String>> it =
        map.entrySet().iterator();

while (it.hasNext()) {

    Map.Entry<Integer,String> e = it.next();

    if (e.getKey() == 5)
        it.remove();
}

Safe.

26. Time Complexity¶

Production Examples¶

Removing Invalid Users¶

Iterator<User> it = users.iterator();

while (it.hasNext()) {

    if (!it.next().isActive()) {
        it.remove();
    }
}

Iterating Over Cache¶

for (Map.Entry<String, User> e :
        cache.entrySet()) {

    process(e.getValue());
}

Common Interview Questions¶

Q1. Why do we need an Iterator?¶

To provide a uniform traversal mechanism across different collection implementations.

Q2. Why doesn't HashSet support indexing?¶

Because it is hash-table based.

There is no logical index.

Q3. What is fail-fast?¶

An iterator that detects unexpected structural modification and throws ConcurrentModificationException.

Q4. What is modCount?¶

An internal counter tracking structural modifications to the collection.

Q5. Does ConcurrentModificationException guarantee concurrent threads?¶

No.

It can occur in a single thread.

Q6. Which method should be used to remove elements while iterating?¶

Iterator.remove();

Q7. Difference between fail-fast and weakly consistent iterators?¶

Q8. Difference between Iterator and ListIterator?¶

ListIterator supports bidirectional traversal and element insertion/replacement.

Q9. Can you modify a collection while iterating?¶

Yes, but only through the iterator's supported modification methods (such as remove()), or by using collections designed for concurrent modification.

Q10. Why is Iterator.remove() safe?¶

Because it keeps the iterator's internal modification count synchronized with the collection.

Senior Interview Scenario¶

Question:

Why does this fail?

for (String s : list) {

    if (s.equals("Java"))
        list.remove(s);
}

Answer:

The enhanced for loop uses an Iterator internally.

Calling list.remove() modifies the collection directly, increasing modCount.

The iterator's expectedModCount no longer matches, so the next iterator operation throws ConcurrentModificationException.

Correct solution:

Iterator<String> it = list.iterator();

while (it.hasNext()) {

    if (it.next().equals("Java")) {
        it.remove();
    }
}

Key Takeaways¶

• Iterator provides a common traversal API for collections.
• Enhanced for loops use an Iterator internally.
• Fail-fast iterators rely on modCount and expectedModCount.
• ConcurrentModificationException can occur even in a single thread.
• Iterator.remove() is the correct way to remove elements during iteration.
• ListIterator supports bidirectional traversal and additional modification operations.
• ConcurrentHashMap iterators are weakly consistent, not snapshot iterators.

Next: Part 10 — Comparable vs Comparator Deep Dive¶

We'll cover:

• Natural ordering vs custom ordering
• compareTo() internals
• Comparator chaining
• Lambda comparators
• TimSort (Collections.sort() / List.sort())
• Multi-field sorting
• Common contract violations
• Senior interview questions and production examples