Що таке патерн Iterator

У Java патерн вбудовано на рівні ядра через два ключові інтерфейси:

🟢 Junior Level

Iterator (Ітератор) — це поведінковий патерн проєктування, який надає стандартизований спосіб послідовного обходу елементів складеного об’єкта (колекції), не розкриваючи при цьому його внутрішнього представлення та структури даних (масив, зв’язний список, бінарне дерево чи граф).

У Java патерн вбудовано на рівні ядра через два ключові інтерфейси:

Iterable<T>: інтерфейс колекції, що оголошує метод Iterator<T> iterator(). Будь-який клас, що реалізує Iterable, можна використовувати в циклі for-each.
Iterator<T>: безпосередньо сам ітератор із методами hasNext(), next(), default void remove().

Побутова аналогія

Плеєр із музичним списком відтворення (плейлистом): Натискаючи кнопку «Next», слухач переходить до наступного треку, не замислюючись, як влаштовано збереження треків — це локальні MP3-файли на диску, мережевий буфер стрімінгу чи хмарна база даних. Плеєр зберігає поточну позицію і знає, чи є наступний трек.
Турнікет у метро: Пасажири проходять по одному; турнікет пропускає поточну людину і чекає на наступну, не вимагаючи бачити весь натовп на площі одночасно.

Базовий приклад у Java

import java.util.List;
import java.util.Iterator;

public class IteratorExample {
    public static void main(String[] args) {
        List<String> frameworks = List.of("Spring", "Hibernate", "Quarkus");

        // 1. Явне використання Iterator
        Iterator<String> iterator = frameworks.iterator();
        while (iterator.hasNext()) {
            String item = iterator.next();
            System.out.println("Фреймворк: " + item);
        }

        // 2. Цикл for-each (синтаксичний цукор над Iterator)
        for (String item : frameworks) {
            System.out.println("For-each: " + item);
        }
    }
}

🟡 Middle Level

Iterator vs ListIterator

Інтерфейс ListIterator<E> розширює Iterator<E> і доступний виключно для колекцій, що реалізують інтерфейс List (списки з прямим доступом за індексом):

Можливість	`Iterator<E>`	`ListIterator<E>`
Напрямок обходу	Тільки вперед (`next()`)	Двонапрямлений (`next()` та `previous()`)
Перевірка меж	`hasNext()`	`hasNext()` та `hasPrevious()`
Отримання індексу	Не підтримується	`nextIndex()`, `previousIndex()`
Модифікація даних	Тільки видалення `remove()`	Видалення `remove()`, заміна `set(E)`, додавання `add(E)`
Застосовність	Будь-яка `Collection` (Set, Queue, List)	Тільки `List` (ArrayList, LinkedList)

import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

public class ListIteratorDemo {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>(List.of("A", "B", "C"));
        ListIterator<String> listIterator = list.listIterator();

        while (listIterator.hasNext()) {
            String val = listIterator.next();
            if ("B".equals(val)) {
                listIterator.set("B_MODIFIED"); // Заміна поточного елемента
                listIterator.add("INSERTED");    // Вставка перед наступним елементом
            }
        }
    }
}

Як працює `for-each` під капотом

Цикл for (Element e : collection) транслюється компілятором javac у стандартний байткод виклику ітератора:

// Вихідний код:
for (String item : list) {
    System.out.println(item);
}

// Еквівалентний декомпільований код:
for (Iterator<String> it = list.iterator(); it.hasNext(); ) {
    String item = it.next();
    System.out.println(item);
}

Саме тому спроба змінити розмір колекції всередині циклу for-each (list.add(...) або list.remove(...)) призводить до винятку ConcurrentModificationException: модифікується сама колекція, а не ітератор!

Реалізація власного Iterable & Iterator

Приклад реалізації ітератора для обходу бінарного дерева пошуку в порядку зростання (In-Order Traversal):

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class BinaryTree<T> implements Iterable<T> {
    private Node<T> root;

    private static class Node<T> {
        T value;
        Node<T> left;
        Node<T> right;
        Node(T val) { this.value = val; }
    }

    @Override
    public Iterator<T> iterator() {
        return new InOrderIterator(root);
    }

    private class InOrderIterator implements Iterator<T> {
        private final Deque<Node<T>> stack = new ArrayDeque<>();

        public InOrderIterator(Node<T> root) {
            pushLeftBranch(root);
        }

        private void pushLeftBranch(Node<T> node) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
        }

        @Override
        public boolean hasNext() {
            return !stack.isEmpty();
        }

        @Override
        public T next() {
            if (!hasNext()) throw new NoSuchElementException();
            Node<T> current = stack.pop();
            pushLeftBranch(current.right);
            return current.value;
        }
    }
}

🔴 Senior Level

Механізм Fail-Fast: `modCount` та `expectedModCount`

Стандартні колекції (ArrayList, HashMap, HashSet, LinkedList) реалізують поведінку Fail-Fast:

Колекція містить внутрішнє службове поле protected transient int modCount = 0;.
Кожна структурна операція (add, remove, clear, ensureCapacity) інкрементує лічильник: modCount++.
Під час створення екземпляра ітератора запам’ятовується поточне значення лічильника: int expectedModCount = modCount;.

Під час кожного виклику методів next() або remove() ітератор виконує сувору перевірку:

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

⚠️ Важливо для Senior: Специфікація JDK підкреслює: поведінка Fail-Fast не гарантується на 100% у багатопотоковому середовищі без зовнішньої синхронізації. Поле modCount не є volatile-змінною, тому зміни одного потоку можуть не одразу потрапити до кешу ядра іншого потоку. Механізм Fail-Fast спроєктований виключно для виявлення логічних помилок програмування.

Fail-Fast vs Fail-Safe vs Weakly Consistent

Категорія	Представники	Поведінка під час модифікації	Чи бачить нові дані?	`remove()` ітератора
Fail-Fast	`ArrayList`, `HashMap`, `LinkedList`	Негайно викидає `ConcurrentModificationException`	Ні, обхід примусово переривається	Підтримується (синхронізує `modCount`)
Fail-Safe (Snapshot)	`CopyOnWriteArrayList`, `CopyOnWriteArraySet`	Не викидає винятків, ітерує по незмінному знімку масиву	Не бачить змін, зроблених після створення ітератора	`UnsupportedOperationException`
Weakly Consistent	`ConcurrentHashMap`, `ConcurrentLinkedQueue`	Не викидає винятків, гарантує безпечний обхід	Може бачити деякі паралельні зміни	Підтримується

Spliterator у Java 8: Еволюція під Stream API та Fork/Join

З появою Java 8 та паралельних стрімів (Parallel Streams) можливостей класичного Iterator виявилося недостатньо: звичайний ітератор неможливо ефективно розпаралелити на кілька ядер процесора. Для цього було спроєктовано інтерфейс Spliterator<T> (Splitable Iterator):

import java.util.Spliterator;
import java.util.function.Consumer;

public interface Spliterator<T> {
    boolean tryAdvance(Consumer<? super T> action); // Аналог hasNext() + next()
    Spliterator<T> trySplit();                       // Ділить діапазон даних навпіл!
    long estimateSize();                             // Оціночна кількість залишку елементів
    int characteristics();                           // Бітові прапорці характеристик джерела
}

trySplit(): Ключовий метод для роботи з пулом ForkJoinPool.commonPool(). Джерело даних рекурсивно розщеплюється на дві рівні частини: одна залишається в поточному потоці, інша передається паралельному потоку.
characteristics(): Бітова маска характеристик для оптимізації конвеєра стріма:
- ORDERED (важливий порядок), DISTINCT (елементи унікальні), SORTED (колекція відсортована),
- SIZED (точний розмір відомий), NONNULL (відсутні null), IMMUTABLE, CONCURRENT. Наприклад, якщо стрім бачить прапорець DISTINCT, проміжний крок .distinct() автоматично виключається з графа виконання як надлишковий.

Примітивні ітератори та навантаження на Garbage Collector

Використання типізованого Iterator<Integer> у критичних за продуктивністю ділянках призводить до неперервного автобоксингу (int $\rightarrow$ Integer), створюючи мільйони короткоживучих об’єктів в Eden Space та спричиняючи відчутний GC-тиск.

Для запобігання зайвим алокаціям у Java використовуються спеціалізовані примітивні ітератори:

PrimitiveIterator.OfInt
PrimitiveIterator.OfLong
PrimitiveIterator.OfDouble

import java.util.Arrays;
import java.util.PrimitiveIterator;

int[] array = {1, 2, 3, 4, 5};
PrimitiveIterator.OfInt it = Arrays.stream(array).iterator();
while (it.hasNext()) {
    int val = it.nextInt(); // 0 алокацій у купі, повна відсутність boxing!
}

🎯 Шпаргалка для інтерв’ю

30-секундна відповідь (Elevator Pitch)

«Iterator — це поведінковий патерн, що забезпечує універсальний послідовний доступ до елементів колекції без розкриття її внутрішньої структури. У Java він реалізований через інтерфейси Iterable та Iterator, на яких базується цикл for-each. Основні підвиди ітераторів у Java: Fail-Fast (стандартні колекції, відстежують структурні зміни через modCount і викидають ConcurrentModificationException), Fail-Safe (по незмінному знімку в CopyOnWriteArrayList), та Weakly Consistent (у ConcurrentHashMap). Для паралельного виконання у Stream API використовується Spliterator, що підтримує рекурсивне розділення діапазону даних методом trySplit()».

3–4 каверзних запитання з відповідями

Як правильно видаляти елементи з колекції під час ітерації?
- Відповідь:
  1. Через виклик iterator.remove() у класичному циклі while (it.hasNext()).
  2. Починаючи з Java 8 — за допомогою декларативного методу collection.removeIf(predicate), який всередині оптимізований під конкретну структуру даних (наприклад, в ArrayList зсув елементів відбувається за один прохід $O(N)$ замість $O(N^2)$ при повторних викликах remove()).
Чому лічильник modCount не гарантує викидання ConcurrentModificationException у багатопотоковому середовищі?
- Відповідь: Поле modCount не оголошене як volatile. У конкурентному середовищі значення змінної може осідати в регістрах або локальних кешах L1/L2 конкретного ядра процесора. Без синхронізації один потік змінить колекцію, але інший потік у методі checkForComodification() прочитає застаріле значення expectedModCount == modCount і продовжить обхід, що призведе до спотворення даних замість очікуваного винятку.
У чому принципова різниця між Spliterator та Iterator?
- Відповідь: Iterator розрахований строго на послідовний обхід одним потоком (hasNext()/next()). Spliterator спроєктований спеціально під паралельну обробку: він вміє ділити дані навпіл за допомогою trySplit(), повідомляє оціночний розмір estimateSize() і надає характеристики (SORTED, DISTINCT, SIZED), що дозволяють Stream API уникати зайвих обчислень.
Чому виклик remove() у ітератора CopyOnWriteArrayList призводить до винятку?
- Відповідь: Ітератор у CopyOnWriteArrayList працює по статичному незмінному знімку базового масиву (final Object[] snapshot), зафіксованому в момент створення ітератора. Оскільки сам знімок є абсолютно незмінним, метод remove() не підтримується і безумовно викидає UnsupportedOperationException.

Типові помилки та Red Flags

🚩 Спроба модифікувати колекцію (list.remove(...) / list.add(...)) всередині циклу for-each (гарантований виняток ConcurrentModificationException).
🚩 Твердження, що ConcurrentModificationException виникає лише за наявності багатьох потоків (у переважній більшості випадків він виникає в одному потоці через некоректне видалення елемента в циклі).
🚩 Помилкова думка, що Fail-Safe ітератор бачить найсвіжіші зміни колекції (він бачить знімок, зроблений суворо в момент його створення).
🚩 Використання Iterator<Integer> замість PrimitiveIterator.OfInt у високонавантажених циклах обробки числових масивів.

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

Які основні інтерфейси Collection — ієрархія колекцій та контракт iterator()
Що таке CopyOnWriteArrayList — будова snapshot-ітераторів
Що таке Stream API — внутрішня робота зі Spliterator
Які категорії патернів існують — поведінкові патерни GoF
Що таке патерни проектування — фундаментальні основи патернів проєктування