🟢 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 EACH
  → 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²)!

When ArrayList also loses

// Частые вставки в НАЧАЛО большого списка (> 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]]