🟢 Junior Level

LinkedList — двозв’язний список, де кожен елемент — окремий об’єкт.

Операція	Складність	Пояснення
get(index)	O(n)	Потрібно перебрати елементи
add(e)	O(1)	Додавання в кінець
addFirst(e)	O(1)	Додавання на початок
add(index, e)	O(n)	Потрібно знайти позицію
remove(index)	O(n)	Потрібно знайти позицію
iterator.remove()	O(1)	Якщо ітератор вже дійшов до елемента (тобто ви перебираєте список та видаляєте поточний елемент)

Важливо: get(index) повільний!

// ❌ Повільно: O(n²)
for (int i = 0; i < list.size(); i++) {
    list.get(i);  // Кожного разу перебор!
}

// ✅ Швидко: O(n)
for (String s : list) {
    // Перебор один раз
}

---

🟡 Middle Level

Деталі операцій

// get(index): O(n)
// → Перебор від початку АБО кінця (що ближче)
// → Немає прямого доступу!

// add(e): O(1)
// → Додавання в кінець
// → Без ресайзів (на відміну від ArrayList)

// add(0, e): O(1)
// → Додавання на початок
// → Швидший за ArrayList (немає зсуву)

// add(index, e): O(n)
// → O(n) на пошук позиції
// → O(1) на вставку
// → Разом: O(n)

// iterator.remove(): O(1)
// → Єдина перевага!
// → Якщо ітератор вже на елементі

Пастка ітерації

// ❌ O(n²) — класична помилка!
LinkedList<String> list = ...;
for (int i = 0; i < list.size(); i++) {
    String s = list.get(i);  // O(n) кожного разу!
    // Разом: n × n = n²
}

// ✅ O(n) — використовуйте foreach
for (String s : list) {
    // Перебор один раз
}

// ✅ O(n) — використовуйте ітератор
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String s = it.next();
}

Пам’ять

LinkedList Node: 32 байти
  → Object Header: 12 байт
  → item reference: 4 байти
  → next reference: 4 байти
  → prev reference: 4 байти
  → Padding: 8 байт

ArrayList: 4 байти на посилання
  → Тільки посилання у масиві

→ LinkedList у 8 разів більший!

---

🔴 Senior Level

Коли НЕ використовувати LinkedList

1. Якщо важлива продуктивність — ArrayList або ArrayDeque завжди швидші
2. Якщо потрібна кеш-локальність — елементи LinkedList розкидані по купі
3. Якщо пам’яті мало — LinkedList витрачає 24+ байти на вузол (prev + next + item)

Cache Locality катастрофа

CPU Cache Line: 64 байти

ArrayList:
  [ref1][ref2][ref3][ref4]...
  → 1 читання → 8 посилань у L1
  → Ітерація: мінімум cache misses

LinkedList:
  [Node1]...[Node2]...[Node3]
  → Кожен next = cache miss
  → Очікування з RAM: 100+ cycles
  → Pipeline stall — коли CPU змушений чекати дані з RAM, весь конвеєр інструкцій зупиняється. Це коштує 100-300 тактів CPU.

GC Pressure

LinkedList: 1 млн елементів
  → 1 млн Node об'єктів
  → 32 МБ оверхеду
  → Minor GC: сканувати 1 млн об'єктів

ArrayList: 1 млн елементів
  → 1 Object[] array
  → 4 МБ
  → GC: одне посилання

Коли LinkedList O(1) реально швидший?

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

Чому?
  LinkedList: new Node() → алокація → 3 посилання
  ArrayList: System.arraycopy() → SIMD

→ Алокація об'єкта ДОРОЖЧА за зсув масиву!

Для малих списків (< 10-20к елементів). На великих списках з частими вставками на початок LinkedList може виграти.

Єдиний кейс для LinkedList

// ДУЖЕ великий список + видалення через ітератор
LinkedList<String> list = new LinkedList<>();

Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (shouldRemove(it.next())) {
        it.remove();  // O(1) — просто переприв'язка посилань
    }
}

// ArrayList: O(n) — зсув масиву кожного разу
// АЛЕ! removeIf() в ArrayList теж O(n) один раз!
list.removeIf(e -> shouldRemove(e));  // Використовуйте це!

Java 21: SequencedCollection

// LinkedList тепер SequencedCollection
list.getFirst();   // O(1)
list.getLast();    // O(1)
list.reversed();   // O(1) — view

// ArrayDeque теж підтримує
// І швидший!

Best Practices

1. Уникайте LinkedList — у переважній більшості сценаріїв ArrayList або ArrayDeque справляються краще
2. Ніколи не використовуйте get(index) у циклі
3. ArrayDeque > LinkedList для черг/стеків
4. removeIf() > ітерація з видаленням
5. foreach > for-i для LinkedList
6. Пам’ять: LinkedList у 8 разів більший
7. GC: LinkedList створює мільйони об’єктів

Резюме для Senior

• get(index) = O(n) — головний недолік
• add/remove(0) = O(1) — але ArrayList швидший на малих
• iterator.remove() = O(1) — єдина перевага
• Cache Miss на кожному елементі → pipeline stalls
• GC Pressure = 32 байти × N об’єктів
• O(n²) пастка — foreach використовуйте, не for-i
• removeIf() > ітерації з видаленням
• ArrayDeque > LinkedList завжди для стеків/черг

---

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

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

• get(index) = O(n) — перебор від початку або кінця (що ближче), немає прямого доступу
• add(e)/addFirst(e) = O(1), але ArrayList швидший на малих списках завдяки SIMD
• iterator.remove() = O(1) — єдина реальна перевага LinkedList
• Пам’ять: 32 байти на елемент (Object header + item + next + prev + padding) — у 8 разів більше ArrayList
• Cache Miss катастрофа: кожен next = 100+ циклів очікування з RAM, pipeline stalls
• O(n²) пастка: for-i з get(i) = n × O(n) = O(n²), використовуйте foreach або iterator
• GC Pressure: 1 млн елементів = 1 млн Node об’єктів = 32 МБ оверхеду
• ArrayDeque > LinkedList для стеків/черг — швидший та менше GC pressure

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

• Чому LinkedList.add(0,e) = O(1) але повільніший за ArrayList? — Алокація Node об’єкта дорожча ніж System.arraycopy() для малих списків
• Коли iterator.remove() = O(1) реально корисне? — При видаленні через ітератор у ДУЖЕ великих списках (100к+), де не можна removeIf()
• Що таке O(n²) пастка? — Цикл for-i з get(i): кожен get(i) = O(n), разом n×n = O(n²)
• Чому LinkedList поганий для кешу? — Вузли розкидані по купі, кожен next = cache miss → очікування з RAM

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

• ❌ “LinkedList швидший за ArrayList для вставки” — тільки на списках >10-20к, і то не завжди
• ❌ “Використовуйте for-i для LinkedList” — це O(n²), використовуйте foreach/iterator
• ❌ “LinkedList економить пам’ять” — навпаки, 32 байти vs 4 байти на елемент
• ❌ “LinkedList — хороший вибір для черги” — ArrayDeque завжди кращий

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

• [[В чому різниця між ArrayList та LinkedList]]
• [[Коли використовувати ArrayList, а коли LinkedList]]
• [[Яка часова складність операцій в ArrayList]]
• [[Що таке Deque]]