В чому різниця між ArrayList та LinkedList

Усередині ArrayList інкапсулює звичайний масив transient Object[] elementData.

🟢 Junior Level

ArrayList та LinkedList — це дві стандартні реалізації інтерфейсу List у Java, які кардинально відрізняються внутрішньою організацією зберігання даних у пам’яті:

ArrayList базується на динамічному масиві (Object[]). Елементи розташовані в пам’яті неперервним послідовним блоком один за одним.
LinkedList являє собою класичний двозв’язний список. Кожен елемент огорнутий в окремий об’єкт-вузол (Node), який містить корисне навантаження та посилання на попередній і наступний вузли.

Коротке порівняння характеристик

Характеристика	`ArrayList`	`LinkedList`
Внутрішня структура	Динамічний масив (`Object[]`)	Двозв’язний список вузлів (`Node<E>`)
Доступ за індексом `get(i)`	$O(1)$ (миттєво за формулою зміщення)	$O(N)$ (послідовний обхід від початку або кінця)
Додавання в кінець `add(e)`	*$O(1)^$** (амортизований час)	$O(1)$
Вставка на початок `add(0, e)`	$O(N)$ (зсув елементів масиву праворуч)	$O(1)$ (переприв’язка покажчиків голови)
Споживання пам’яті	Мінімальне (~4–8 байтів на посилання)	Високе (~24–32 байти на кожен вузол)
Інтерфейс `RandomAccess`	Реалізує (підтримує швидкий довільний доступ)	Не реалізує

[!NOTE] Золоте правило production-розробки: У 99% випадків за замовчуванням слід обирати ArrayList. Використання LinkedList у сучасному коді практично зійшло нанівець через колосальний програш у локалізації кешу процесора та надлишкове споживання пам’яті.

🟡 Middle Level

1. Архітектура та механіка роботи `ArrayList`

Усередині ArrayList інкапсулює звичайний масив transient Object[] elementData.

Індекс:      0     1     2     3     4     5
Пам'ять:   [ A ] [ B ] [ C ] [ D ] [   ] [   ]
            ▲                       ▲
            └───── size = 4 ────────┴── capacity = 6

Читання за індексом $O(1)$: Базова адреса елемента обчислюється процесором за 1 машинний такт: $\text{Address}(i) = \text{BaseAddress} + i \times \text{ReferenceSize}$
Динамічне розширення (Resizing): Коли місткість масиву вичерпана, ArrayList створює новий масив розміром: $\text{newCapacity} = \text{oldCapacity} + (\text{oldCapacity} \gg 1) \approx 1.5 \times \text{oldCapacity}$ Елементи копіюються за допомогою високошвидкісного нативного системного виклику System.arraycopy(), який компілюється JIT у векторні інструкції процесора (SIMD / AVX).

2. Архітектура та механіка роботи `LinkedList`

Усередині LinkedList зберігає посилання на перший та останній вузли: transient Node<E> first і transient Node<E> last.

          Node 0                    Node 1                    Node 2
     ┌──────────────┐          ┌──────────────┐          ┌──────────────┐
null ◄── prev       │    ┌─────┼── prev       │    ┌─────┼── prev       │
     │   item = "A" │    │     │   item = "B" │    │     │   item = "C" │
     │   next ──────┼────┘     │   next ──────┼────┘     │   next ──► null
     └──────────────┘          └──────────────┘          └──────────────┘

Читання за індексом $O(N)$: Щоб отримати list.get(500), JVM змушена пройти за ланцюжком від first (або last, якщо шуканий індекс ближче до кінця списку) рівно 500 кроків за посиланнями:
```
Node<E> x = first;
for (int i = 0; i < index; i++)
    x = x.next;
```
Вставка в середину: Хоча сам процес переприв’язки посилань займає $O(1)$, пошук цільового вузла, перед яким потрібно вставити елемент, вимагає $O(N)$ операцій послідовного обходу!

3. Зведена таблиця часової складності операцій

Операція	`ArrayList`	`LinkedList`	Примітка
`get(index)`	$O(1)$	$O(N)$	`LinkedList` ділить пошук навпіл (від початку або кінця)
`add(e)` (у кінець)	*$O(1)^$** аморт.	$O(1)$	В `ArrayList` рідко трапляється ресайз $O(N)$
`add(0, e)` (на початок)	$O(N)$	$O(1)$	`ArrayList` зсуває масив через `System.arraycopy`
`add(index, e)`	$O(N)$	$O(N)$	У `LinkedList` $O(N)$ витрачається на пошук позиції
`remove(index)`	$O(N)$	$O(N)$	`ArrayList` зсуває хвіст; `LinkedList` шукає вузол
`iterator.remove()`	$O(N)$	$O(1)$	Єдиний сценарій, де `LinkedList` теоретично швидший
Ітерація (`for-each`)	$O(N)$ (швидко)	$O(N)$ (повільно)	Колосальна різниця через промахи кешу CPU

🔴 Senior Level

1. Локалізація даних у кеші процесора (CPU Cache Locality)

Головна причина домінування ArrayList у сучасному високонавантаженому серверному ПЗ — апаратна архітектура центральних процесорів.

+-----------------------------------------------------------------------+
|  Лінія кешу процесора L1/L2 (64 байти)                                |
|  [ Посилання 0 ][ Посилання 1 ][ Посилання 2 ][ Посилання 3 ]...      |
+-----------------------------------------------------------------------+
                                  ▲
        ArrayList: 1 звернення до RAM завантажує відразу 8–16 посилань!

Hardware Prefetching в ArrayList: Масив розміщений у строго суміжних комірках оперативної пам’яті. Коли процесор запитує один елемент, апаратний контролер пам’яті автоматично підтягує в кеш L1/L2 усю 64-байтну лінію кешу. Доступ до наступних елементів відбувається практично миттєво (1–3 такти CPU) без повторного звернення до повільної шини оперативної пам’яті (RAM).
Cache Misses у LinkedList: Об’єкти Node алокуються в різні моменти часу і розкидані збирачем сміття по всьому простору купи (Heap). Кожен перехід за посиланням node = node.next призводить до промаху кешу процесора (CPU Cache Miss). Ядро процесора простоює 100–200 тактів в очікуванні завантаження даних із фізичної RAM.
Практичний результат: Послідовний обхід мільйона елементів в ArrayList працює в 10–50 разів швидше, ніж у LinkedList.

2. Ілюзія Big-O: Чому `ArrayList.add(0, e)` часто швидший за `LinkedList`

У теорії алгоритмів операція вставки на початок LinkedList.add(0, e) має складність $O(1)$, а ArrayList.add(0, e) — $O(N)$. На співбесідах кандидати нерідко роблять хибний висновок, що LinkedList завжди швидший.

Реальність на сучасному апаратному забезпеченні:

Для вставки елемента в LinkedList необхідно:
- Створити новий об’єкт new Node<>() у купі (виділення пам’яті в TLAB, запис заголовка об’єкта, ініціалізація трьох полів);
- Оновити 4 посилання в пам’яті;
- Створити додаткове навантаження на збирач сміття (GC allocation churn).
Для вставки в ArrayList:
- Викликається System.arraycopy(), що транслюється у векторні інструкції процесора (AVX / memmove), які зсувають суміжні блоки пам’яті цілими регістрами по 256/512 бітів за мінімальну кількість тактів.
Бенчмарки JMH демонструють: На списках розміром до 10 000 – 20 000 елементів ArrayList.add(0, e) виявляється швидшим, ніж LinkedList!

3. Аналіз накладних витрат пам’яті (Memory Footprint)

Порівняємо зберігання 1 000 000 об’єктів у 64-бітній JVM з увімкненим стисненням покажчиків (-XX:+UseCompressedOops):

ArrayList (1 млн елементів):
├── Заголовок масиву Object[]: 16 байтів
└── 1 000 000 посилань по 4 байти: 4 000 000 байтів (~4 МБ)
Разом: ~4 МБ

LinkedList (1 млн елементів):
Кожен елемент вимагає створення окремого об'єкта Node:
├── Заголовок об'єкта (Mark + Klass): 12 байтів
├── Посилання item: 4 байти
├── Посилання next: 4 байти
├── Посилання prev: 4 байти
└── Вирівнювання (Padding до 8 байтів): 0 байтів (сумарно 24 байти)
1 000 000 вузлів × 24 байти = 24 000 000 байтів (~24 МБ)
Разом: ~24 МБ (у 6 разів більше, ніж ArrayList!)

За вимкненого механізму Compressed OOPs вузол Node займає вже 40 байтів (у 10 разів більше, ніж ArrayList).

4. Чому `ArrayDeque` повністю витіснив `LinkedList`

Історично LinkedList використовували як реалізацію черги або стека (Queue / Deque). Сьогодні для цих завдань існує спеціалізований клас ArrayDeque:

Побудований на кільцевому динамічному масиві без створення проміжних об’єктів-вузлів Node;
Вставка та видалення з обох кінців виконуються за справжній амортизований час $O(1)$;
Не створює сміття для GC і має абсолютну локалізацію даних у кеші CPU;
Працює в 3–5 разів швидше за LinkedList у будь-яких сценаріях черг або стеків (Producer-Consumer).

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

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

«ArrayList побудований на неперервному динамічному масиві, забезпечує доступ за індексом за $O(1)$, має виняткову локалізацію даних у кеші процесора та мінімальні витрати пам’яті (4 байти на посилання). LinkedList — це двозв’язний список об’єктів Node, де доступ за індексом вимагає $O(N)$ кроків, а кожен елемент створює оверхед у 24–32 байти. Через апаратні особливості сучасних CPU (промахи кешу при переході за розрізненими вузлами LinkedList та векторні інструкції System.arraycopy в ArrayList) ArrayList перевершує LinkedList практично в усіх практичних сценаріях. У ролі черг та стеків замість LinkedList завжди слід обирати ArrayDeque».

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

Чому LinkedList програє ArrayList за швидкістю ітерації в десятки разів, хоча алгоритмічна складність обходу в обох $O(N)$? Відповідь: Причина полягає в локалізації даних у кеші процесора (Cache Locality). В ArrayList посилання розташовані в неперервній ділянці пам’яті, тому при першому зверненні апаратний префетчер підтягує в кеш лінію (64 байти), забезпечуючи миттєве потрапляння в кеш L1/L2 для наступних 8–16 елементів. У LinkedList кожен вузол Node — це окремий об’єкт, виділений збирачем сміття у довільному місці купи. Обхід списку спричиняє постійні промахи кешу (Cache Misses), змушуючи ядра CPU простоювати сотні тактів в очікуванні завантаження кожного вузла з оперативної пам’яті.
У чому полягає «ілюзія складності» при вставці на початок LinkedList проти ArrayList? Відповідь: Теоретична складність вставки на початок LinkedList.add(0, e) дорівнює $O(1)$, а ArrayList.add(0, e) — $O(N)$ через зсув елементів. Проте на практиці вставка в LinkedList вимагає виділення пам’яті під новий об’єкт Node у купі та ініціалізації вказівників, що створює помітну затримку та навантаження на GC. В ArrayList зсув масиву здійснюється системною функцією System.arraycopy(), яка використовує векторні інструкції SIMD/AVX. Як наслідок, для списків розміром до 10–20 тисяч елементів ArrayList вставляє елементи на початок швидше, ніж LinkedList.
Скільки пам’яті споживає LinkedList порівняно з ArrayList на мільйоні елементів? Відповідь: У 64-бітній JVM з увімкненим механізмом Compressed OOPs посилання в масиві ArrayList займає 4 байти, тобто мільйон посилань потребує близько 4 МБ пам’яті. У LinkedList кожен елемент вимагає створення об’єкта Node, який містить заголовок (12 байтів) та три посилання по 4 байти (item, next, prev) — разом 24 байти (або 32 байти з урахуванням вирівнювання за 8-байтною межею в деяких середовищах). Отже, LinkedList споживає від 24 до 32 МБ, тобто в 6–8 разів більше пам’яті, додатково створюючи мільйон дрібних об’єктів для збирача сміття.
Чи існують реальні сценарії в сучасному Java-коді, де LinkedList перевершує ArrayList? Відповідь: Єдиний вузькоспеціалізований сценарій — коли в процесі ітерації величезним списком (сотні тисяч елементів) необхідно масово видаляти елементи через iterator.remove(), за умови, що не можна скористатися предикатною фільтрацією через list.removeIf(). В усіх інших випадках (включно з організацією черг FIFO чи стеків LIFO) LinkedList беззастережно програє ArrayList та ArrayDeque.

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

❌ Стверджувати, що LinkedList швидший за ArrayList при вставці всередину списку. (Red Flag: нерозуміння того, що до середини списку спочатку треба дійти за $O(N)$ кроків).
❌ Стверджувати, що LinkedList економніший за пам’яттю, бо «не виділяє масив із надлишком». (Груба помилка: накладні витрати на службові об’єкти Node багаторазово перевищують 50% резерв масиву ArrayList).
❌ Використовувати LinkedList як чергу завдань замість ArrayDeque. (Незнання більш ефективних і сучасних колекцій стандартної бібліотеки JDK).