Interfaccia Java ListIterator | W3Docs Learn Java

ListIterator<E> estende Iterator<E> con tutto ciò che una lista può supportare e che un iterabile generico non può: scorrimento all'indietro, richiesta dell'indice corrente, e aggiunta o sostituzione di elementi durante l'iterazione. È disponibile su ogni List<E> tramite list.listIterator() e list.listIterator(int startAt).

Se si itera un Set o una Queue, questo capitolo non si applica — quelle collezioni non hanno posizioni. Per List, ListIterator è il cursore che fa tutto quello che fa il semplice Iterator, più le quattro operazioni specifiche delle liste.

Cosa aggiunge `ListIterator`

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);
}

Tre nuove capacità:

Scorrimento bidirezionale. hasPrevious() / previous() spostano il cursore all'indietro. previous() lancia NoSuchElementException oltre l'inizio.
Segnalazione della posizione. nextIndex() restituisce l'indice che restituirebbe next(); previousIndex() restituisce l'indice che restituirebbe previous(). Differiscono di 1.
Modifiche in-place. set(e) sostituisce l'elemento restituito più di recente da next o previous. add(e) inserisce un nuovo elemento tra le posizioni precedente e successiva del cursore.

Il modello del cursore

Il segreto per capire ListIterator è immaginare il cursore posizionato tra gli elementi, non su di essi:

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

next() restituisce l'elemento a destra del cursore e avanza. previous() restituisce l'elemento a sinistra e torna indietro. Appena dopo che next() restituisce "b":

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

Un successivo set("B") sostituisce "b". Un successivo add("x") inserisce "x" tra "b" e "c". Un successivo remove() elimina "b". Solo uno tra set, add o remove può essere chiamato una volta per ogni next/previous — chiamarne due di fila, o chiamarne uno qualsiasi senza un next/previous intermedio, lancia IllegalStateException.

Scorrimento bidirezionale

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

Entrambi i cicli usano lo stesso iteratore. Quando il ciclo in avanti termina, il cursore è oltre "c"; il ciclo all'indietro parte da lì e torna all'inizio. Si può anche cambiare direzione a metà scorrimento — chiamare next() e poi previous() restituisce lo stesso elemento entrambe le volte, perché il cursore lo ha superato e poi è tornato su di esso.

Modifiche in-place durante l'iterazione

Questo è il motivo principale per usare ListIterator al posto di un semplice 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 è l'unico modo sicuro per sostituire un elemento durante l'iterazione. add è l'unico modo sicuro per inserire un elemento durante l'iterazione. Entrambi aggiornano il contatore interno di modifiche attese dell'iteratore, quindi nessuno dei due lancia ConcurrentModificationException.

add merita un secondo sguardo: inserisce al cursore — tra il risultato del next più recente e il risultato del next successivo. Dopo l'inserimento, il cursore è oltre il nuovo elemento, quindi il successivo it.next() restituisce l'elemento originale successivo, non quello appena aggiunto. Questo è quasi sempre il comportamento desiderato quando si "espande" un elemento in-place.

Un errore comune: `previous()` restituisce lo stesso elemento appena restituito da `next()`

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

Questo confonde spesso. La posizione del cursore cambia dopo next, ma previous torna indietro sullo stesso elemento. Se si vuole l'elemento precedente a quello corrente, bisogna chiamare previous due volte — una per tornare sull'elemento appena restituito, un'altra per leggere effettivamente il precedente.

Partire da un indice specifico

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

La forma con due argomenti posiziona il cursore prima dell'indice indicato. it.nextIndex() restituisce 3, it.previousIndex() restituisce 2, e il primissimo next() restituisce list.get(3). Utile quando si è già individuato un punto di partenza con indexOf o binarySearch e si vuole scorrere da lì in entrambe le direzioni.

`LinkedList` vs `ArrayList`: stessa interfaccia, costi diversi

Entrambe espongono ListIterator. Il profilo dei costi è diverso:

ArrayList — next/previous sono O(1); add/remove durante l'iterazione sono O(n) perché spostano la coda dell'array. L'operazione set rimane O(1).
LinkedList — next/previous sono O(1) (l'iteratore memorizza il nodo); add/remove tramite iteratore sono O(1) perché non avviene nessuno spostamento. Le stesse operazioni tramite indice su una LinkedList sono O(n) — le ricerche per indice percorrono la catena.

Se ci si trova a iterare una LinkedList e si chiama list.add(index, ...) all'interno del ciclo, si percorre la catena due volte per ogni inserimento. Usando ListIterator si paga O(1) per operazione, che è l'intera ragione d'essere di LinkedList.

Un esempio pratico: scorrimento bidirezionale, modifiche in-place, segnalazione degli indici, costi delle operazioni

Il programma seguente scorre una lista in avanti e all'indietro con lo stesso iteratore, sostituisce e inserisce elementi in-place, riporta gli indici man mano, e misura la differenza tra la modifica basata sull'iteratore e quella basata sull'indice su una 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");
  }
}

Cosa ricavare dall'esecuzione:

Lo scorrimento in avanti e all'indietro avviene sullo stesso ListIterator. Una volta che il ciclo in avanti esaurisce hasNext, il cursore è oltre l'ultimo elemento e hasPrevious diventa true.
set ha sostituito "alpha" con "ALPHA" e add("BETA-extra") ha inserito un nuovo elemento subito dopo "beta" — e l'iteratore ha sopravvissuto a entrambe le modifiche senza ConcurrentModificationException.
next() e poi previous() hanno restituito lo stesso elemento. Il cursore lo ha superato e poi è tornato su di esso; quello che sembrava la lettura di due elementi "diversi" è in realtà un unico elemento percorso due volte.
Su una LinkedList, la versione basata sull'iteratore per "eliminare ogni altro elemento" era notevolmente più veloce della versione basata sull'indice. La ricerca per indice su una linked list è O(n); l'iteratore memorizza il suo nodo e l'eliminazione è O(1).

Cosa c'è dopo

Iterator e ListIterator gestiscono il lato del traversal nel lavoro con le collezioni. L'altra metà del "fare cose con gli elementi" è ordinarli: dire a Java quando un elemento è minore, uguale o maggiore di un altro. È questo che coprono Comparable e Comparator — l'ordine naturale integrato nel tipo stesso, e gli ordinamenti esterni forniti per operazione. Sono la base su cui si appoggia tutto il resto in questa parte del libro, compresi le utility di ordinamento e ricerca.

Esercitazione

Pratica

Chiami `ListIterator<String> it = list.listIterator()`, poi `it.next()`, poi `it.add('x')`. Cosa restituisce la successiva chiamata a `it.next()`?

L'elemento che era all'indice 1 prima dell'`add` — il cursore si è spostato oltre l'`"x"` inserito, quindi `add` non cambia quale elemento viene dopo`"x"` — l'elemento appena aggiunto è ora davanti al cursore`null` — `add` invalida l'iteratore e il successivo `next()` restituisce il valore predefinitoLancia `IllegalStateException` — non si può chiamare `next` dopo `add` senza reimpostare l'iteratore

Cosa aggiunge ListIterator