Iteration and Iterators

The Enhanced For-Loop

The enhanced for-loop (also called the for-each loop) is syntactic sugar over the Iterable/Iterator interfaces:

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

The compiler translates this to:

for (Iterator<String> it = collection.iterator(); it.hasNext(); ) {
    String s = it.next();
    System.out.println(s);
}

Any class that implements Iterable<T> can be used in a for-each loop.

The Iterator<E> Interface

public interface Iterator<E> {
    boolean hasNext();  // are there more elements?
    E next();           // return the next element and advance
    void remove();      // remove the last element returned by next()
}

The Contract

• next() must be called before remove(). Calling remove() without a preceding next() throws IllegalStateException.
• remove() can only be called once per call to next(). Calling it twice without an intervening next() also throws IllegalStateException.
• remove() is an optional operation — some iterators throw UnsupportedOperationException (e.g., iterators over unmodifiable collections).

Safe Removal During Iteration

Mutating a collection directly (not through the iterator) while iterating throws ConcurrentModificationException:

for (String s : list) {
    if (s.startsWith("remove")) {
        list.remove(s);  // ConcurrentModificationException!
    }
}

The correct way:

Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String s = it.next();
    if (s.startsWith("remove")) {
        it.remove();  // safe — removes through the iterator
    }
}

Since Java 8, there is also Collection.removeIf():

list.removeIf(s -> s.startsWith("remove"));

The Iterable<E> Interface

public interface Iterable<T> {
    Iterator<T> iterator();
}

Collection<E> extends Iterable<E>, making every collection usable in a for-each loop. You can also implement Iterable on your own classes to support for-each iteration:

class Range implements Iterable<Integer> {
    private final int start, end;

    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() { return current++; }
        };
    }
}

for (int i : new Range(0, 10)) {
    System.out.println(i);  // 0 1 2 ... 9
}

ListIterator<E>

ListIterator<E> extends Iterator<E> and adds bidirectional traversal:

public interface ListIterator<E> extends Iterator<E> {
    boolean hasPrevious();
    E previous();
    int nextIndex();
    int previousIndex();

    void set(E e);   // replaces the last element returned by next() / previous()
    void add(E e);   // inserts BEFORE the element that would be returned by next()

    boolean hasNext();
    E next();
    void remove();
}

Usage example:

List<String> list = new ArrayList<>(List.of("a", "b", "c"));
ListIterator<String> lit = list.listIterator();

while (lit.hasNext()) {
    String s = lit.next();
    System.out.print(s);  // a, b, c
}

while (lit.hasPrevious()) {
    String s = lit.previous();
    System.out.print(s);  // c, b, a
}

Index-Based Iteration Pitfalls

Using a traditional for loop with get(i) is $O(n^2)$ on a LinkedList:

LinkedList<String> list = new LinkedList<>();
for (int i = 0; i < list.size(); i++) {
    String s = list.get(i);  // each get(i) walks from the nearest end — O(n) per call
}

This is a quadratic disaster. The enhanced for-loop always uses an iterator, giving $O(n)$ traversal regardless of list implementation:

for (String s : list) {
    // O(n) total — iterator walks the links once
}

If you need the index during iteration on a LinkedList, use a counter alongside an iterator rather than get(i).

The For-Each Loop Requirements

For a class to work with the for-each loop, all of the following must hold:

1. The expression after the colon must implement Iterable<T> (or be an array, which is a special case handled by the compiler).
2. The declared loop variable type must be assignment-compatible with the element type T.
3. The compiler-generated iterator calls must not be interfered with by concurrent structural modification to the underlying collection.

Internal versus External Iteration

The traditional Iterator pattern is external iteration — the client code controls the traversal explicitly.

Java 8 introduced internal iteration via streams, where the collection itself controls the traversal and the client provides a callback:

list.stream()
    .filter(s -> s.length() > 3)
    .map(String::toUpperCase)
    .forEach(System.out::println);

For most Tripos questions, however, external iteration with Iterator/ListIterator is the relevant model.