Java ListIterator Interface | W3Docs Learn Java

ListIterator<E> erweitert Iterator<E> um alles, was eine Liste unterstützen kann, was ein generisches Iterable nicht kann: rückwärts laufen, den aktuellen Index abfragen und während der Iteration Elemente hinzufügen oder ersetzen. Es ist auf jeder List<E> über list.listIterator() und list.listIterator(int startAt) verfügbar.

Wenn Sie ein Set oder eine Queue durchlaufen, gilt dieses Kapitel nicht — diese Collections haben keine Positionen. Für List ist ListIterator der Cursor, der alles tut, was der einfache Iterator tut, plus die vier listenspezifischen Operationen.

Was `ListIterator` hinzufügt

public interface ListIterator<E> extends Iterator<E> {
  // inherited:
  boolean hasNext();
  E next();
  void remove();
  // new:
  boolean hasPrevious();
  E previous();
  int nextIndex();
  int previousIndex();
  void set(E e);
  void add(E e);
}

Drei neue Fähigkeiten:

Bidirektionaler Durchlauf. hasPrevious() / previous() bewegen den Cursor rückwärts. previous() wirft NoSuchElementException nach dem Anfang.
Positionsabfrage. nextIndex() gibt den Index zurück, den next() zurückgeben würde; previousIndex() gibt den Index zurück, den previous() zurückgeben würde. Sie unterscheiden sich um 1.
In-Place-Bearbeitung. set(e) ersetzt das Element, das zuletzt von next oder previous zurückgegeben wurde. add(e) fügt ein neues Element zwischen der vorherigen und der nächsten Cursorposition ein.

Das Cursor-Modell

Der Trick beim Verständnis von ListIterator besteht darin, sich den Cursor zwischen den Elementen vorzustellen, nicht auf ihnen:

       [ "a"   "b"   "c" ]
        ^     ^     ^     ^
        0     1     2     3      <- nextIndex() values

next() gibt das Element rechts vom Cursor zurück und rückt vor. previous() gibt das Element links zurück und bewegt sich zurück. Direkt nachdem next() "b" zurückgegeben hat:

       [ "a"   "b"   "c" ]
                    ^
              previousIndex()=1, nextIndex()=2

Ein anschließendes set("B") ersetzt "b". Ein anschließendes add("x") fügt "x" zwischen "b" und "c" ein. Ein anschließendes remove() löscht "b". Nur eines von set, add oder remove kann einmal pro next/previous aufgerufen werden — zwei nacheinander aufzurufen oder eines davon ohne dazwischenliegendes next/previous aufzurufen, wirft IllegalStateException.

Bidirektionale Traversierung

List<String> letters = new ArrayList<>(List.of("a", "b", "c"));
ListIterator<String> it = letters.listIterator();
while (it.hasNext()) System.out.print(it.next() + " ");      // a b c
while (it.hasPrevious()) System.out.print(it.previous() + " "); // c b a

Beide Schleifen verwenden denselben Iterator. Nachdem die Vorwärtsschleife endet, befindet sich der Cursor hinter "c"; die Rückwärtsschleife beginnt dort und geht zurück. Sie können die Richtung auch mitten im Durchlauf wechseln — rufen Sie next() und dann previous() auf und Sie erhalten dasselbe Element zurück, weil der Cursor es passiert hat und dann wieder zurückgegangen ist.

In-Place-Bearbeitung während der Iteration

Dies ist der Hauptgrund für die Verwendung von ListIterator anstelle eines einfachen Iterator:

List<String> words = new ArrayList<>(List.of("alpha", "beta", "gamma"));
ListIterator<String> it = words.listIterator();
while (it.hasNext()) {
  String w = it.next();
  if (w.startsWith("a")) it.set(w.toUpperCase());     // replace in place
  if (w.equals("beta"))  it.add("BETA-extra");        // insert after beta
}
// words is now [ALPHA, beta, BETA-extra, gamma]

set ist der einzige sichere Weg, ein Element während der Iteration zu ersetzen. add ist der einzige sichere Weg, ein Element während der Iteration einzufügen. Beide aktualisieren den intern erwarteten Änderungszähler des Iterators, sodass keiner eine ConcurrentModificationException auslöst.

add verdient einen zweiten Blick: Es fügt am Cursor ein — zwischen dem letzten next-Ergebnis und dem nächsten next-Ergebnis. Nach dem Einfügen ist der Cursor hinter dem neuen Element, sodass das nächste it.next() das ursprüngliche nächste Element zurückgibt, nicht das, das Sie gerade hinzugefügt haben. Das ist fast immer das gewünschte Verhalten, wenn Sie ein Element "erweitern".

Ein häufiger Fallstrick: `previous()` gibt dasselbe Element zurück, das Sie gerade mit `next()` erhalten haben

ListIterator<String> it = letters.listIterator();
it.next();      // "a", cursor between a and b
it.previous();  // "a" again, cursor between (start) and a

Das verwirrt viele. Die Position des Cursors ändert sich nach next, aber previous geht zurück über dasselbe Element. Wenn Sie das Element vor dem aktuellen wollen, müssen Sie previous zweimal aufrufen — einmal um zurück über das gerade zurückgegebene Element zu treten, einmal um das vorherige tatsächlich zu lesen.

An einem bestimmten Index beginnen

ListIterator<String> it = list.listIterator(3);    // start with cursor before index 3

Die zweiargumentige Form positioniert den Cursor vor dem angegebenen Index. it.nextIndex() gibt 3 zurück, it.previousIndex() gibt 2 zurück und das erste next() gibt list.get(3) zurück. Nützlich, wenn Sie bereits einen Startpunkt mit indexOf oder binarySearch gefunden haben und von dort aus in beide Richtungen laufen möchten.

`LinkedList` vs. `ArrayList`: dieselbe Schnittstelle, unterschiedliche Kosten

Beide bieten ListIterator. Das Kostenprofil unterscheidet sich:

ArrayList — next/previous sind O(1); add/remove während der Iteration sind O(n), weil sie das Array-Ende verschieben. Die set-Operation bleibt O(1).
LinkedList — next/previous sind O(1) (der Iterator cacht den Knoten); add/remove über den Iterator sind O(1), weil kein Verschieben stattfindet. Dieselben Operationen über einen Index auf einer LinkedList sind O(n) — Indexabfragen durchlaufen die Kette.

Wenn Sie eine LinkedList durchlaufen und list.add(index, ...) innerhalb der Schleife aufrufen, durchlaufen Sie die Kette zweimal pro Einfügung. Verwenden Sie den ListIterator und Sie zahlen O(1) pro Operation, was genau der Grund ist, warum LinkedList existiert.

Ein ausgearbeitetes Beispiel: bidirektionaler Durchlauf, In-Place-Bearbeitung, Indexabfrage, Kostenvergleich

Das folgende Programm durchläuft eine Liste vorwärts und rückwärts mit demselben Iterator, ersetzt und fügt Elemente in-place ein, meldet Indizes beim Durchlaufen und misst den Unterschied zwischen iteratorbasierter und indexbasierter Änderung einer LinkedList.

java— editable, runs on the server

import java.util.*;

public class ListIteratorShowcase {
  public static void main(String[] args) {
    List<String> words = new ArrayList<>(List.of("alpha", "beta", "gamma", "delta"));

// --- Forward walk with index reporting ---
    ListIterator<String> it = words.listIterator();
    System.out.println("forward:");
    while (it.hasNext()) {
      int i = it.nextIndex();
      String w = it.next();
      System.out.println("  [" + i + "] " + w);
    }

// --- Backward walk on the SAME iterator ---
    System.out.println("backward:");
    while (it.hasPrevious()) {
      int i = it.previousIndex();
      String w = it.previous();
      System.out.println("  [" + i + "] " + w);
    }

// --- In-place edits: set + add ---
    ListIterator<String> it2 = words.listIterator();
    while (it2.hasNext()) {
      String w = it2.next();
      if (w.startsWith("a")) it2.set(w.toUpperCase());     // ALPHA
      if (w.equals("beta"))  it2.add("BETA-extra");         // insert after beta
    }
    System.out.println("after edits: " + words);

// --- next() then previous() returns the SAME element ---
    ListIterator<String> it3 = words.listIterator();
    String a = it3.next();
    String b = it3.previous();
    System.out.println("next() = " + a + "   previous() = " + b + "   (same element)");

// --- Cost: index-based vs iterator-based modification of a LinkedList ---
    LinkedList<Integer> chain = new LinkedList<>();
    for (int i = 0; i < 20_000; i++) chain.add(i);

long t1 = System.nanoTime();
    for (int i = chain.size() - 1; i >= 0; i -= 2) chain.remove(i);   // O(n) per call
    long indexDur = System.nanoTime() - t1;

LinkedList<Integer> chain2 = new LinkedList<>();
    for (int i = 0; i < 20_000; i++) chain2.add(i);
    long t2 = System.nanoTime();
    ListIterator<Integer> lit = chain2.listIterator();
    while (lit.hasNext()) { lit.next(); if (lit.hasNext()) { lit.next(); lit.remove(); } }
    long iterDur = System.nanoTime() - t2;

System.out.println("LinkedList drop-every-other:");
    System.out.println("  index-based:    " + (indexDur / 1_000_000) + " ms");
    System.out.println("  iterator-based: " + (iterDur  / 1_000_000) + " ms");
  }
}

Was aus dem Lauf zu entnehmen ist:

Der Vorwärts- und Rückwärtsdurchlauf erfolgen auf demselben ListIterator. Sobald die Vorwärtsschleife hasNext erschöpft, befindet sich der Cursor hinter dem letzten Element und hasPrevious wird true.
set hat "alpha" durch "ALPHA" ersetzt und add("BETA-extra") hat ein neues Element direkt nach "beta" eingefügt — und der Iterator hat beide Änderungen ohne ConcurrentModificationException überstanden.
next() und dann previous() haben dasselbe Element zurückgegeben. Der Cursor hat es passiert und ist dann wieder zurückgegangen; was wie zwei Lesevorgänge von "verschiedenen" Elementen aussah, ist tatsächlich ein Element, das zweimal durchlaufen wurde.
Bei einer LinkedList war die iteratorbasierte Version von "jedes zweite Element löschen" dramatisch schneller als die indexbasierte Version. Indexabfrage auf einer verketteten Liste ist O(n); der Iterator cacht seinen Knoten und das Löschen ist O(1).

Nächste Schritte

Iterator und ListIterator behandeln die Traversierungs-Seite der Arbeit mit Collections. Die andere Hälfte von "Dinge mit Elementen tun" ist ihr Sortieren: Java zu sagen, wann ein Element kleiner, gleich oder größer als ein anderes ist. Das decken Comparable und Comparator ab — natürliche Reihenfolge, die in den Typ selbst eingebaut ist, und externe Ordnungen, die Sie pro Operation bereitstellen. Sie sind die Grundlage, auf der alles andere in diesem Teil des Buches aufbaut, einschließlich der Sort- und Such-Utilities.

Übungen

Übung

Sie rufen `ListIterator<String> it = list.listIterator()` auf, dann `it.next()`, dann `it.add('x')`. Was gibt der nächste Aufruf von `it.next()` zurück?

Das Element, das vor dem `add` an Index 1 war — der Cursor ist am eingefügten `"x"` vorbeigegangen, also ändert `add` nicht, welches Element als nächstes kommt`"x"` — das gerade hinzugefügte Element steht jetzt vor dem Cursor`null` — `add` macht den Iterator ungültig und das nächste `next()` gibt den Standardwert zurückEs wirft `IllegalStateException` — man kann `next` nach `add` nicht aufrufen, ohne den Iterator zurückzusetzen

Was ListIterator hinzufügt