Java ListIterator: интерфейс для обхода списков

ListIterator<E> расширяет Iterator<E>, добавляя всё то, что поддерживает список, но недоступно в обобщённом итерируемом: обход в обратном направлении, получение текущего индекса, а также добавление и замена элементов во время итерации. Он доступен для любого List<E> через list.listIterator() и list.listIterator(int startAt).

Если вы итерируете Set или Queue, эта глава не применима — у этих коллекций нет позиций. Для List ListIterator является курсором, который делает всё то же, что обычный Iterator, плюс четыре специфичные для списка операции.

Что добавляет `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);
}

Три новых возможности:

Двунаправленный обход. hasPrevious() / previous() перемещают курсор назад. previous() выбрасывает NoSuchElementException при выходе за начало.
Отчёт о позиции. nextIndex() возвращает индекс, который вернёт next(); previousIndex() — индекс, который вернёт previous(). Они отличаются на 1.
Изменение на месте. set(e) заменяет элемент, последний раз возвращённый next или previous. add(e) вставляет новый элемент между предыдущей и следующей позициями курсора.

Модель курсора

Чтобы понять ListIterator, представьте курсор как находящийся между элементами, а не на них:

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

next() возвращает элемент справа от курсора и продвигается вперёд. previous() возвращает элемент слева и сдвигается назад. Сразу после того как next() вернул "b":

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

Последующий вызов set("B") заменяет "b". Последующий add("x") вставляет "x" между "b" и "c". Последующий remove() удаляет "b". Только один из set, add или remove может быть вызван один раз после каждого next/previous — два подряд вызова или вызов любого из них без промежуточного next/previous бросает IllegalStateException.

Двунаправленный обход

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

Оба цикла используют один и тот же итератор. После окончания прямого цикла курсор находится за "c"; обратный цикл начинает с этой позиции и движется к началу. Направление можно менять посреди обхода — вызов next(), затем previous() вернёт тот же элемент, потому что курсор миновал его и вернулся обратно.

Изменение элементов во время итерации

Это главная причина использовать ListIterator вместо обычного 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 — единственный безопасный способ заменить элемент во время итерации. add — единственный безопасный способ вставить элемент во время итерации. Оба метода обновляют внутренний счётчик ожидаемых модификаций итератора, поэтому ни один из них не вызывает ConcurrentModificationException.

add заслуживает отдельного внимания: он вставляет элемент в позиции курсора — между последним результатом next и следующим. После вставки курсор оказывается за новым элементом, поэтому следующий вызов it.next() вернёт оригинальный следующий элемент, а не только что добавленный. Это именно то поведение, которое обычно нужно при «раскрытии» элемента на месте.

Распространённая ловушка: `previous()` возвращает тот же элемент, что и `next()`

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

Это сбивает с толку. Позиция курсора меняется после next, но previous проходит обратно через тот же элемент. Если нужен элемент перед текущим, придётся вызвать previous дважды — один раз чтобы вернуться через только что возвращённый элемент, и ещё раз чтобы прочитать предыдущий.

Начало с конкретного индекса

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

Форма с двумя аргументами размещает курсор перед указанным индексом. it.nextIndex() вернёт 3, it.previousIndex() вернёт 2, а первый вызов next() вернёт list.get(3). Полезно, когда начальная позиция уже найдена с помощью indexOf или binarySearch и нужно двигаться оттуда в любом направлении.

`LinkedList` vs `ArrayList`: один интерфейс, разная стоимость

Обе коллекции предоставляют ListIterator. Стоимость операций различается:

ArrayList — next/previous выполняются за O(1); add/remove во время итерации — O(n), так как смещают хвост массива. Операция set остаётся O(1).
LinkedList — next/previous выполняются за O(1) (итератор кеширует узел); add/remove через итератор — O(1), так как сдвига нет. Те же операции по индексу в LinkedList — O(n), так как поиск по индексу обходит цепочку.

Если вы итерируете LinkedList и внутри цикла вызываете list.add(index, ...), вы дважды обходите цепочку на каждую вставку. Используйте ListIterator, и каждая операция обойдётся O(1) — именно ради этого и существует LinkedList.

Развёрнутый пример: двунаправленный обход, изменения на месте, отчёт об индексах, стоимость операций

Программа ниже обходит список вперёд и назад с помощью одного итератора, заменяет и вставляет элементы на месте, выводит индексы по ходу и замеряет разницу между модификацией через итератор и по индексу в 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");
  }
}

Что можно вынести из запуска:

Прямой и обратный обход выполняются на одном ListIterator. После завершения прямого цикла через hasNext курсор оказывается за последним элементом, и hasPrevious становится истинным.
set заменил "alpha" на "ALPHA", а add("BETA-extra") вставил новый элемент сразу после "beta" — и итератор пережил обе модификации без ConcurrentModificationException.
next() и затем previous() вернули один и тот же элемент. Курсор прошёл мимо него и вернулся обратно; то, что выглядит как два чтения «разных» элементов, на самом деле один элемент, пройденный дважды.
На LinkedList версия «удалить каждый второй элемент» через итератор оказалась значительно быстрее версии по индексу. Поиск по индексу в связном списке — O(n); итератор кеширует узел, а удаление — O(1).

Что дальше

Iterator и ListIterator отвечают за обход коллекций. Вторая половина «работы с элементами» — их упорядочивание: указание Java, когда один элемент меньше, равен или больше другого. Об этом рассказывают Comparable и Comparator — естественный порядок, встроенный в тип, и внешние порядки, задаваемые для конкретной операции. Они являются основой всего остального в этой части книги, включая утилиты сортировки и поиска.

Практика

Вы вызываете `ListIterator<String> it = list.listIterator()`, затем `it.next()`, затем `it.add('x')`. Что вернёт следующий вызов `it.next()`?

Элемент, который был на индексе 1 до вызова `add` — курсор переместился за вставленный `"x"`, поэтому `add` не меняет, какой элемент идёт следующим`"x"` — только что добавленный элемент теперь стоит перед курсором`null` — `add` делает итератор недействительным, и следующий `next()` возвращает значение по умолчаниюБросает `IllegalStateException` — нельзя вызвать `next` после `add` без сброса итератора

Что добавляет ListIterator