Почему ArrayDeque быстрее LinkedList в роли стека или очереди

Вопрос звучит просто: «какую структуру используете как стек в Java». Многие по привычке называют LinkedList — она реализует Deque, у неё есть push() и pop(). Формально работает. Но вопрос проверяет не знание интерфейса, а понимание того, во что реально упирается производительность.

LinkedList — это узлы с указателями на соседей. Каждый push() — это выделение нового объекта Node в куче, плюс накладные расходы на GC для каждого удалённого узла. Плюс объекты разбросаны по памяти — кэш процессора промахивается чаще.

ArrayDeque хранит элементы в кольцевом массиве. Добавление и удаление с обоих концов — амортизированное O(1), без аллокации объекта на каждую операцию. Массив резервируется заранее и растёт как ArrayList, при необходимости.

В документации Java прямо написано: ArrayDeque обычно быстрее LinkedList в роли стека и быстрее LinkedBlockingQueue в роли очереди при однопоточном доступе. Единственный минус — ArrayDeque не допускает null-элементы, а LinkedList допускает.

Спросят следом: а зачем тогда LinkedList существует, если ArrayDeque почти всегда лучше как Deque? Ответ — LinkedList даёт O(1) вставку в середину через итератор, если у вас уже есть ListIterator на нужной позиции. ArrayDeque такого не даёт вообще — вставка не с краёв не поддерживается как операция интерфейса Deque.

Выбор структуры данных на собеседовании — это не «что реализует нужный интерфейс», а «что реализует его с наименьшими накладными расходами для конкретного паттерна доступа».

Тренажёр: 600 вопросов, мок с таймером, план повторов

senior·base — что спрашивают на самом деле

В этом посте были ссылки, но мы их удалили по правилам Сетки