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

Коли використовувати ArrayList, а коли LinkedList

У 99% сценаріїв слід використовувати ArrayList.

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

🟢 Junior Level

Коротка й категорична відповідь для сучасної розробки: У 99% сценаріїв слід використовувати ArrayList.

Клас LinkedList у промисловому коді сьогодні вважається практично застарілим антипатерном.

Чому ArrayList перемагає за замовчуванням:

  1. Швидке читання: доступ до будь-якого елемента за індексом get(i) виконується миттєво за $O(1)$.
  2. Економія пам’яті: зберігає компактний масив посилань (4–8 байтів на елемент), тоді як LinkedList виділяє громіздкий об’єкт вузла на кожен елемент (24–32 байти).
  3. Швидкість ітерації: завдяки неперервному розташуванню в пам’яті процесор миттєво читає елементи через кеш L1/L2.

Коли використовувати альтернативи:

  • Якщо вам потрібен список об’єктів за замовчуванням $\to$ ArrayList.
  • Якщо вам потрібна черга (FIFO) або стек (LIFO) $\to$ використовуйте ArrayDeque, а не LinkedList!
  • Якщо вам потрібно зберігати унікальні значення $\to$ HashSet.
// ✅ Стандарт сучасної Java:
List<User> users = new ArrayList<>();

// ❌ Невиправдане використання:
List<User> users = new LinkedList<>(); // Повільніше і споживає в 6 разів більше пам'яті!

🟡 Middle Level

1. Матриця вибору за сценаріями використання

Сценарій застосування Рекомендована колекція Чому саме вона
Читання за індексом get(i) ArrayList Прямий розрахунок адреси в пам’яті за $O(1)$ проти послідовного обходу посилань $O(N)$.
Ітерація (for-each, Stream API) ArrayList Кеш-локальність (Cache Locality): процесор зчитує масив цілими лініями кешу по 64 байти.
Додавання в кінець add(e) ArrayList Амортизований час $O(1)$ без виділення проміжних об’єктів-вузлів.
Черга (FIFO) або Стек (LIFO) ArrayDeque Кільцевий масив, $O(1)$ на обох кінцях, жодного зайвого сміття для GC.
Видалення за умовою (фільтрація) ArrayList (removeIf) Ефективне стиснення масиву в один прохід за $O(N)$.
Часта вставка у випадкову середину Жодна з них! ArrayList зсуває хвіст, а LinkedList шукає місце вставки за $O(N)$. Для таких завдань обирають дерева або хеш-таблиці.

2. Чому аргумент про «швидку вставку в середину» LinkedList — міф?

Класичний аргумент на користь LinkedList: «Вставка в середину списку займає $O(1)$, оскільки потрібно лише переприв’язати вказівники prev та next».

У чому полягає фатальна помилка цього міркування:

Щоб вставити елемент у позицію N у LinkedList:
1. Спочатку потрібно ДІЙТИ до позиції N:
   Node current = first;
   for (int i = 0; i < N; i++) current = current.next; // <-- Це O(N) кроків повільною RAM!
2. Переприв'язати посилання: O(1).
Підсумкова складність: O(N) + O(1) = O(N)!

В ArrayList позиція знаходиться за $O(1)$, а зсув елементів виконується нативним викликом System.arraycopy(), що переносить дані суцільними машинними блоками. До розміру списку в десятки тисяч елементів ArrayList вставляє дані в середину швидше або нарівні з LinkedList.

3. Оптимізація видалення: removeIf проти ітератора

// ❌ АНТИПАТЕРН: Видалення через ітератор в ArrayList призводить до O(N²) через багаторазові зсуви
Iterator<Order> it = list.iterator();
while (it.hasNext()) {
    if (it.next().isCancelled()) {
        it.remove(); // Кожен виклик зсуває хвіст масиву!
    }
}

// ✅ ПРАВИЛЬНО: list.removeIf() (Java 8+)
list.removeIf(Order::isCancelled);

Як працює removeIf() в ArrayList: Він використовує двоточковий алгоритм стиснення (Two Pointers) та BitSet. За один прохід $O(N)$ фіксуються всі елементи, що підлягають видаленню, після чого вцілілі елементи зсуваються на свої фінальні позиції за один прохід. Жодних квадратичних накладних витрат!

🔴 Senior Level

1. Архітектурна анатомія Hardware: «Стіна пам’яті» (Memory Wall)

Розрив між тактовою частотою процесора та швидкістю читання з оперативної пам’яті DRAM є колосальним:

  • Читання з регістрів CPU: $\sim 0.5$ нс (1 такт);
  • Читання з кешу L1: $\sim 1$ нс (3–4 такти);
  • Читання з кешу L2/L3: $\sim 4–15$ нс;
  • Читання з фізичної RAM: $\sim 60–100$ нс (200–300 тактів простою CPU!).
ArrayList в оперативній пам'яті (суміжні комірки):
[ Cell 0 ][ Cell 1 ][ Cell 2 ][ Cell 3 ][ Cell 4 ][ Cell 5 ]...
▲───────────────────────────────────────▲
CPU завантажує всю 64-байтну лінію кешу (Cache Line) за 1 звернення!

LinkedList в оперативній пам'яті (фрагментована купа):
[ Node 0 ] ──► ...пам'ять... ──► [ Node 1 ] ──► ...пам'ять... ──► [ Node 2 ]
     ▲                               ▲                               ▲
Cache Miss!                     Cache Miss!                     Cache Miss!

Під час ітерації LinkedList кожне розіменування посилання node.next звертається до випадкової адреси в купі, породжуючи безперервні CPU Cache Misses. Процесор проводить до 90% часу в режимі очікування відповіді від шини пам’яті (Pipeline Stall).

2. Навантаження на збирач сміття (GC Allocation Churn)

Під час інтенсивної обробки потоків даних (наприклад, парсинг повідомлень у Kafka consumer):

  • ArrayList: при заповненні створює масив, при очищенні занулює посилання. Нових об’єктів у купі створюється мінімум.
  • LinkedList: на кожен доданий елемент ініціюється виділення пам’яті під об’єкт Node в області TLAB. При видаленні елемента вузол негайно перетворюється на сміття.
  • Мільйон подій за секунду через LinkedList генерує мільйон об’єктів Node за секунду в Young Generation, викликаючи безперервні цикли Minor GC та паузи Stop-The-World.

3. Чи існує бодай один сценарій, де LinkedList виправданий?

Клас java.util.LinkedList не дає переваг практично ніколи, оскільки стандартна реалізація не надає прямого доступу до внутрішніх об’єктів Node. Навіть якщо вам потрібен справжній $O(1)$ для вставки та видалення вузлів, LinkedList приховує клас Node як приватний статичний (private static class).

Коли зв’язні списки дійсно потрібні:

  1. Користувацькі інтрузивні зв’язні списки (Intrusive Linked Lists): коли бізнес-об’єкт сам містить посилання prev і next (наприклад, внутрішня організація LinkedHashMap або LRU-кеші у Netty).
  2. Алгоритми ковзного вікна величезного розміру (від сотень тисяч елементів): де переміщення ітератора вперед і видалення поточного вузла iterator.remove() виконується безперервно й паралельно з додаванням, а довільний доступ за індексом взагалі не потрібен.

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

30-секундна відповідь для співбесіди

«За замовчуванням в абсолютній більшості завдань слід обирати ArrayList. Він забезпечує максимальну швидкість довільного доступу $O(1)$, мінімальне споживання пам’яті (у 6–8 разів менше за LinkedList) та еталонну кеш-локальність для процесора. LinkedList програє на сучасних CPU через постійні промахи кешу при переході між розрізненими вузлами Node і високе навантаження на збирач сміття. Для завдань черг (FIFO) та стеків (LIFO) замість LinkedList обов’язково слід використовувати ArrayDeque».

Питання підвищеної складності з відповідями

  1. Кандидат стверджує: «Я використовую LinkedList, тому що мені потрібно часто вставляти елементи всередину списку». Як ви прокоментуєте це рішення? Відповідь: Це класична помилка. Щоб вставити елемент у середину LinkedList, до цієї середини спочатку необхідно дійти за ланцюжком посилань від початку або кінця списку за $O(N)$ операцій. Кожен крок обходу супроводжується промахами кешу процесора. В ArrayList позиція вставки знаходиться миттєво за $O(1)$, а зсув решти елементів виконується через оптимізовану функцію System.arraycopy(). На практиці для списків реального розміру (до 20–50 тисяч елементів) ArrayList виконує вставку в середину швидше, ніж LinkedList.

  2. Чому метод list.removeIf(predicate) в ArrayList працює за $O(N)$, тоді як цикл з iterator.remove() працює за $O(N^2)$? Відповідь: Під час виклику iterator.remove() в ArrayList щоразу запускається зсув усіх правих елементів ліворуч на одну позицію. Якщо видаляється багато елементів, масив зсувається заново при кожному вилученні, що призводить до квадратичної складності $O(N^2)$. Метод removeIf() використовує двопрохідний алгоритм: спочатку за один прохід $O(N)$ фіксує позиції видалюваних елементів (наприклад, через BitSet), а потім за другий прохід компактно переміщує елементи, що вижили, на нові місця єдиним безперервним алгоритмом стиснення за $O(N)$.

  3. Що ефективніше використовувати як реалізацію стека: java.util.Stack, LinkedList чи ArrayDeque? Відповідь: ArrayDeque. Клас Stack застарів, оскільки успадковує Vector і синхронізує кожен метод монітором synchronized, що надлишково уповільнює код. LinkedList витрачає зайву пам’ять на об’єкти Node і створює сміття для GC. ArrayDeque працює на плоскому циклічному масиві, позбавлений накладних витрат на синхронізацію та вузли, а операції push() і pop() виконуються за амортизований час $O(1)$ з максимальною кеш-локальністю.

  4. Як впливає прапорець -XX:+UseCompressedOops на розмір LinkedList? Відповідь: Вузол LinkedList$Node містить 3 посилання (item, next, prev). За увімкненого Compressed OOPs посилання є 32-бітними (4 байти), заголовок об’єкта займає 12 байтів, і загальний розмір ноди становить 24 байти (з вирівнюванням). При вимкненні Compressed OOPs (або розмірі купи $>32$ ГБ) посилання стають 64-бітними (8 байтів), заголовок займає 16 байтів, і розмір ноди зростає до 40 байтів, що збільшує надлишкове споживання пам’яті LinkedList порівняно з ArrayList ще помітніше.

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

  • ❌ Вважати, що LinkedList швидший за ArrayList при додаванні на початок для будь-яких колекцій. (Для невеликих і середніх колекцій ArrayList випереджає LinkedList завдяки усуненню алокацій Node та роботі векторних інструкцій SIMD).
  • ❌ Рекомендувати LinkedList як чергу повідомлень. (Red Flag: незнання ArrayDeque).
  • ❌ Не знати про існування методу removeIf() і пропонувати видалення через звичайний цикл for(int i=0; ...).

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