Interface Java ListIterator | W3Docs Learn Java

ListIterator<E> étend Iterator<E> avec tout ce qu'une liste peut prendre en charge mais qu'un itérable générique ne peut pas : parcourir en arrière, obtenir l'index courant, et ajouter ou remplacer des éléments durant l'itération. Il est disponible sur chaque List<E> via list.listIterator() et list.listIterator(int startAt).

Si vous itérez un Set ou une Queue, ce chapitre ne s'applique pas — ces collections n'ont pas de positions. Pour List, ListIterator est le curseur qui fait tout ce que fait le simple Iterator, plus les quatre opérations spécifiques aux listes.

Ce que `ListIterator` ajoute

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

Trois nouvelles capacités :

Parcours bidirectionnel. hasPrevious() / previous() déplacent le curseur vers l'arrière. previous() lève NoSuchElementException avant le début.
Rapport de position. nextIndex() retourne l'index que next() retournerait ; previousIndex() retourne l'index que previous() retournerait. Ils diffèrent de 1.
Éditions en place. set(e) remplace l'élément le plus récemment retourné par next ou previous. add(e) insère un nouvel élément entre les positions précédente et suivante du curseur.

Le modèle de curseur

La clé pour comprendre ListIterator est d'imaginer le curseur comme se trouvant entre les éléments, pas sur eux :

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

next() retourne l'élément à droite du curseur et avance. previous() retourne l'élément à gauche et recule. Juste après que next() retourne "b" :

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

Un set("B") suivant remplace "b". Un add("x") suivant insère "x" entre "b" et "c". Un remove() suivant supprime "b". Un seul appel parmi set, add ou remove peut être effectué une fois par next/previous — appeler deux d'affilée, ou en appeler un sans next/previous intermédiaire, lève IllegalStateException.

Parcours bidirectionnel

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

Les deux boucles utilisent le même itérateur. Une fois la boucle avant épuisée, le curseur est passé "c" ; la boucle arrière commence là et revient au début. Vous pouvez aussi changer de direction en cours de parcours — appelez next() puis previous() et vous obtenez le même élément en retour les deux fois, car le curseur l'a dépassé puis est revenu dessus.

Édition en place durant l'itération

C'est la principale raison d'utiliser ListIterator plutôt qu'un simple 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 est le seul moyen sûr de remplacer un élément durant l'itération. add est le seul moyen sûr d'insérer un élément durant l'itération. Les deux mettent à jour le compteur de modifications attendues de l'itérateur, donc aucun des deux ne déclenche de ConcurrentModificationException.

add mérite un second regard : il insère au niveau du curseur — entre le résultat du next le plus récent et le prochain résultat de next. Après l'insertion, le curseur est passé le nouvel élément, donc le tout prochain it.next() retourne l'élément suivant original, pas celui que vous venez d'ajouter. C'est presque toujours le comportement souhaité lorsque vous "développez" un élément en place.

Un piège courant : `previous()` retourne le même élément que vous venez de retourner avec `next()`

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

Cela trompe les gens. La position du curseur change après next, mais previous revient en arrière sur le même élément. Si vous voulez l'élément avant le courant, vous devez appeler previous deux fois — une fois pour revenir en arrière sur ce que vous venez de retourner, une fois pour lire réellement le précédent.

Démarrer à un index spécifique

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

La forme à deux arguments positionne le curseur avant l'index donné. it.nextIndex() retourne 3, it.previousIndex() retourne 2, et le tout premier next() retourne list.get(3). Utile lorsque vous avez déjà localisé un point de départ avec indexOf ou binarySearch et souhaitez parcourir à partir de là dans l'une ou l'autre direction.

`LinkedList` vs `ArrayList` : même interface, coût différent

Les deux exposent ListIterator. Le profil de coût diffère :

ArrayList — next/previous sont O(1) ; add/remove durant l'itération sont O(n) car ils décalent la queue du tableau. L'opération set reste O(1).
LinkedList — next/previous sont O(1) (l'itérateur met en cache le nœud) ; add/remove via l'itérateur sont O(1) car aucun décalage ne se produit. Les mêmes opérations par index sur une LinkedList sont O(n) — les recherches par index parcourent la chaîne.

Si vous itérez une LinkedList et appelez list.add(index, ...) à l'intérieur de la boucle, vous parcourez la chaîne deux fois par insertion. Utilisez le ListIterator et vous payez O(1) par opération, ce qui est la raison d'être de LinkedList.

Un exemple concret : parcours bidirectionnel, éditions en place, rapport d'index, coût des opérations

Le programme ci-dessous parcourt une liste en avant et en arrière sur le même itérateur, remplace et insère des éléments en place, rapporte les index au fur et à mesure, et mesure la différence entre la modification basée sur l'itérateur et la modification basée sur l'index sur une 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");
  }
}

Ce qu'il faut retenir de l'exécution :

Les parcours en avant et en arrière se font sur le même ListIterator. Une fois que la boucle vers l'avant épuise hasNext, le curseur est passé le dernier élément et hasPrevious devient vrai.
set a remplacé "alpha" par "ALPHA" et add("BETA-extra") a inséré un nouvel élément juste après "beta" — et l'itérateur a survécu aux deux modifications sans ConcurrentModificationException.
next() puis previous() ont retourné le même élément. Le curseur l'a dépassé puis est revenu dessus ; ce qui ressemblait à deux lectures d'éléments "différents" est en réalité un seul élément parcouru deux fois.
Sur une LinkedList, la version basée sur l'itérateur de "supprimer un élément sur deux" était considérablement plus rapide que la version basée sur l'index. La recherche par index sur une liste chaînée est O(n) ; l'itérateur met en cache son nœud et la suppression est O(1).

La suite

Iterator et ListIterator gèrent le côté traversal du travail avec les collections. L'autre moitié de "faire des choses avec les éléments" est de les ordonner : dire à Java quand un élément est inférieur, égal ou supérieur à un autre. C'est ce que couvrent Comparable et Comparator — l'ordre naturel intégré au type lui-même, et les ordres externes que vous fournissez par opération. Ils constituent le fondement sur lequel repose tout le reste dans cette partie du livre, y compris les utilitaires de tri et de recherche.

Pratique

Vous appelez `ListIterator<String> it = list.listIterator()`, puis `it.next()`, puis `it.add('x')`. Que retourne le prochain appel à `it.next()` ?

L'élément qui était à l'index 1 avant le `add` — le curseur a dépassé le `"x"` inséré, donc `add` ne change pas quel élément vient ensuite`"x"` — l'élément juste ajouté est maintenant devant le curseur`null` — `add` invalide l'itérateur et le prochain `next()` retourne la valeur par défautIl lève `IllegalStateException` — vous ne pouvez pas appeler `next` après `add` sans réinitialiser l'itérateur

Ce que ListIterator ajoute