🟢 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]]