Iterator over Lists

Beginner Algorithms and Data Structures English

Also available: Deutsch

Created by Best · 16.08.2026 at 09:13 UTC

An iterator encapsulates the current position in the list. hasNext and next traverse node by node without revealing the internal representation.

In Java, Collection.iterator() provides an iterator. The list must not be structurally modified during iteration, otherwise a ConcurrentModificationException (fail-fast) may occur.

Advantage: Algorithms operate based on the iterator protocol, remaining decoupled from arrays versus lists.

Edge case: Calling next without a hasNext check throws NoSuchElementException.

Method	Effect
hasNext	checks that another element remains
next	returns the value and advances
## Where used

for-each, streams, and collection APIs work through iterators. Fail-fast iterators in the JDK detect structural changes during iteration. Writing your own Iterator trains the pattern behind enhanced for and graph/tree traversals.

Depth

A list iterator typically retains the next node to be output. hasNext only checks if this reference exists, and next returns the value and then advances. This way, traversal does not require repeated index access.

The iterator object encapsulates a time-dependent cursor. Multiple iterators can traverse the same unmodified list independently. Structural changes during iteration, however, require clear semantics, such as fail-fast detection via a modification counter.

An optional remove operation requires additional information about the predecessor and the last returned node. Its state machine must prevent deletion before the first next or twice after the same next.

Difficulty levels

Track cursor states of hasNext and next.
Compare the overall costs against index-based traversal.
Define valid states for a removing iterator operation.

Pitfalls

hasNext must not move the cursor forward. An iterator that runs from the head to the index at each step makes a full run unnecessarily quadratic.

University approvals: 0

Tasks

Question 1

What do fail-fast iterators in the JDK roughly describe?

They ignore every mutation.

They identify structural changes and raise

They always lock the list for other threads.

They copy the list at every next.

Question 2

Why is a node-based iterator linear for a complete list traversal?

He sorts the list in advance.

He visits each successor exactly once.

He jumps directly to each node via index.

He copies all values at each step.

Question 3

Implement a simple iterator over the nodes of an IntList.

Hint

Implement java.util.Iterator<Integer> and override hasNext() and next(). Use @Override where necessary.

public class IntList {
  public static class Node {
    int value;
    Node next;
    Node(int value) { this.value = value; }
  }
  private Node head;
  public void prepend(int value) {
    Node n = new Node(value);
    n.next = head;
    head = n;
  }
  public Iter iterator() { return new Iter(head); }
  public static class Iter {
    private Node current;
    Iter(Node first) { current = first; }
    public boolean hasNext() {
      // TODO
      return false;
    }
    public int next() {
      // TODO
      return 0;
    }
  }
}

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

1 test case will be used for grading

Run checks runtime behavior only. Final correctness is evaluated when you submit.

Card Info

Topic: Algorithms and Data Structures
Difficulty: Beginner
Completed: 0 users

Creator

Best

BestBuddy