📦 Розділ 4 · Питання #25

В чому різниця між Iterator та ListIterator

Інтерфейси Iterator та ListIterator призначені для послідовного обходу колекцій у Java. При цьому ListIterator є розширенням Iterator (public interface ListIterator extends I...

📦 Колекції 📄 Вихідний Markdown

🟢 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() не поверне щойно вставлений елемент (він поверне той самий елемент, що й повернув би до виклику add()). А наступний виклик 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 у разі паралельної модифікації списку.

Пов’язані теми