Java LinkedList

LinkedList<E> — это двусвязный список: каждый элемент живёт в собственном узле кучи с указателем на следующий узел и указателем на предыдущий. Это даёт ему профиль производительности, противоположный ArrayList: вставка и удаление на концах — O(1), но get(i) вынужден обходить список от одного конца до нужного индекса — O(n). Класс также является единственным встроенным в Java List, который реализует Deque<E>, поэтому он служит ещё и очередью. В этой главе объясняется, когда такая комбинация является правильным инструментом, и (чуть более длинный) список случаев, когда это не так.

Структура данных

Каждый элемент представляет собой узел:

node:  prev ←—— element ——→ next

Список хранит две ссылки на поля — first и last — и счётчик size. Чтобы добавить элемент на любой конец, нужно выделить узел, вставить его, скорректировав два указателя, и увеличить size. Никакого массива, никакого изменения размера, никакой свободной памяти. В этом и состоит привлекательность.

Издержки проявляются везде в остальном:

• Каждый элемент платит за объект-узел — три ссылки и заголовок объекта. Накладные расходы памяти на элемент намного выше, чем у плоского массива ArrayList.
• get(i), set(i, x), add(i, x), remove(i) — все они обходят список от ближайшего конца. Таким образом, list.get(size/2) — это O(n/2). Для длинных списков это становится очень дорогим.
• Локальность кэша плохая — узлы разбросаны по куче, поэтому обход промахивается мимо кэша CPU и замедляется даже тогда, когда алгоритм выглядит линейным.

Когда LinkedList является правильным выбором

Честный ответ в 2026 году: редко в роли List, иногда в роли Deque, почти никогда для «ускорения вставок». Народная мудрость «используйте LinkedList, потому что будете вставлять» не выдержала испытания временем — для большинства рабочих нагрузок кэш-дружелюбность ArrayList вместе с его амортизированным O(1) добавлением в конец превосходит дополнительные издержки на преследование указателей в связном списке, даже когда алгоритм иногда вызывает add(0, x). Случаи, когда LinkedList действительно выигрывает:

• Вам нужна Deque (добавление/удаление на обоих концах), и у вас нет ArrayDeque в области видимости. ArrayDeque быстрее; LinkedList привычнее.
• Вы держите постоянные ссылки на конкретные узлы (через ListIterator) и хотите O(1) вставки/удаления именно в этих позициях. Это классический учебный пример использования связного списка — и он почти никогда не встречается в повседневном Java.
• Вам нужна реализация Queue, которая также открывает методы List для инспекции. Реальный пример: очередь задач, которую иногда нужно выгрузить в лог.

Для «списка, к которому добавляешь и читаешь по индексу», используйте ArrayList. Для «очереди или двухсторонней очереди» используйте ArrayDeque. LinkedList находится между ними и редко является лучшим вариантом для какой-либо из задач.

Создание и использование в роли List

Половина API, относящаяся к List, идентична ArrayList:

List<String> tasks = new LinkedList<>();
tasks.add("compile");
tasks.add("test");
tasks.add(0, "lint");          // O(1) — at the head
String first = tasks.get(0);   // O(1) — head
String last  = tasks.get(tasks.size() - 1);   // O(1) — tail
String mid   = tasks.get(tasks.size() / 2);   // O(n/2) — has to walk

Конструктор не имеет параметра ёмкости — нечего предварительно задавать, потому что узлы выделяются по одному.

Использование в роли Queue и Deque

Поскольку LinkedList реализует и Queue<E>, и Deque<E>, вы получаете методы очереди поверх методов List:

Deque<String> stack = new LinkedList<>();
stack.push("a");          // adds to head
stack.push("b");
String top = stack.pop(); // removes from head → "b"

Queue<String> jobs = new LinkedList<>();
jobs.offer("j1");         // adds to tail
jobs.offer("j2");
String next = jobs.poll();// removes from head → "j1"

Если ваша потребность — исключительно «очередь FIFO» или «стек LIFO», объявите переменную как Queue<E> или Deque<E> — и предпочтите new ArrayDeque<>() в качестве реализации. Интерфейс тот же; реализация на основе массива заметно быстрее.

Итерация и ConcurrentModificationException

Та же модель fail-fast, что и в ArrayList. Изменение во время цикла for-each бросает исключение:

LinkedList<Integer> xs = new LinkedList<>(List.of(1, 2, 3, 4));
for (int x : xs) if (x % 2 == 0) xs.remove(Integer.valueOf(x));  // throws

removeIf и явный Iterator.remove() — две безопасные формы — идентично главе об ArrayList. Интересная особенность LinkedList — ListIterator: поскольку итератор держит прямую ссылку на текущий узел, его add и remove действительно O(1). Если вам действительно нужна быстрая вставка при итерации по позиции, LinkedList.listIterator() — это API, который выполняет то, что обещают учебники.

Потокобезопасность

Та же история, что и с ArrayList: никакой. Используйте Collections.synchronizedList(new LinkedList<>()) для блокировки всего списка или — что намного лучше — ConcurrentLinkedDeque, если ваш вариант использования действительно является параллельной очередью.

Сравнение с ArrayDeque в одном абзаце

Когда вы тянетесь к LinkedList, чтобы использовать его как очередь или стек, сначала посмотрите на ArrayDeque. ArrayDeque — это кольцевой массив: нет узла на каждый элемент, нет погони за указателями, нет правил об отклонении null, которые нужно помнить. На больших реальных нагрузках стека/очереди он обычно превосходит LinkedList — иногда со значительным отрывом — потому что избегает узла кучи и заголовка на каждый элемент и держит данные непрерывно в памяти. Единственный реальный его недостаток — он не реализует List. (Не переоценивайте небольшие бенчмарки ни в ту, ни в другую сторону; см. проработанный пример ниже.)

Проработанный пример: одна задача, две структуры данных

Программа ниже строит одну и ту же очередь с ArrayList, LinkedList и ArrayDeque — добавляет на один конец, забирает с другого 200 000 раз — и выводит время настенных часов для каждого. Читайте числа в контексте: это грубый, однократный микробенчмарк на холодной JVM, а не строгий результат, поэтому воспринимайте относительный порядок — а не точные миллисекунды — как урок. ArrayList драматически медленнее двух других, потому что remove(0) — O(n), и цикл слива становится квадратичным. LinkedList и ArrayDeque оба быстры: каждый выполняет O(1) работы в начале. Кто из них двух окажется впереди, зависит от машины, JIT и упаковки Integer — именно поэтому никогда не следует полагаться на такой маленький бенчмарк при выборе между ними.

Два вывода:

• Первые два замера показывают, почему никогда не индексируйте LinkedList в цикле. Форма for-each проходит список один раз за O(n); форма с индексом проходит его по разу на каждый индекс, давая O(n²). Для 10 000 элементов это уже болезненно; для 100 000 — это секунды.
• Три замера очереди показывают настоящий водораздел: он проходит между ArrayList (квадратичный слив) и двумя структурами с O(1) на головном конце, а не между LinkedList и ArrayDeque. Как только вы исключили ArrayList для работы с очередью, в любом случае предпочтите ArrayDeque — он не выделяет узел на каждый элемент и имеет гораздо лучшую локальность кэша на больших долгоживущих очередях, что холодный старт с 200 000 элементов полностью не раскрывает. Единственная оставшаяся реальная причина использовать LinkedList — «мне нужна Deque и List одновременно», и даже это редкость.

Что дальше

LinkedList и ArrayList — две интересные реализации List общего назначения. Третья — старше, синхронизирована, в основном историческая — это Vector. Знание того, почему это не правильный выбор в новом коде, является частью беглого владения фреймворком.

Практика