Як правильно видаляти елементи під час ітерації

Найбільш лаконічний, безпечний та високопродуктивний спосіб:

🟢 Junior Level

1. Головне правило видалення елементів

[!CAUTION] Ніколи не викликайте метод collection.remove() всередині циклу for-each! Це гарантовано призведе до викидання ConcurrentModificationException.

List<String> names = new ArrayList<>(List.of("Анна", "Іван", "Петро", "Іван"));

// ❌ ТАК РОБИТИ НЕ МОЖНА (Аварійне завершення програми):
for (String name : names) {
    if (name.equals("Іван")) {
        names.remove(name); // Викине ConcurrentModificationException!
    }
}

2. Два правильних способи в сучасному коді

Варіант 1: `Collection.removeIf()` (Стандарт Java 8+)

Найбільш лаконічний, безпечний та високопродуктивний спосіб:

// ✅ НАЙКРАЩИЙ СПОСІБ:
names.removeIf(name -> name.equals("Іван"));

Варіант 2: Явний виклик `Iterator.remove()`

Класичний підхід для ситуацій, коли перед видаленням потрібна складна процедурна логіка або додаткове логування:

// ✅ КЛАСИЧНИЙ БЕЗПЕЧНИЙ СПОСІБ:
Iterator<String> it = names.iterator();
while (it.hasNext()) {
    String name = it.next();
    if (name.equals("Іван")) {
        it.remove(); // Безпечно: ітератор сам видаляє елемент і вирівнює лічильники
    }
}

🟡 Middle Level

1. Порівняльний аналіз стратегій видалення

Стратегія	`ArrayList`	`LinkedList`	Потокобезпека	Складність за пам’яттю	Примітка
`removeIf(Predicate)`	$O(N)$	$O(N)$	❌ Ні	$O(1)$	Промисловий стандарт
`Iterator.remove()`	$O(N^2)$	$O(N)$	❌ Ні	$O(1)$	$O(N^2)$ в `ArrayList` через зсуви
Зворотний цикл `for (i--)`	$O(N^2)$	$O(N^2)$	❌ Ні	$O(1)$	Не викликає CME, але повільний
Stream API `.filter()`	$O(N)$	$O(N)$	❌ Ні	$O(N)$	Створює новий список у купі (Heap)
Допоміжний список	$O(N^2)$	$O(N)$	❌ Ні	$O(N)$	`removeAll(toRemove)`

2. Чому `Iterator.remove()` деградує до $O(N^2)$ в `ArrayList`

Усередині ArrayList.remove() (та Itr.remove()) під час видалення будь-якого елемента викликається низькорівнева операція копіювання пам’яті:

System.arraycopy(elementData, index + 1, elementData, index, numMoved);

Усі елементи праворуч від видаленого зсуваються на одну позицію ліворуч.

Якщо зі списку в $1\,000\,000$ елементів видалити 500 000 записів через Iterator.remove():

500 000 разів викличеться System.arraycopy.
Кожне копіювання переміщує сотні кілобайтів пам’яті.
Сумарна складність становить $O(K \cdot N) \approx O(N^2)$. На практиці така операція займає десятки секунд або хвилини!

У LinkedList ситуація протилежна: Iterator.remove() працює за константний час $O(1)$, оскільки ітератор уже зберігає пряме посилання на поточний вузол Node і просто перенаправляє посилання prev та next у сусідніх вузлів. Сумарна складність повного обходу з видаленням для LinkedList — чесні $O(N)$.

🔴 Senior Level

1. Архітектурна перевага `ArrayList.removeIf()` під капотом

У класі ArrayList метод removeIf повністю перевизначений для досягнення максимальної продуктивності процесора та дбайливого ставлення до збирача сміття:

Фаза пошуку першої мутації: Алгоритм сканує масив elementData предикатом. Якщо жоден елемент не підійшов під умову видалення, метод завершується за $O(N)$ без жодного запису в пам’ять!

Фаза компактифікації (Two-Pointer Compaction): При знаходженні першого елемента, що підлягає видаленню, алгоритм перемикається в режим фільтрації двома вказівниками:

// Псевдокод логіки компактифікації ArrayList:
int to = i; // Індекс комірки призначення
for (int from = i + 1; from < size; from++) {
    if (!filter.test((E) elementData[from])) {
        elementData[to++] = elementData[from]; // Зсув елементів на місці за один прохід!
    }
}

Очищення посилань для GC (Prevention of Memory Loitering): Усі звільнені комірки наприкінці масиву примусово зануляються:
```
for (int j = to; j < size; j++) {
    elementData[j] = null; // Звільняємо об'єкти для Garbage Collector!
}
```
Результат: Замість сотень тисяч викликів System.arraycopy виконується рівно один послідовний прохід по пам’яті з лінійною складністю $O(N)$ та нульовим виділенням додаткової пам’яті!

2. Видалення в конкурентних колекціях

У багатопотоковому середовищі операції видалення мають принципові особливості:

CopyOnWriteArrayList: Метод iterator().remove() викидає UnsupportedOperationException. Якщо викликати cowal.removeIf(predicate), метод відпрацює потокобезпечно під ексклюзивним замком, створивши один новий масив із відфільтрованими даними.
ConcurrentHashMap: Видалення через Iterator.remove() або keySet().removeIf(...) є абсолютно безпечним. Ітератори CHM є слабкоузгодженими (Weakly Consistent), не викидають ConcurrentModificationException і відбивають видалення в живій хеш-таблиці через CAS та гранулярні блокування бакетів.

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

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

«Правильний та найбільш продуктивний спосіб видалення елементів під час ітерації в сучасній Java — метод Collection.removeIf(Predicate). В ArrayList він працює за $O(N)$ без додаткових алокацій завдяки однопрохідному алгоритму компактифікації (two-pointer), явно зануляючи хвостові посилання для запобігання витокам пам’яті в GC (Memory Loitering). Використання Iterator.remove() також безпечне проти ConcurrentModificationException, але в ArrayList деградує до катастрофічних $O(N^2)$ через постійні зсуви масиву через System.arraycopy. Прямий виклик collection.remove() всередині циклу for-each суворо заборонений».

3 каверзних запитання з інтерв’ю та відповіді

1. Чому обхід із кінця `for (int i = list.size() - 1; i >= 0; i--)` із викликом `list.remove(i)` не викидає `ConcurrentModificationException`?

Відповідь: Цикл з індексним лічильником for (int i...) звертається безпосередньо за індексами і не створює об’єкт Iterator. Поле структурних змін modCount при цьому штатно інкрементується, але перевіряти його нікому. Видалення з кінця не порушує індекси ще не перевірених елементів (усі вони розташовані лівіше за поточний індекс i). Проте для ArrayList алгоритмічна складність все одно залишається $O(N^2)$ у разі видалення багатьох елементів із середини чи початку списку, а для LinkedList деградує до жахливих $O(N^2)$ через постійний пошук вузлів за індексом від країв списку.

2. У чому прихована небезпека підходу «зібрати елементи в проміжний список `toRemove` і викликати `list.removeAll(toRemove)`»?

Відповідь:

Витрати пам’яті: Необхідно виділяти пам’ять під додатковий список toRemove, створюючи суттєве навантаження на Garbage Collector.
Алгоритмічний колапс: Метод ArrayList.removeAll(Collection c) для кожного елемента базового списку викликає c.contains(e). Якщо toRemove є звичайним ArrayList, пошук contains() займає лінійний час $O(M)$. Загальна складність операції складе $O(N \cdot M) \approx O(N^2)$. На великих обсягах даних застосунок просто зависне.

3. Як `ArrayList.removeIf()` запобігає витокам пам’яті (Memory Loitering)?

Відповідь: При зміщенні елементів ліворуч логічний розмір списку size зменшується, проте фізичний масив elementData зберігає свою колишню довжину. Якби алгоритм просто зменшив значення поля size, у комірках від нового size до старого залишилися б старі посилання на видалені об’єкти. Збирач сміття (Garbage Collector) вважав би ці об’єкти досяжними через ланцюг посилань списку й не міг би звільнити пам’ять. У реалізації removeIf() хвостові комірки масиву явно зануляються: elementData[j] = null.

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

❌ Видалення через list.remove() усередині циклу for-each: Груба помилка, що призводить до падіння з ConcurrentModificationException.
❌ Використання Iterator.remove() для масового видалення елементів з ArrayList: Неминуча деградація швидкодії до квадратичної складності $O(N^2)$.
❌ Видалення в прямому циклі за зростанням індексів for (int i=0; i<size; i++): При видаленні елемента сусідній елемент праворуч зміщується на поточний індекс i і на наступній ітерації i++ буде безслідно пропущений.
❌ Спроба викликати it.remove() у CopyOnWriteArrayList: Викине негайний UnsupportedOperationException.

🟢 Junior Level

1. Головне правило видалення елементів

2. Два правильних способи в сучасному коді

Варіант 1: Collection.removeIf() (Стандарт Java 8+)

Варіант 2: Явний виклик Iterator.remove()