Chapter 59 of 77

Iterator in Java

So far, we have walked through collections like ArrayList, HashSet, HashMap, and TreeMap using loops. A normal for loop with an index works for lists, but what about a HashSet? It has no index at all. And what if we want to remove some elements while we are looping?

Java solves both problems with one simple tool: the Iterator.

Think of an iterator like a bookmark that moves through a book one page at a time. It always knows where it is, it can tell you whether there is a next page, and it can tear out the page it is currently on.

An Iterator is an object that lets us go through the elements of a collection one by one, and safely remove elements while doing so.

The Three Iterator Methods

The Iterator<E> interface lives in the java.util package. It has three main methods:

Method

What it does

hasNext()

Returns true if there are more elements to visit

next()

Moves forward and returns the next element

remove()

Removes the element that was returned by the last next() call

Every collection in the Collections Framework (lists, sets, queues) has an iterator() method that gives us an iterator for that collection.

Using an Iterator

Let's go through a list of names:

import java.util.ArrayList;
import java.util.Iterator;

class Main {
    public static void main(String[] args) {

        ArrayList<String> names = new ArrayList<>();
        names.add("John");
        names.add("Jason");
        names.add("Alex");

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

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

Output:

John
Jason
Alex

It helps to picture the iterator as a cursor that sits between elements:

Start:          | John  Jason  Alex      hasNext() = true
next() → John     John | Jason  Alex     hasNext() = true
next() → Jason    John  Jason | Alex     hasNext() = true
next() → Alex     John  Jason  Alex |    hasNext() = false → loop ends

Each call to next() jumps over one element and returns it. When the cursor reaches the end, hasNext() returns false.

The Enhanced for Loop Uses an Iterator

You have already been using iterators without knowing it. When you write:

for (String name : names) {
    System.out.println(name);
}

the Java compiler turns it into something like this:

Iterator<String> it = names.iterator();
while (it.hasNext()) {
    String name = it.next();
    System.out.println(name);
}

The enhanced for loop works with any class that implements the Iterable interface. Iterable has just one abstract method, iterator(). All lists, sets, and queues implement it, which is why we can use the enhanced for loop on all of them. (Arrays also work with the enhanced for loop, but the compiler handles them separately with an index.)

Iterable → "I can give you an iterator". Iterator → "I walk through the elements".

Removing Elements While Looping

This is the most important reason to use an iterator directly. Suppose we want to remove all failing marks (below 40) from a list. A beginner might write:

for (Integer m : marks) {
    if (m < 40) {
        marks.remove(m);   // modifies the list directly
    }
}

With the marks [85, 32, 91, 28, 67], this crashes:

Exception in thread "main" java.util.ConcurrentModificationException

Why? The hidden iterator inside the enhanced for loop remembers how many times the list has been changed. When we call marks.remove() directly, the list changes behind the iterator's back. On the next call to next(), the iterator notices the change and throws ConcurrentModificationException. This behaviour is called fail-fast: it is better to stop immediately than to silently skip or repeat elements.

The correct way is to remove through the iterator itself:

import java.util.ArrayList;
import java.util.Iterator;

class Main {
    public static void main(String[] args) {

        ArrayList<Integer> marks = new ArrayList<>();
        marks.add(85);
        marks.add(32);
        marks.add(91);
        marks.add(28);
        marks.add(67);

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

        while (it.hasNext()) {
            int m = it.next();
            if (m < 40) {
                it.remove();   // safe removal
            }
        }

        System.out.println(marks);
    }
}

Output:

[85, 91, 67]

Because the iterator did the removal itself, it updates its own bookkeeping and everything stays consistent.

One interesting interview fact: fail-fast behaviour is done on a "best effort" basis and is not guaranteed. For example, removing the second-last element inside an enhanced for loop over an ArrayList does not throw at all, because after the removal hasNext() returns false and the loop simply ends before the check happens (the last element is silently skipped). So never rely on the exception to catch your mistakes. Always use it.remove().

Later, after learning lambda expressions, you will also see the shorter removeIf() method, which does the same job in one line.

Iterating Over a Map

A Map is not a Collection, so it has no iterator() method of its own. Instead, we take one of its views: keySet(), values(), or entrySet(). Each of these is a collection with its own iterator.

Here we remove all fruits that are out of stock:

import java.util.Iterator;
import java.util.Map;
import java.util.TreeMap;

class Main {
    public static void main(String[] args) {

        TreeMap<String, Integer> stock = new TreeMap<>();
        stock.put("Apple", 12);
        stock.put("Banana", 0);
        stock.put("Mango", 7);
        stock.put("Orange", 0);

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

        while (it.hasNext()) {
            Map.Entry<String, Integer> entry = it.next();
            if (entry.getValue() == 0) {
                it.remove();   // removes the whole key-value pair
            }
        }

        System.out.println(stock);
    }
}

Output:

{Apple=12, Mango=7}

Removing through the view's iterator also removes the entry from the map itself.

ListIterator: Moving in Both Directions

Lists offer a more powerful iterator called ListIterator. In addition to the normal methods, it can:

hasPrevious() / previous()   → move backwards
nextIndex() / previousIndex() → get the current position
set(e)                        → replace the last returned element
add(e)                        → insert an element at the cursor

For example:

import java.util.ArrayList;
import java.util.ListIterator;

class Main {
    public static void main(String[] args) {

        ArrayList<String> names = new ArrayList<>();
        names.add("john");
        names.add("jason");
        names.add("alex");

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

        // Forward: capitalise every name
        while (it.hasNext()) {
            int index = it.nextIndex();
            String name = it.next();
            it.set(name.toUpperCase());
            System.out.println(index + " -> " + name);
        }

        // Backward: the cursor is now at the end
        while (it.hasPrevious()) {
            System.out.println(it.previous());
        }

        System.out.println(names);
    }
}

Output:

0 -> john
1 -> jason
2 -> alex
ALEX
JASON
JOHN
[JOHN, JASON, ALEX]

Notice that set() changed the list while we were looping, and no exception was thrown, because the change was made through the iterator.

Iterator vs ListIterator

Feature

Iterator

ListIterator

Works with

Any collection

Lists only

Direction

Forward only

Forward and backward

Remove

Yes

Yes

Replace / add

No

Yes (set(), add())

Index information

No

Yes (nextIndex(), previousIndex())

Common Iterator Errors

Two exceptions show up when an iterator is used incorrectly:

ArrayList<String> names = new ArrayList<>();
names.add("John");

Iterator<String> it = names.iterator();
System.out.println(it.next());   // John
it.next();                       // no more elements!
java.util.NoSuchElementException

Always check hasNext() before calling next().

Iterator<String> it2 = names.iterator();
it2.remove();   // remove() before any next()
java.lang.IllegalStateException

remove() can only be called once after each next(). Calling it before next(), or twice in a row, throws IllegalStateException.

Making Your Own Class Iterable

If your own class implements Iterable, it can be used in an enhanced for loop just like a list. Here is a simple Range class that produces numbers from start up to (but not including) end:

import java.util.Iterator;
import java.util.NoSuchElementException;

class Range implements Iterable<Integer> {

    private final int start;
    private final int end;   // exclusive

    Range(int start, int end) {
        this.start = start;
        this.end = end;
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            private int current = start;

            @Override
            public boolean hasNext() {
                return current < end;
            }

            @Override
            public Integer next() {
                if (!hasNext()) {
                    throw new NoSuchElementException();
                }
                return current++;
            }
        };
    }

    public static void main(String[] args) {
        for (int n : new Range(1, 6)) {
            System.out.print(n + " ");
        }
        System.out.println();
    }
}

Output:

1 2 3 4 5 

The iterator() method returns an anonymous class that keeps track of the current number. The numbers are produced one at a time, so no list is ever created in memory.

Performance Notes

Calling hasNext() and next() takes O(1) time (on average) for the common collections, so going through all elements is O(n). The cost of remove() depends on the collection:

Collection

Cost of it.remove()

ArrayList

O(n), because later elements must shift left

LinkedList

O(1), only links are changed

HashSet / HashMap

O(1) on average

TreeSet / TreeMap

O(log n)

So removing many elements from a large ArrayList one by one with an iterator can take O(n²) time in the worst case. For huge lists, building a new list with only the elements you want to keep is often faster.

Common Mistakes

1. Calling list.remove() inside an enhanced for loop
   → ConcurrentModificationException (use it.remove())

2. Calling next() twice in one loop iteration
   → skips elements, and may throw NoSuchElementException

3. Calling it.remove() before next(), or twice after one next()
   → IllegalStateException

4. Reusing an iterator after the loop ends
   → it is already at the end; ask the collection for a new one

Mistake 2 deserves an example, because it is very common:

while (it.hasNext()) {
    if (it.next().startsWith("J")) {
        System.out.println(it.next());   // WRONG: moves forward again!
    }
}

Always store the result of next() in a variable and use that variable.

The Main Idea

An Iterator walks through a collection one element at a time using hasNext() and next(), and remove() is the safe way to delete elements while looping.

Key points to remember:

  • Every list, set, and queue gives you an iterator through iterator().

  • The enhanced for loop is just a shortcut that uses an iterator behind the scenes.

  • Changing a collection directly while iterating causes ConcurrentModificationException.

  • ListIterator can move backwards and can replace or insert elements.

  • Implementing Iterable lets your own classes work with the enhanced for loop.

A popular interview question is: "How do you remove elements from a list while iterating over it?" Now you know the answer: use the iterator's own remove() method.