Iterator über Listen

Beginner Algorithmen und Datenstrukturen Deutsch

Also available: English

Created by Best · 16.08.2026 at 09:13 UTC

Ein Iterator kapselt die aktuelle Position in der Liste. hasNext und next wandern knotenweise, ohne die innere Darstellung preiszugeben.

In Java liefert Collection.iterator() einen Iterator. Während der Iteration darf die Liste nicht strukturell verändert werden, sonst droht ConcurrentModificationException (fail-fast).

Vorteil: Algorithmen arbeiten gegen das Iterator-Protokoll und bleiben von Array versus Liste entkoppelt.

Randfall: next ohne hasNext-Prüfung wirft NoSuchElementException.

Methode	Wirkung
hasNext	prüft, ob noch ein Element wartet
next	liefert den Wert und rückt vor
## Wo gebraucht

for-each, Streams und Collection-APIs laufen über Iteratoren. Fail-fast-Iteratoren in der JDK erkennen strukturelle Änderungen während der Iteration. Eigenes Iterator-Schreiben trainiert das Muster hinter Enhanced for und hinter Graph-/Baumwanderungen.

Vertiefung

Ein Listeniterator speichert typischerweise den nächsten auszugebenden Knoten. hasNext prüft nur, ob diese Referenz existiert, und next liefert den Wert und rückt anschliessend weiter. Damit benötigt die Traversierung keinen wiederholten Indexzugriff.

Das Iteratorobjekt kapselt einen zeitabhängigen Cursor. Mehrere Iteratoren können dieselbe unveränderte Liste unabhängig durchlaufen. Strukturelle Änderungen während der Iteration erfordern dagegen eine klare Semantik, etwa fail-fast-Erkennung über einen Änderungszähler.

Eine optionale remove-Operation braucht zusätzliche Information über Vorgänger und zuletzt gelieferten Knoten. Ihre Zustandsmaschine muss verhindern, dass vor dem ersten next oder zweimal nach demselben next gelöscht wird.

Schwierigkeitsstufen

Cursorzustände von hasNext und next verfolgen.
Die Gesamtkosten gegenüber indexbasierter Traversierung vergleichen.
Gültige Zustände einer entfernenden Iteratoroperation definieren.

Fallstricke

hasNext darf den Cursor nicht weiterbewegen. Ein Iterator, der bei jedem Schritt erneut vom Kopf bis zum Index läuft, macht einen vollständigen Durchlauf unnötig quadratisch.

University approvals: 0

Tasks

Question 1

Was beschreibt fail-fast-Iteratoren im JDK grob?

Sie ignorieren jede Mutation

Sie erkennen strukturelle Änderungen und werfen

Sie sperren die Liste für andere Threads immer

Sie kopieren die Liste bei jedem next

Question 2

Warum ist ein knotenbasierter Iterator für einen vollständigen Listendurchlauf linear?

Er sortiert die Liste vorab.

Er besucht jeden Nachfolger genau einmal.

Er springt per Index direkt zu jedem Knoten.

Er kopiert alle Werte bei jedem Schritt.

Question 3

Implementiere einen einfachen Iterator über die Knoten einer IntList.

Hint

Implementiere java.util.Iterator<Integer> und überschreibe hasNext() sowie next(). Verwende bei Bedarf @Override.

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: Algorithmen und Datenstrukturen
Difficulty: Beginner
Completed: 0 users

Creator

Best

BestBuddy