🟢 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]]