В чём разница между Iterator и ListIterator

Интерфейсы Iterator и ListIterator предназначены для последовательного обхода коллекций в Java. При этом ListIterator является расширением Iterator (public interface ListIterato...

🟢 Junior Level

1. Главные различия

Интерфейсы Iterator и ListIterator предназначены для последовательного обхода коллекций в Java. При этом ListIterator является расширением Iterator (public interface ListIterator<E> extends Iterator<E>), созданным специально для списков (List).

Характеристика	`Iterator`	`ListIterator`
Применимость	Любые коллекции (`List`, `Set`, `Queue`)	Только списки (`List`)
Направление обхода	Только вперед (`next()`)	Двунаправленный (`next()` и `previous()`)
Индексы	Не поддерживаются	Поддерживает `nextIndex()` и `previousIndex()`
Модификация данных	Только удаление: `remove()`	Удаление, замена и вставка: `remove()`, `set(e)`, `add(e)`
Стартовая позиция	Всегда только с начала	С начала или с произвольного индекса (`listIterator(index)`)

List<String> list = new ArrayList<>(List.of("A", "B", "C"));

// 1. Обычный Iterator: только вперед и только remove
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    System.out.println(it.next());
}

// 2. ListIterator: обход с конца в обратную сторону
ListIterator<String> listIt = list.listIterator(list.size()); // Курсор в самом конце
while (listIt.hasPrevious()) {
    System.out.println(listIt.previous()); // "C", "B", "A"
}

🟡 Middle Level

1. Модель курсора в `ListIterator`

Чтобы понимать поведение методов ListIterator, важно помнить: курсор итератора всегда логически находится МЕЖДУ элементами, а не на самом элементе:

Индекс:          0           1           2
Элементы:   [ "Alpha" ] [ "Beta" ] [ "Gamma" ]
Курсор:   ▲           ▲          ▲           ▲
Позиция:  0           1          2           3

Вызов next() возвращает элемент справа от курсора и смещает курсор вправо.
Вызов previous() возвращает элемент слева от курсора и смещает курсор влево.
Метод nextIndex() возвращает индекс элемента, который вернет следующий вызов next().
Метод previousIndex() возвращает индекс элемента, который вернет следующий вызов previous().

2. Расширенные операции модификации: `set()` и `add()`

В отличие от Iterator, умеющего только удалять текущий элемент, ListIterator поддерживает замену и вставку:

List<String> names = new ArrayList<>(List.of("Иван", "Петр", "Анна"));
ListIterator<String> it = names.listIterator();

// 1. Метод set(E e) - заменяет ПОСЛЕДНИЙ возвращенный элемент:
while (it.hasNext()) {
    if (it.next().equals("Петр")) {
        it.set("Петр Первый"); // "Петр" заменяется на "Петр Первый"
    }
}

// 2. Метод add(E e) - вставляет элемент ПЕРЕД текущим курсором:
it = names.listIterator();
while (it.hasNext()) {
    if (it.next().equals("Иван")) {
        it.add("Сергей"); // "Сергей" встает сразу после "Иван"
    }
}
System.out.println(names); // [Иван, Сергей, Петр Первый, Анна]

🔴 Senior Level

1. Контракт состояний: когда бросается `IllegalStateException`

Операции remove() и set(e) в ListIterator привязаны к понятию последнего возвращенного элемента (Last Returned Element):

Вызов set(e) или remove() допустим только после вызова next() или previous().
Вызов add(e) сбрасывает ссылку на последний возвращенный элемент.
Вызов remove() также сбрасывает ссылку на последний возвращенный элемент.

ListIterator<String> it = list.listIterator();
it.next(); // Возвращен элемент 0

it.add("Новый"); // Вставили элемент
it.set("Замена"); // КАТАСТРОФА: выбросит java.lang.IllegalStateException!

it.remove(); // КАТАСТРОФА: выбросит java.lang.IllegalStateException!

Почему вылетает ошибка: Метод add() сдвинул курсор за вставленный элемент. Метод set() не знает, какой именно элемент нужно заменить — тот, что был возвращен предыдущим next(), или только что вставленный. Во избежание двусмысленности спецификация JDK запрещает вызов set и remove сразу после add.

2. Критическое спасение производительности для `LinkedList`

Классическая ошибка разработчиков при работе со связным списком LinkedList — использование обычного цикла for со счетчиком:

// ❌ АНТИПАТТЕРН: Сложность O(N^2)!
for (int i = 0; i < linkedList.size(); i++) {
    String item = linkedList.get(i); // Каждый вызов get(i) идет по связям с 0 до i!
}

// ✅ ОПТИМАЛЬНО: Сложность O(N)
ListIterator<String> it = linkedList.listIterator();
while (it.hasNext()) {
    String item = it.next(); // O(1) переход по ссылке node.next!
    if (needInsert) {
        it.add("newItem");   // O(1) вставка ноды в текущую позицию!
    }
}

Внутри LinkedList.ListItr сохраняется прямая ссылка на текущий узел Node<E> next. Поэтому операции шага и модификации происходят за $O(1)$, предотвращая квадратичный коллапс при росте коллекции.

🎯 Шпаргалка для интервью

30-секундный ответ (Elevator Pitch)

«Iterator — это универсальный интерфейс для однонаправленного обхода любой коллекции (List, Set, Queue) только вперед с поддержкой единственной операции модификации — remove(). ListIterator — его расширение, доступное исключительно для списков (List). Он является двунаправленным (hasPrevious(), previous()), отслеживает индексы (nextIndex(), previousIndex()), позволяет стартовать с произвольной позиции (list.listIterator(index)) и поддерживает операции замены (set) и вставки (add). Для LinkedList использование ListIterator критично, так как снижает обход и модификацию с катастрофических $O(N^2)$ до $O(N)$».

3 каверзных вопроса на интервью с ответами

1. Куда именно вставляется элемент при вызове `ListIterator.add(E e)` и что вернут последующие вызовы `next()` и `previous()`?

Ответ: Элемент вставляется непосредственно перед курсором. Соответственно, следующий вызов it.next() не вернет вставленный элемент (он вернет тот же элемент, что вернул бы и до вставки). А следующий вызов it.previous() сразу же вернет этот только что вставленный элемент. Кроме того, значение nextIndex() увеличивается на 1.

2. Почему интерфейс `Set` не предоставляет метод `setIterator()` с возможностью движения назад?

Ответ: По своей математической природе интерфейс Set (в частности, HashSet) представляет собой неупорядоченное множество элементов, распределенных по корзинам хэш-таблицы. В нем отсутствует концепция индекса и фиксированного предыдущего соседа. Даже упорядоченные множества (TreeSet, LinkedHashSet) не имеют прямого индексного доступа, поэтому их интерфейс ограничивается стандартным Iterator.

3. Можно ли вызвать `it.remove()` дважды подряд после одного вызова `it.next()`?

Ответ: Нет, второй вызов немедленно завершится с ошибкой IllegalStateException. Метод remove() удаляет последний возвращенный элемент и обнуляет внутренний указатель lastRet = null. Чтобы вызвать remove() повторно, необходимо сначала передвинуть курсор следующим вызовом next() или previous().

Типичные ошибки и Red Flags

❌ Попытка получить ListIterator от HashSet или TreeSet: Метод listIterator() существует только у коллекций, реализующих List.
❌ Вызов set() сразу после add(): Приведет к IllegalStateException.
❌ Использование list.get(i) вместо ListIterator для обхода LinkedList: Фатальное падение скорости до $O(N^2)$.
❌ Попытка использовать ListIterator в многопоточном коде без синхронизации: Итераторы списков являются Fail-Fast и бросят ConcurrentModificationException при параллельной модификации списка.

🟢 Junior Level

1. Главные различия

🟡 Middle Level

1. Модель курсора в ListIterator

2. Расширенные операции модификации: set() и add()

🔴 Senior Level

1. Контракт состояний: когда бросается IllegalStateException

2. Критическое спасение производительности для LinkedList