В чём разница между ArrayList и LinkedList

Внутри ArrayList инкапсулирует обычный массив transient Object[] elementData.

🟢 Junior Level

ArrayList и LinkedList — это две стандартные реализации интерфейса List в Java, различающиеся внутренним устройством хранения данных в памяти:

ArrayList основан на динамическом массиве (Object[]). Элементы лежат в памяти непрерывным блоком друг за другом.
LinkedList представляет собой классический двусвязный список. Каждый элемент упакован в отдельный объект-узел (Node), который содержит ссылки на предыдущий и следующий элементы.

Краткое сравнение характеристик

Характеристика	`ArrayList`	`LinkedList`
Внутренняя структура	Динамический массив (`Object[]`)	Двусвязный список узлов (`Node<E>`)
Доступ по индексу `get(i)`	$O(1)$ (мгновенно по формуле смещения)	$O(N)$ (последовательный обход с начала или конца)
Добавление в конец `add(e)`	*$O(1)^$** (амортизированное время)	$O(1)$
Вставка в начало `add(0, e)`	$O(N)$ (сдвиг элементов массива вправо)	$O(1)$ (перепривязка указателей головы)
Потребление памяти	Минимальное (~4–8 байт на ссылку)	Высокое (~24–32 байта на каждый узел)
Интерфейс `RandomAccess`	Реализует (поддерживает быстрый доступ)	Не реализует

[!NOTE] Золотое правило production-разработки: В 99% случаев по умолчанию следует выбирать ArrayList. Использование LinkedList в современном коде практически сошло на нет из-за колоссального проигрыша в локализации кэша процессора и расходе памяти.

🟡 Middle Level

1. Архитектура и механика работы `ArrayList`

Внутри ArrayList инкапсулирует обычный массив transient Object[] elementData.

Индекс:      0     1     2     3     4     5
Память:   [ A ] [ B ] [ C ] [ D ] [   ] [   ]
            ▲                       ▲
            └───── size = 4 ────────┴── capacity = 6

Чтение по индексу $O(1)$: Адрес элемента вычисляется процессором за 1 такт: $\text{Address}(i) = \text{BaseAddress} + i \times \text{ReferenceSize}$
Динамическое расширение (Resizing): Когда емкость массива исчерпана, ArrayList создает новый массив размером: $\text{newCapacity} = \text{oldCapacity} + (\text{oldCapacity} \gg 1) \approx 1.5 \times \text{oldCapacity}$ Элементы переносятся с помощью высокоскоростного нативного системного вызова System.arraycopy(), который компилируется JIT в векторные инструкции процессора (SIMD / AVX).

2. Архитектура и механика работы `LinkedList`

Внутри LinkedList хранит ссылки на первый и последний узлы: transient Node<E> first и transient Node<E> last.

          Node 0                    Node 1                    Node 2
     ┌──────────────┐          ┌──────────────┐          ┌──────────────┐
null ◄── prev       │    ┌─────┼── prev       │    ┌─────┼── prev       │
     │   item = "A" │    │     │   item = "B" │    │     │   item = "C" │
     │   next ──────┼────┘     │   next ──────┼────┘     │   next ──► null
     └──────────────┘          └──────────────┘          └──────────────┘

Чтение по индексу $O(N)$: Чтобы получить list.get(500), JVM вынуждена пройти по цепочке от first (или last, если индекс ближе к концу списка) ровно 500 шагов по ссылкам:
```
Node<E> x = first;
for (int i = 0; i < index; i++)
    x = x.next;
```
Вставка в середину: Хотя сам процесс перепривязки ссылок занимает $O(1)$, поиск узла, перед которым нужно вставить элемент, всё равно требует $O(N)$ операций обхода!

3. Сводная таблица временной сложности операций

Операция	`ArrayList`	`LinkedList`	Примечание
`get(index)`	$O(1)$	$O(N)$	`LinkedList` делит поиск пополам (от начала или конца)
`add(e)` (в конец)	*$O(1)^$** аморт.	$O(1)$	В `ArrayList` редко случается ресайз $O(N)$
`add(0, e)` (в начало)	$O(N)$	$O(1)$	`ArrayList` сдвигает массив через `System.arraycopy`
`add(index, e)`	$O(N)$	$O(N)$	В `LinkedList` $O(N)$ уходит на поиск позиции
`remove(index)`	$O(N)$	$O(N)$	`ArrayList` сдвигает хвост; `LinkedList` ищет узел
`iterator.remove()`	$O(N)$	$O(1)$	Единственный сценарий, где `LinkedList` теоретически быстрее
Итерация (`for-each`)	$O(N)$ (быстро)	$O(N)$ (медленно)	Огромная разница из-за кэш-промахов CPU

🔴 Senior Level

1. Локализация данных в кэше процессора (CPU Cache Locality)

Главная причина доминирования ArrayList в современном серверном ПО — аппаратная архитектура процессоров.

+-----------------------------------------------------------------------+
|  Кэш-линия процессора L1/L2 (64 байта)                                 |
|  [ Ссылка 0 ][ Ссылка 1 ][ Ссылка 2 ][ Ссылка 3 ][ Ссылка 4 ]...       |
+-----------------------------------------------------------------------+
                                  ▲
        ArrayList: 1 обращение к RAM загружает сразу 8–16 ссылок!

Hardware Prefetching в ArrayList: Массив расположен в строго смежных ячейках оперативной памяти. Когда процессор запрашивает один элемент, аппаратный контроллер памяти автоматически подтягивает в кэш L1/L2 всю 64-байтную строку. Доступ к следующим элементам происходит мгновенно (1–3 такта CPU) без обращения к медленной шине памяти RAM.
Cache Misses в LinkedList: Объекты Node аллоцируются в разные моменты времени и разбросаны сборщиком мусора по всему объему кучи (Heap). Каждый переход по ссылке node = node.next приводит к промаху кэша процессора (CPU Cache Miss). Процессор простаивает 100–200 тактов в ожидании данных из физической RAM.
Практический итог: Последовательный обход миллиона элементов в ArrayList работает в 10–50 раз быстрее, чем в LinkedList.

2. Иллюзия Big-O: Почему `ArrayList.add(0, e)` часто быстрее `LinkedList`

В теории алгоритмов операция вставки в начало LinkedList.add(0, e) имеет сложность $O(1)$, а ArrayList.add(0, e) — $O(N)$. На собеседованиях кандидаты часто делают вывод, что LinkedList быстрее.

Реальность на современном «железе»:

Для вставки элемента в LinkedList необходимо:
- Создать новый объект new Node<>() в куче (выделение памяти в TLAB, заполнение заголовка объекта, инициализация трех полей);
- Обновить 4 ссылки в памяти;
- Создать дополнительную нагрузку на сборщик мусора (GC allocation churn).
Для вставки в ArrayList:
- Вызывается System.arraycopy(), который транслируется в векторные инструкции процессора (AVX / memmove), сдвигающие блоки памяти целыми регистрами по 256/512 бит.
Бенчмарки JMH показывают: На списках размером до 10 000 – 20 000 элементов ArrayList.add(0, e) оказывается быстрее, чем LinkedList!

3. Анализ накладных расходов памяти (Memory Footprint)

Сравним хранение 1 000 000 объектов в 64-битной JVM с Compressed OOPs (-XX:+UseCompressedOops):

ArrayList (1 млн элементов):
├── Заголовок массива Object[]: 16 байт
└── 1 000 000 ссылок по 4 байта: 4 000 000 байт (~4 МБ)
Итого: ~4 МБ

LinkedList (1 млн элементов):
Каждый элемент требует отдельный объект Node:
├── Заголовок объекта (Mark + Klass): 12 байт
├── Ссылка item: 4 байта
├── Ссылка next: 4 байта
├── Ссылка prev: 4 байта
└── Выравнивание (Padding до 8 байт): 0 байт (суммарно 24 байта)
1 000 000 узлов × 24 байта = 24 000 000 байт (~24 МБ)
Итого: ~24 МБ (в 6 раз больше, чем ArrayList!)

При отключенном Compressed OOPs узел Node занимает уже 40 байт (в 10 раз больше, чем ArrayList).

4. Почему `ArrayDeque` полностью вытеснил `LinkedList`

Исторически LinkedList использовали как реализацию стека или очереди (Queue / Deque). Сегодня для этих задач существует класс ArrayDeque:

Построен на кольцевом динамическом массиве без создания узлов Node;
Вставка и удаление с обоих концов выполняются за истинное амортизированное $O(1)$;
Не создает мусора для GC и обладает абсолютной кэш-локальностью;
Работает в 3–5 раз быстрее LinkedList в любых сценариях Producer-Consumer.

🎯 Шпаргалка для интервью

30-секундный ответ для собеседования

«ArrayList построен на непрерывном динамическом массиве, обеспечивает доступ по индексу за $O(1)$, обладает высокой локализацией данных в кэше процессора и минимальным расходом памяти (4 байта на ссылку). LinkedList — это двусвязный список объектов Node, где доступ по индексу требует $O(N)$ шагов, а каждый элемент порождает оверхед в 24–32 байта. Из-за аппаратных особенностей современных CPU (кэш-промахи при обходе разрозненных узлов LinkedList и векторные инструкции System.arraycopy в ArrayList) ArrayList превосходит LinkedList практически во всех сценариях. В качестве очередей и стеков вместо LinkedList всегда следует выбирать ArrayDeque».

Вопросы повышенной сложности с ответами

Почему LinkedList проигрывает ArrayList по скорости итерации в десятки раз, хотя сложность обхода у обоих $O(N)$? Ответ: Причина кроется в кэш-локальности (Cache Locality). В ArrayList элементы лежат в непрерывном участке памяти, и при первом обращении процессор загружает целую строку кэша (64 байта), обеспечивая попадание в быстрый кэш L1/L2 для последующих 8–16 элементов. В LinkedList каждый узел Node — это отдельный объект, аллоцированный сборщиком мусора в случайном месте кучи. Обход списка порождает постоянные промахи кэша процессора (Cache Misses), вынуждая ядра CPU простаивать сотни тактов в ожидании подгрузки каждого узла из оперативной памяти.
В чём заключается «иллюзия сложности» при вставке в начало LinkedList против ArrayList? Ответ: Теоретическая сложность вставки в начало LinkedList.add(0, e) равна $O(1)$, а ArrayList.add(0, e) — $O(N)$ из-за сдвига массива. Однако на практике вставка в LinkedList требует создания нового объекта Node, выделения памяти в куче и инициализации указателей, что создает задержку и нагрузку на GC. В ArrayList сдвиг массива выполняется системной функцией System.arraycopy(), использующей векторные SIMD-инструкции процессора. В результате для списков до 10–20 тысяч элементов ArrayList вставляет элементы в начало быстрее, чем LinkedList.
Сколько памяти расходует LinkedList по сравнению с ArrayList на миллионе элементов? Ответ: В 64-битной JVM с включенным сжатием ссылок (Compressed OOPs) ссылка в массиве ArrayList занимает 4 байта, то есть миллион элементов потребует около 4 МБ памяти. В LinkedList каждый элемент требует создания объекта Node, который содержит заголовок (12 байт), три ссылки по 4 байта (item, next, prev) — суммарно 24 байта (или 32 байта с выравниванием в ряде JVM-архитектур). Таким образом, LinkedList потребует от 24 до 32 МБ, то есть в 6–8 раз больше памяти, одновременно создавая миллион дополнительных объектов для сборщика мусора.
Существуют ли реальные сценарии в современном Java-коде, где LinkedList предпочтительнее ArrayList? Ответ: Единственный узкоспециализированный сценарий — когда в процессе итерации по огромному списку (сотни тысяч элементов) требуется массово удалять элементы через iterator.remove(), при условии, что нельзя предварительно профильтровать список через list.removeIf(). Во всех остальных задачах (включая работу в качестве очереди FIFO или стека LIFO) LinkedList полностью уступает ArrayList и ArrayDeque.

Типичные ошибки и Red Flags

❌ Утверждать, что LinkedList быстрее ArrayList при вставке в середину. (Red Flag: непонимание того, что до середины списка сначала нужно дойти за $O(N)$ шагов).
❌ Утверждать, что LinkedList эффективнее по памяти, так как «не выделяет лишний массив про запас». (Грубая ошибка: оверхед на служебные объекты Node превышает 50% запас массива ArrayList в разы).
❌ Использовать LinkedList для реализации очереди задач вместо ArrayDeque. (Незнание более эффективных структур стандартной библиотеки).