Java Iterator and ListIterator: traversal and controlled edits

Traversal and mutation have separate rules

Calling next returns the next element and changes iterator state. Calling remove then removes that returned element when the implementation supports removal. Calling remove twice without another next is not valid.

An enhanced for loop uses an iterator for most collections, but does not expose that iterator’s remove method. Removing through the collection inside that loop can invalidate traversal. Use an explicit iterator when the traversal itself owns removals.

Fail-fast exceptions help detect misuse. They are not a synchronisation protocol and are not guaranteed to detect every race. A program must be correct without relying on ConcurrentModificationException to police competing writers.

Use the cursor for a linked list

A list iterator has a cursor between elements. After next, add inserts before the element that would be returned by the next next call. It does not replace the last returned element; set performs that replacement.

For a LinkedList, repeatedly calling get(index) during traversal can accumulate quadratic work. An iterator follows nodes instead. Locating the initial cursor still has traversal cost, even when the later local edit is cheap.

The cleanup program removes failed stage markers, then inserts a quality stage at a known cursor. It intentionally does not share the list with another thread. Ownership is what makes the small editing sequence easy to reason about.

Working program

import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;

public class WorkflowIterator {
    public static void main(String[] args) {
        LinkedList<String> stages = new LinkedList<>(Arrays.asList("received", "failed:scan", "packed"));
        Iterator<String> cleanup = stages.iterator();
        while (cleanup.hasNext()) {
            if (cleanup.next().startsWith("failed:")) {
                cleanup.remove();
            }
        }
        ListIterator<String> editor = stages.listIterator(1);
        editor.add("quality-check");
        System.out.println(stages);
        System.out.println(editor.next());
    }
}

Output

[received, quality-check, packed]
packed

Cost and design choices

Traversing n linked nodes takes O(n) time with O(1) cursor state. Removing the current linked node is constant link work. For an ArrayList, iterator removal can shift later elements; many individual removals can be expensive.

Initial listIterator(index) positioning on a linked list traverses toward that index. Describing every iterator edit as constant total cost hides this setup expense.

If the goal is a separate filtered result, copying accepted values into a new list preserves the original. That uses O(k) result space for k accepted values and makes the ownership boundary explicit.

Common Mistakes

• Do not call remove before next or twice for the same returned element.
• Do not modify the collection independently while its iterator is in use.
• Do not treat fail-fast behavior as thread safety.

Connect the contracts

Compare the boundary explained in Filtering into a result with the assumptions made by this program.

Next boundary checks

Continue with Java synchronizedList iteration: hold the wrapper lock.