🟢 Junior Level

Iterator — для перебора любых коллекций (только вперёд). ListIterator — для списков (вперёд и назад).

// Iterator: работает с List, Set, Queue
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String s = it.next();
}

// ListIterator: только List, но мощнее
ListIterator<String> it = list.listIterator();
while (it.hasNext()) {
    String s = it.next();
    // Можно назад!
    if (it.hasPrevious()) {
        String prev = it.previous();
    }
}

---

🟡 Middle Level

Сравнение

	Iterator	ListIterator
Коллекции	Все (List, Set, Queue)	Только List
Направление	Только вперёд	Вперёд и назад
Индексы	Нет	nextIndex(), previousIndex()
Модификация	remove()	remove(), set(), add()
Старт	С начала	С любого индекса

Курсор между элементами

List: [A] [B] [C]
       ↑
    Курсор (между A и B)

it.next()     → возвращает B, курсор двигается вправо
it.previous() → возвращает A, курсор двигается влево

ListIterator vs for (int i...): for (int i...) для LinkedList = O(n^2), потому что каждый get(i) перебирает с начала. ListIterator = O(n), потому что помнит текущую позицию. Для ArrayList оба подхода O(n).

Оптимизация LinkedList

// ❌ O(n²) — каждый get перебирает!
for (int i = 0; i < list.size(); i++) {
    list.get(i);  // O(n) для LinkedList
}

// ✅ O(n) — итератор уже на месте
ListIterator<String> it = list.listIterator();
while (it.hasNext()) {
    it.next();      // O(1)
    it.add("new");  // O(1) — уже на узле!
}

LinkedList.get(i) каждый раз начинает с head/tail и шагает i раз по ссылкам. ListIterator один раз дошёл до нужного узла и дальше двигается с O(1) — он хранит ссылку на текущий Node.

---

🔴 Senior Level

Когда НЕ использовать ListIterator

1. Работаете с Set/Queue — ListIterator не поддерживается
2. Просто читаете элементы — for-each чище
3. Нужна параллельная обработка — Iterator проще

Методы модификации

// add(E) — вставляет ПЕРЕД курсором
it.add("X");
// it.previous() вернёт "X"

// set(E) — заменяет ПОСЛЕДНИЙ next/previous
it.next();  // → "A"
it.set("B"); // "A" → "B"

// ❌ IllegalStateException если не было next/previous
it.set("X");  // Ошибка!

forEachRemaining (Java 8+)

Iterator<String> it = list.iterator();
it.forEachRemaining(System.out::println);
// → Оставшиеся элементы

LinkedList оптимизация

LinkedList.get(500) → 500 переходов по узлам
ListIterator на позиции 500:
  → add/remove/set → O(1)
  → Уже держит ссылку на Node!

Best Practices

1. Iterator → для всех коллекций
2. ListIterator → для List, особенно LinkedList
3. Курсор между элементами
4. set/add зависят от последнего next/previous
5. listIterator(index) → старт с позиции
6. forEachRemaining → Java 8+ functional style

Резюме для Senior

• Iterator = универсальный, только вперёд
• ListIterator = List, двунаправленный, модификация
• Курсор между элементами
• LinkedList → ListIterator критичен для O(1)
• set/add → после next/previous

---

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

Обязательно знать:

• Iterator работает со всеми коллекциями (List, Set, Queue), только вперёд
• ListIterator только для List, но поддерживает: движение назад, индексы, set(), add()
• Курсор ListIterator находится МЕЖДУ элементами — next() возвращает элемент справа, previous() — слева
• Для LinkedList: for (int i...) = O(n^2), ListIterator = O(n)
• set() и add() работают только после вызова next() или previous()
• listIterator(index) позволяет начать итерацию с любой позиции
• forEachRemaining() (Java 8+) — функциональный стиль для оставшихся элементов

Частые уточняющие вопросы:

• Почему for (int i...) для LinkedList — O(n^2)? — Каждый get(i) шагает от начала/конца по узлам; n вызовов × n шагов = O(n^2).
• Когда ListIterator.add(“X”) вставляет элемент? — Перед курсором; следующий previous() вернёт “X”.
• Можно ли использовать ListIterator с HashSet? — Нет, Set не поддерживает ListIterator — только обычный Iterator.
• Что будет если вызвать set() без предварительного next()? — IllegalStateException — нет «последнего элемента» для замены.

Красные флаги (НЕ говорить):

• «ListIterator работает с Set» — нет, только с List
• «Iterator может двигаться назад» — нет, только ListIterator имеет previous()
• «for (int i...) и ListIterator одинаково эффективны для LinkedList» — нет, O(n^2) vs O(n)
• «set() заменяет следующий элемент» — нет, заменяет последний, возвращённый next()/previous()

Связанные темы:

• [[28. Как правильно удалять элементы во время итерации]]
• [[26. Что такое fail-fast и fail-safe итераторы]]
• [[27. Что такое ConcurrentModificationException]]