🟢 Junior Level

Коротка відповідь: У переважній більшості випадків використовуйте ArrayList.

Винятки для LinkedList: (1) Видалення через ітератор у списках 100к+ елементів, де не можна використовувати removeIf() (Java 8+). (2) Спеціалізовані структури даних (LRU-кеш на основі двозв’язного списку).

// ✅ У 99% випадків:
List<String> list = new ArrayList<>();

// ❌ LinkedList — не використовуйте без причини
List<String> list = new LinkedList<>();

Єдина причина для LinkedList:

• Дуже великий список (мільйони елементів)
• І потрібно видаляти елементи через ітератор під час обходу

Для черги/стека використовуйте ArrayDeque:

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

// ✅ ArrayDeque (швидший!)
Deque<String> queue = new ArrayDeque<>();

---

🟡 Middle Level

ArrayList: коли використовувати

// ✅ Читання за індексом
list.get(100);  // O(1) — миттєво

// ✅ Ітерація (перебор всіх елементів)
for (String s : list) { ... }  // Швидко (кеш-локальність)

// ✅ Додавання в кінець
list.add(e);  // O(1)* — амортизоване

// ✅ Якщо відомий розмір
ArrayList<String> list = new ArrayList<>(10000);
// → Без ресайзів

LinkedList: коли (рідко) використовувати

// ⚠️ Єдиний кейс:
// 1. Величезний список (100,000+ елементів)
// 2. Часте видалення ЧЕРЕЗ ІТЕРАТОР
// 3. В процесі обходу

Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (shouldRemove(it.next())) {
        it.remove();  // O(1) для LinkedList, O(n) для ArrayList
    }
}

// АЛЕ! У Java 8+ краще використовувати:
list.removeIf(this::shouldRemove);  // O(n) для обох

ArrayDeque: для черг та стеків

// Стек (LIFO)
Deque<String> stack = new ArrayDeque<>();
stack.push("A");
stack.pop();

// Черга (FIFO)
Deque<String> queue = new ArrayDeque<>();
queue.offer("A");
queue.poll();

// → Швидший за LinkedList, менше пам'яті

Порівняння на практиці

Сценарій	ArrayList	LinkedList	ArrayDeque
Читань багато	✅	❌	Н/Д
Вставка в кінець	✅	✅	✅
Вставка на початок	❌	✅	✅
Видалення за індексом	❌	❌	Н/Д
Видалення ітератором	❌	✅	Н/Д
Пам’ять	✅	❌	✅
GC pressure	✅	❌	✅

---

🔴 Senior Level

Cache Locality — головний аргумент

CPU Cache Lines: 64 байти
Cache line — мінімальний блок пам'яті, який CPU завантажує з RAM у кеш. Навіть якщо вам потрібен 1 байт, CPU завантажить усі 64 байти навколо нього. Тому сусідні дані у масиві «безкоштовні».

ArrayList:
  [ref1][ref2][ref3][ref4][ref5][ref6][ref7][ref8]
  → Одне читання → 8 посилань у L1 кеші
  → Наступні 7 елементів = 0 затримок!

LinkedList:
  [Node1]......[Node2]......[Node3]
     ↓             ↓             ↓
  RAM access: 100+ cycles КОЖНОГО разу
  → Cache miss на КОЖНОМУ елементі!

System.arraycopy vs Node Creation

// ArrayList.add(0, e):
// → System.arraycopy() → SIMD інструкції
// → 1000 елементів → ~1 мкс

// LinkedList.add(0, e):
// → new Node() → алокація у Heap
// → 3 посилання (item, next, prev)
// → 1000 елементів → ~5 мкс + GC overhead

// ArrayList швидший до ~10-20к елементів!
// (За даними бенчмарків JMH на сучасних JVM. Конкретний поріг залежить від CPU, версії JVM та патерну доступу.)

GC Pressure Deep Dive

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

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

removeIf оптимізація

// ❌ Ручне видалення через ітератор
for (Iterator<String> it = list.iterator(); it.hasNext(); ) {
    if (condition(it.next())) {
        it.remove();  // O(n) для ArrayList (зсув кожного разу)
    }
}

// ✅ removeIf (Java 8+)
list.removeIf(e -> condition(e));
// → Спочатку знаходить всі для видалення (O(n))
// → Потім ОДИН зсув (O(n))
// → Разом: O(n) замість O(n²)!

Коли ArrayList також програє

// Часті вставки на ПОЧАТОК великого списку (> 100к елементів)
// ArrayList: кожного разу зсув 100к елементів

// Рішення:
// 1. ArrayDeque (якщо вставка з обох кінців)
// 2. Або два ArrayList (head + tail)
// 3. Або переглянути архітектуру

Production Experience

Реальний сценарій #1: LinkedList → ArrayList

• Лог: 500,000 рядків у LinkedList
• Пам’ять: 800 МБ
• Ітерація: 5 секунд
• Рішення: ArrayList
• Результат: 80 МБ, 100 мс (прискорення у 50 разів!)

Реальний сценарій #2: LinkedList як черга

• Message queue: LinkedList
• GC: кожні 2 секунди (створення Node)
• Рішення: ArrayDeque
• Результат: GC раз на хвилину

Best Practices

1. ArrayList — 99% випадків
2. ArrayDeque — черги/стеки
3. removeIf() замість ітерації з видаленням
4. ensureCapacity() при відомому розмірі
5. Уникайте LinkedList без вагомої причини
6. Кеш-локальність > алгоритмічна складність
7. GC pressure враховуйте при виборі

Резюме для Senior

• ArrayList — вибір за замовчуванням (кеш-локальність)
• LinkedList — антипатерн для сучасних CPU
• ArrayDeque — для стеків та черг
• removeIf() > ітерація з видаленням
• Cache Locality > Big O у реальності
• GC Pressure — прихована вартість LinkedList
• System.arraycopy швидший за створення Node
• Valhalla (майбутнє): Inline Types збільшать розрив

---

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

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

• ArrayList — вибір за замовчуванням для 99% сценаріїв
• Кеш-локальність > алгоритмічна складність: CPU завантажує 64-байтну лінію кешу за раз, отримуючи 8-16 посилань «безкоштовно»
• System.arraycopy() = SIMD інструкції — швидший за new Node() для списків до 10-20к елементів
• removeIf() краще ручного видалення через ітератор: один прохід + один зсув = O(n) замість O(n²)
• ArrayDeque — для стеків та черг (швидший за LinkedList, менше пам’яті, немає GC pressure)
• GC Pressure: LinkedList 1 млн елементів = 32 МБ сміття, ArrayList = 0 нових об’єктів
• ensureCapacity() економить 30+ ресайзів при відомому розмірі
• Реальний кейс: заміна LinkedList → ArrayList дала прискорення у 50-200 разів та зниження пам’яті у 10 разів

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

• Коли LinkedList може виграти? — Часті вставки на ПОЧАТОК списку >100к елементів; видалення через ітератор у величезних списках
• Що таке cache line та чому це важливо? — 64-байтний блок, CPU завантажує його цілком; ArrayList використовує це, LinkedList — ні
• Чому removeIf() швидший за цикл з ітератором? — Спочатку знаходить всі елементи для видалення, потім ОДИН зсув масиву
• Коли ArrayList теж програє? — Часті вставки на початок великого списку (>100к) — тоді ArrayDeque

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

• ❌ “LinkedList кращий для частих вставок” — ArrayList швидший до 10-20к елементів завдяки SIMD
• ❌ “Для черги використовуйте LinkedList” — ArrayDeque завжди кращий (швидший, менше пам’яті)
• ❌ “Big O визначає продуктивність” — кеш-локальність та константи важливіші на практиці
• ❌ “Видалення через ітератор — нормальна практика” — використовуйте removeIf() у Java 8+

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

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