Какова временная сложность операций в LinkedList?

🟢 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

Если важна производительность — ArrayList или ArrayDeque всегда быстрее
Если нужна кэш-локальность — элементы LinkedList разбросаны по куче
Если памяти мало — 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

Избегайте LinkedList — в подавляющем большинстве сценариев ArrayList или ArrayDeque справляются лучше
Никогда не используйте get(index) в цикле
ArrayDeque > LinkedList для очередей/стеков
removeIf() > итерация с удалением
foreach > for-i для LinkedList
Память: LinkedList в 8 раз больше
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]]