🟢 Junior Level

ArrayList та LinkedList — дві реалізації інтерфейсу List.

Головна різниця:

	ArrayList	LinkedList
Структура	Динамічний масив	Двозв’язний список
Читання за індексом	Швидке get(0)	Повільне (перебор)
Вставка на початок	Повільна (зсув)	Швидка
Пам’ять	Мало	Багато (об’єкт на елемент)

Просте правило:

• ArrayList — для більшості випадків ✅
• LinkedList — займає менше 1% реальних сценаріїв. Єдиний практичний кейс: видалення через ітератор у величезних списках (100к+ елементів), де не можна використовувати removeIf(). ❌

Приклад:

List<String> arrayList = new ArrayList<>();
arrayList.get(0);  // Миттєво!

List<String> linkedList = new LinkedList<>();
linkedList.get(0);  // Перебор всіх елементів!

Порада: Якщо вам потрібен LinkedList як черга або стек — використовуйте ArrayDeque замість нього. ArrayDeque швидший за LinkedList у 3-10 разів при ітерації та у 2-5 разів при вставці/видаленні.

---

🟡 Middle Level

ArrayList: Динамічний масив

// Всередині: Object[] array
// Доступ: array[index] → O(1)

// Додавання:
list.add(e)        // O(1)* амортизоване
list.add(0, e)     // O(n) зсув масиву
list.remove(0)     // O(n) зсув масиву

// Ресайз: при заповненні → новий масив × 1.5
// System.arraycopy() → дуже швидкий (SIMD інструкції)
// SIMD (Single Instruction, Multiple Data) — процесор копіює кілька елементів за одну тактову команду.

LinkedList: Двозв’язний список

// Всередині: ланцюжок Node об'єктів
class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

// Доступ:
list.get(0)        // O(n) перебор від початку/кінця
list.add(e)        // O(1) в кінець
list.add(0, e)     // O(1) на початок
list.remove(iterator)  // O(1) якщо є ітератор

Порівняння

Операція	ArrayList	LinkedList
get(index)	O(1)	O(n)
add(e)	O(1)*	O(1)
add(0, e)	O(n)	O(1)
remove(0)	O(n)	O(1)
contains(e)	O(n)	O(n)
iterator.remove()	O(n)	O(1)
Пам’ять	4-8 байт/ел	24-32 байт/ел

Кеш-локальність

ArrayList: [A][B][C][D]  ← поруч у пам'яті
  → CPU завантажує лінію кешу (64 байти)
  → A, B, C, D вже в L1 кеші!
  → Ітерація: дуже швидко

LinkedList: [A]...[B]...[C]...[D]  ← розкидані
  → Кожне посилання = cache miss
  → Очікування з RAM: 100+ циклів CPU
  → Ітерація: дуже повільно

Коли LinkedList?

Єдиний випадок:
  1. Список ВЕЛИЧЕЗНИЙ (мільйони елементів)
  2. Видалення ЧЕРЕЗ ІТЕРАТОР в процесі обходу
  3. Не можете замінити на removeIf()

В усіх інших випадках → ArrayList!

Альтернатива: ArrayDeque

// ❌ LinkedList як черга/стек
Deque<String> stack = new LinkedList<>();

// ✅ ArrayDeque (швидший та менше пам'яті)
Deque<String> stack = new ArrayDeque<>();

// ArrayDeque:
// → Кільцевий масив
// → Немає об'єктів Node
// → O(1) вставка/видалення з обох кінців
// → Краща кеш-локальність

---

🔴 Senior Level

Memory Footprint Deep Dive

LinkedList Node:
┌─────────────────────────┐
│ Object Header (12 байт)  │
│ item reference (4 байти) │
│ next reference (4 байти) │
│ prev reference (4 байти) │
│ Padding (8 байт)         │
└─────────────────────────┘
Разом: 32 байти на елемент!

Цифри наведено для 64-bit JVM із Compressed Oops (за замовчуванням до 32 ГБ купи). Без Compressed Oops розміри подвояться.

ArrayList:
┌─────────────────────────┐
│ Object[] array           │
│ reference (4 байти)      │
└─────────────────────────┘
Разом: 4 байти на елемент!

→ LinkedList у 8 разів більший!
→ Тиск на GC: мільйони Node об'єктів

Big O Illusion

Теорія: LinkedList.add(0, e) = O(1)
Реальність: ArrayList.add(0, e) швидший для малих списків!

Чому?
  ArrayList: System.arraycopy() → SIMD інструкції
    → 1000 елементів → ~1 мкс

  LinkedList: new Node() + 3 посилання
    → Алокація об'єкта → GC overhead
    → 1000 елементів → ~5 мкс

ArrayList виграє до ~10-20к елементів!

GC Pressure

LinkedList при видаленні:
  → Кожен Node → сміття
  → 1 млн видалень = 1 млн об'єктів у Young Gen
  → Часті Minor GC → STW паузи

ArrayList при видаленні:
  → Занулення посилання у масиві
  → 0 нових об'єктів
  → GC працює миттєво

Vector та Stack — застаріли

// ❌ Vector (синхронізований ArrayList)
Vector<String> v = new Vector<>();  // Повільний!

// ❌ Stack (наслідується від Vector)
Stack<String> s = new Stack<>();  // Подвійний оверхед!

// ✅ ArrayList (без синхронізації)
List<String> list = new ArrayList<>();

// ✅ ArrayDeque (замість Stack)
Deque<String> stack = new ArrayDeque<>();

// ✅ CopyOnWriteArrayList (якщо потрібна потокобезпечність)
List<String> threadSafe = new CopyOnWriteArrayList<>();

RandomAccess маркер

// ArrayList implements RandomAccess
// LinkedList НЕ implements RandomAccess

// JDK перевіряє це для оптимізації:
Collections.binarySearch(list, key);
// → Якщо RandomAccess: бінарний пошук за індексами
// → Якщо ні: ітерація (повільніше)

// Ваш код:
if (list instanceof RandomAccess) {
    for (int i = 0; i < list.size(); i++) { ... }  // for-i
} else {
    for (E e : list) { ... }  // foreach/iterator
}

Java 21: SequencedCollection

// List тепер наслідує SequencedCollection
list.getFirst();   // Новий метод!
list.getLast();    // Новий метод!
list.reversed();   // Зворотний порядок (view)

// ArrayList.reversed() → Efficient (масив назад)
// LinkedList.reversed() → Efficient (двозв'язний список)

Production Experience

Реальний сценарій #1: LinkedList убив продуктивність

• Додаток: 1 млн елементів, часта ітерація
• LinkedList: 10 секунд, 500 МБ пам’яті
• ArrayList: 50 мс, 50 МБ
• Прискорення: 200 разів!

Реальний сценарій #2: GC Pressure

• LinkedList: 10 млн видалень → 320 МБ сміття
• Minor GC кожні 2 секунди → лаги
• ArrayList: 0 сміття → стабільно

Best Practices

1. ArrayList — вибір за замовчуванням (99% випадків)
2. ArrayDeque — замість LinkedList для черг/стеків
3. Уникайте LinkedList через GC pressure
4. RandomAccess перевірка для циклів
5. removeIf() замість ітерації з видаленням
6. ensureCapacity() якщо відомий розмір
7. Java 21 → getFirst(), getLast(), reversed()

Резюме для Senior

• ArrayList = динамічний масив, кеш-дружній
• LinkedList = двозв’язний список, антипатерн для CPU
• Memory: ArrayList у 8 разів компактніший
• GC: LinkedList створює мільйони Node об’єктів
• Big O illusion: O(1) LinkedList часто повільніший за O(n) ArrayList
• ArrayDeque > LinkedList для стеків/черг
• RandomAccess = маркер для оптимізації
• Valhalla (майбутнє): Inline Types збільшать розрив. Project Valhalla запланований не раніше Java 23+. Поки не використовуйте його у плануванні архітектури.

---

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

Обов’язково знати:

• ArrayList = динамічний масив (Object[]), O(1) доступ за індексом, кеш-дружній
• LinkedList = двозв’язний список (Node з item/next/prev), O(n) доступ, 32 байти на елемент
• Пам’ять: ArrayList ~4 байти/ел vs LinkedList ~32 байти/ел — у 8 разів більше
• Кеш-локальність — головна причина: ArrayList завантажує 8 посилань за одну cache line, LinkedList — cache miss на кожному елементі
• Big O Illusion: LinkedList.add(0,e) = O(1) теоретично, але ArrayList швидший до 10-20к елементів завдяки SIMD
• GC Pressure: LinkedList створює мільйони Node об’єктів, ArrayList — тільки занулення посилань
• ArrayDeque > LinkedList для стеків і черг — у 3-10 разів швидший при ітерації
• RandomAccess маркер: JDK перевіряє його для вибору алгоритму (binary search за індексами vs ітерація)

Часті уточнюючі запитання:

• Коли LinkedList реально виправданий? — Видалення через ітератор у списках 100к+ елементів, де не можна використовувати removeIf()
• Чому ArrayList швидший за LinkedList при вставці на початок? — System.arraycopy() = SIMD інструкції, алокація Node дорожча
• Що таке GC Pressure? — Часті Minor GC через мільйони Node об’єктів → STW паузи → лаги
• Навіщо ArrayList implements RandomAccess? — Щоб JDK використовував оптимізовані алгоритми для швидкого доступу за індексом

Червоні прапорці (НЕ говорити):

• ❌ “LinkedList швидший для вставки на початок” — ArrayList швидший до 10-20к елементів завдяки SIMD
• ❌ “LinkedList економніший за пам’яттю” — навпаки, у 8 разів більше (32 байти vs 4 байти на елемент)
• ❌ “Використовуйте LinkedList як чергу” — ArrayDeque швидший та менше пам’яті
• ❌ “Big O = реальна продуктивність” — O(1) LinkedList часто повільніший за O(n) ArrayList через константи

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

• [[Які основні інтерфейси Collection Framework]]
• [[Коли використовувати ArrayList, а коли LinkedList]]
• [[Яка часова складність операцій в ArrayList]]
• [[Яка часова складність операцій в LinkedList]]
• [[Що таке Deque]]