Всем привет, меня зовут Сергей Прощаев, и в этой статье расскажу, почему один из самых старых споров в Java — ArrayList или LinkedList — до сих пор решается неправильно. Причём теперь неправильно его решают не только джуны на собеседованиях, но и языковые модели, которым мы всё чаще доверяем выбор структуры данных.

Я Tech Lead и руководитель направления Java | Kotlin разработки в FinTech & E‑commerce и преподаю на курсах разработки и архитектуры в ОТУС. За годы найма и код‑ревью я видел этот выбор сотни раз. И вот что любопытно: ответ, который дают на автомате, почти всегда расходится с тем, что показывает железо. А с приходом ИИ‑ассистентов разрыв стал заметнее, а не меньше.

Откуда вообще взялся этот спор

Любой, кто готовился к собеседованию по Java, знает «правильный» ответ наизусть. ArrayList — динамический массив: доступ по индексу за O(1), вставка и удаление в середине за O(n) из‑за сдвига элементов. LinkedList — двусвязный список: доступ за O(n), зато вставка и удаление за O(1), ведь надо лишь перецепить пару ссылок.

Вывод напрашивается сам: много вставок и удалений — LinkedList, много чтений по индексу — ArrayList. Красиво, логично, ложится в таблицу из двух колонок.

Проблема не в самой нотации, а в её учебной интерпретации, которая формировалась в эпоху, когда разрыв между скоростью процессора и памяти был куда меньше сегодняшнего. Сейчас обращение к данным, которых нет в кэше, может стоить на два‑три порядка дороже арифметической инструкции. И эта перемена ломает всю красивую таблицу из двух колонок.

Помню, как на ревью мне прислали сервис обработки котировок, где горячий путь был построен на LinkedList — «потому что там частые вставки». На деле код в основном не вставлял, а постоянно обходил коллекцию на каждый тик. Когда мы прогнали бенчмарк, замена на ArrayList ускорила горячий путь в несколько раз — ровно за счёт обхода. Реакция автора была классическая: «Но ведь Big O говорит обратное». Big O действительно говорит обратное. Просто Big O абстрагируется от стоимости отдельных операций и поэтому ничего не говорит о поведении кэшей.

Почему ИИ повторяет ту же ошибку

Казалось бы, при чём здесь ИИ. А вот при чём. Языковые модели обучены на гигантских объёмах кода и текстов за десятилетия — и впитали весь учебный фольклор: тысячи статей, ответов на Stack Overflow и методичек с тезисом «нужны частые вставки — используй LinkedList».

Сразу оговорюсь честно, чтобы не было ощущения дешёвой сенсации: проигрывает практике не сам по себе ИИ как технология, а тот учебный консенсус двадцатилетней давности, который модель добросовестно пересказывает. ИИ здесь не злодей и не дурак — он зеркало, и зеркало довольно точное: в нём отражается то, чему мы сами его научили. Но пользоваться этим зеркалом как истиной в последней инстанции опасно, и сейчас покажу почему.

Мне как‑то стало интересно, и я задал нескольким популярным ассистентам один вопрос: «В Java много вставок и удалений в коллекцию, что выбрать для производительности?» И, как и предполагал, получил уверенные рекомендации в духе «для частых вставок и удалений LinkedList предпочтительнее, операции за константное время». Формально модель пересказала учебник. Фактически дала совет, который на современном железе чаще всего сделает код медленнее.

Это не «галлюцинация» в привычном смысле — модель не выдумала факт, а воспроизвела устаревший консенсус, который численно доминирует в её обучающих данных. И вот тут главная ловушка для разработчика 2026 года: ИИ‑ассистент звучит уверенно, отвечает мгновенно и опирается на «общеизвестное» — а «общеизвестное» в случае с LinkedList уже лет двадцать как разошлось с реальностью. ИИ отлично усредняет то, что написали люди; но если люди в среднем ошибались, он усреднит ошибку и подаст её с уверенным лицом. Проверять руками всё равно придётся нам.

DIY: ставим эксперимент сами

Давайте не верить ни мне, ни ИИ, а замерим. Золотой стандарт микробенчмарков в Java — это JMH (Java Microbenchmark Harness): он сам прогревает JVM, гоняет итерации, борется с устранением «мёртвого» кода и даёт статистику. Для серьёзных замеров берите его. Но чтобы статью можно было повторить без единой внешней зависимости — просто javac и java — я написал компактный харнесс, который заимствует несколько базовых идей JMH: фаза прогрева, медиана по нескольким итерациям, батч операций на измерение и накопление результата в поле‑«чёрную дыру», чтобы JIT не выкинул вычисления.

Это именно базовые идеи, а не замена: тут нет ни форк‑процессов, ни контроля tiered‑компиляции, ни защиты от OSR‑эффектов, ни статистики уровня JMH.Главное правило: никогда не мерьте время операции голым System.nanoTime() без прогрева. JIT либо ещё не скомпилировал горячий код, либо соптимизирует пустой цикл в ничто, и вы измерите шум. Прогрев и батчинг — не украшательство, а минимально честная методика.

Главное правило: никогда не мерьте время операции голым System.nanoTime() без прогрева. JIT либо ещё не скомпилировал горячий код, либо соптимизирует пустой цикл в ничто, и вы измерите шум. Прогрев и батчинг — не украшательство, а минимально честная методика.

import java.util.*;

public class Bench {

    static long blackhole = 0L;            // против dead-code elimination
    static final int WARMUP = 8;           // прогревочные прогоны (отбрасываем)
    static final int ITERS  = 11;          // измерительные итерации (берём медиану)

    public static void main(String[] args) {
        for (int size : new int[]{1_000, 100_000}) {
            int iterBatch   = size <= 1_000 ? 1_000 : 50;
            int insertBatch = size <= 1_000 ? 2_000 : 100;

            List<Integer> al = build(new ArrayList<>(), size);
            List<Integer> ll = build(new LinkedList<>(), size);

            print("iterate", size,
                  medianIter(al, iterBatch),
                  medianIter(ll, iterBatch));

            print("insert middle", size,
                  medianInsert(true,  size, size / 2, insertBatch),
                  medianInsert(false, size, size / 2, insertBatch));

            print("insert head", size,
                  medianInsert(true,  size, 0, insertBatch),
                  medianInsert(false, size, 0, insertBatch));
        }
        System.out.println("(blackhole=" + blackhole + ")");
    }

    static double medianIter(List<Integer> list, int batch) {
        for (int w = 0; w < WARMUP; w++) for (int b = 0; b < batch; b++) iterate(list);
        double[] s = new double[ITERS];
        for (int i = 0; i < ITERS; i++) {
            long t0 = System.nanoTime();
            for (int b = 0; b < batch; b++) iterate(list);
            s[i] = (System.nanoTime() - t0) / 1_000.0 / batch;
        }
        Arrays.sort(s);
        return s[ITERS / 2];
    }

    static double medianInsert(boolean array, int size, int pos, int batch) {
        for (int w = 0; w < WARMUP; w++) {
            List<Integer> l = fresh(array, size);
            l.add(pos, 42);
            blackhole += l.size();
        }
        double[] s = new double[ITERS];
        for (int i = 0; i < ITERS; i++) {
            long total = 0;
            for (int b = 0; b < batch; b++) {
                List<Integer> l = fresh(array, size);
                long t0 = System.nanoTime();
                l.add(pos, 42);
                total += System.nanoTime() - t0;
                blackhole += l.size();
            }
            s[i] = total / 1_000.0 / batch;
        }
        Arrays.sort(s);
        return s[ITERS / 2];
    }

    static List<Integer> fresh(boolean array, int n) {
        return build(array ? new ArrayList<>() : new LinkedList<>(), n);
    }
    static List<Integer> build(List<Integer> l, int n) {
        for (int i = 0; i < n; i++) l.add(i);
        return l;
    }
    static void iterate(List<Integer> list) {
        long sum = 0;
        for (Integer v : list) sum += v;
        blackhole += sum;
    }
    static void print(String name, int size, double al, double ll) {
        String faster = al < ll ? "ArrayList" : "LinkedList";
        double ratio  = al < ll ? ll / al : al / ll;
        System.out.printf("%-14s size=%-7d AL=%9.3f  LL=%9.3f мкс  ->  %s в %.1fx%n",
                name, size, al, ll, faster, ratio);
    }
}

Компилируется и запускается двумя командами: javac Bench.java и java Bench.

На моём прогоне в контейнере программа напечатала такой вывод (AL — ArrayList, LL — LinkedList, время в микросекундах, меньше — быстрее):

iterate        size=1000    AL=    0.828  LL=    3.311 мкс  ->  ArrayList в 4.0x
insert middle  size=1000    AL=    0.185  LL=    0.794 мкс  ->  ArrayList в 4.3x
insert head    size=1000    AL=    0.217  LL=    0.056 мкс  ->  LinkedList в 3.9x
iterate        size=100000  AL=  175.042  LL=  294.708 мкс  ->  ArrayList в 1.7x
insert middle  size=100000  AL=    6.613  LL=  205.384 мкс  ->  ArrayList в 31.1x
insert head    size=100000  AL=   17.123  LL=    0.628 мкс  ->  LinkedList в 27.3x

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

Что показывает эксперимент

Условия для протокола: контейнерная среда, OpenJDK 21, фиксированный heap и ParallelGC, а не «боевой» сервер. Контейнер вносит шум, поэтому абсолютные миллисекунды некалиброванные: для крупных эффектов вроде cache locality точности харнесса хватает, а для тонких различий я бы брал JMH.

Вот что получилось (медиана времени на одну операцию, усреднено по нескольким прогонам, меньше — лучше):

И вот здесь начинается самое интересное. Важная деталь методики: построение коллекции вынесено за пределы таймера, а измеряется полный вызов add(index, e) именно так, как он используется в реальном коде. Разберём таблицу по строкам.

На обходе коллекции ArrayList выигрывает на любом размере. Причина не в алгоритме, а в том, как лежит память. Элементы массива расположены подряд, и процессор, подтягивая элемент в кэш, заодно затягивает соседей целой кэш‑линией — обход превращается в чтение непрерывной ленты. У LinkedList каждый узел — отдельный объект, потенциально разбросанный по куче (свежие узлы из одного TLAB ещё могут лежать рядом, но после нескольких сборок мусора локальность теряется), и чтобы добраться до следующего, процессор то и дело идёт по ссылке в непредсказуемое место памяти.

Это и есть pointer chasing, и каждый такой прыжок — потенциальный промах кэша. На большой коллекции разрыв на обходе даже сократился: оба упираются в пропускную способность памяти, но LinkedList всё равно позади. Направление однозначное — как и обещает «новый» консенсус.

А вот вставка в середину — самое поучительное место таблицы, и тут важно быть точным в формулировках, иначе любой сеньор справедливо придерётся. Теоретическая O(1)‑вставка у LinkedList относится к случаю, когда позиция уже найдена. Но вызов add(index, e) сначала ищет узел по индексу, а уже потом вставляет. То есть здесь соревнуются не «O(1) против O(n)», а две O(n)‑операции с совершенно разной константой: у LinkedList это поиск узла плюс дешёвая перевязка ссылок, у ArrayList — копирование непрерывного блока через System.arraycopy. И ArrayList выигрывает на обоих размерах, а на большой коллекции — в десятки раз.

Разгадка как раз в константе: чтобы дойти до середины, LinkedList шагает к ней половиной списка с pointer chasing — десятки тысяч прыжков по потенциально некэшированной памяти, тогда как System.arraycopy гонит непрерывный блок потоково, и процессор с контроллером памяти делают это очень быстро. Контринтуитивно, но «дорогой» сдвиг массива оказывается дешевле «дешёвой» вставки в список: список сначала надо обойти. С готовым итератором на нужную позицию расклад был бы другим — но в реальном коде вы почти всегда вставляете по индексу.

Вставка в начало — единственный сценарий, где LinkedList стабильно побеждает на любом размере: ArrayList вынужден сдвигать все элементы, а LinkedList просто цепляет узел к голове за константное время. Если ваша нагрузка — именно частые вставки в начало, LinkedList имеет право на жизнь. Но честно: как часто в продакшене это узкое место? За свою практику вспомню пару случаев, и оба лучше решались через ArrayDeque.

И ещё аргумент, который часто забывают, хотя для сеньора он очевиден: дело не только в скорости доступа, но и в памяти. Посмотрите, что физически хранится в пересчёте на один элемент (константные накладные самого списка и массива на больших коллекциях амортизируются).

На 64-битной JVM это разница в разы по накладным расходам на элемент: у ArrayList — практически только полезные ссылки подряд, а у LinkedList каждый элемент тащит за собой отдельный объект Node с заголовком и тремя ссылками. На больших коллекциях это ощутимый рост занимаемой памяти и, как следствие, может создавать дополнительное давление на сборщик мусора. То есть проблема LinkedList двойная: он и по скорости обхода проигрывает из‑за pointer chasing, и по памяти дороже из‑за обвязки вокруг каждого значения.

Ниже — схема того, что физически происходит при обходе. Ключевая деталь: дело не в количестве операций, а в том, куда именно процессор лезет за данными.

Главная мысль отсюда: алгоритмическая сложность описывает количество шагов, но молчит о стоимости одного шага. А на современном железе стоимость шага определяется не арифметикой, а попаданием в кэш. Два алгоритма с одинаковым O() могут отличаться по скорости на порядок лишь из‑за расположения данных в памяти.

Ретроспектива: что изменилось и куда идёт Java

Самое интересное, что Java‑платформа сама движется в сторону «памяти, удобной процессору», и прямо сейчас. В середине июня 2026 года произошло то, во что половина сообщества перестала верить: было объявлено об интеграции JEP 401 (Value Classes and Objects) в основной репозиторий OpenJDK с прицелом на JDK 28. Изменение настолько крупное, что остальных коммиттеров попросили временно придержать большие коммиты на время вливания. Проект Valhalla, про который шутили, что разработчики раньше попадут в скандинавскую Вальгаллу, чем он выйдет, наконец дал первый осязаемый результат.

Почему это касается нашего спора. Когда язык создавался около 25 лет назад, разрыв в скорости между процессором и памятью был относительно невелик. Сегодня же доступ к данным, отсутствующим в кэше, может обойтись на два‑три порядка дороже арифметической инструкции. Java — язык, где почти всё является ссылочным типом, то есть указателем на объект в куче. И именно поэтому структуры вроде LinkedList, целиком построенные на «прыжках по указателям», так больно бьются о современное железо.

JEP 401 вводит новый класс типов — value‑классы, у объектов которых нет объектной идентичности (обычные объекты со своей идентичностью никуда не деваются). Отсутствие идентичности открывает новые оптимизации, особенно для небольших объектов: value‑объекты позволяют JVM хранить данные плоско, без лишних заголовков и разыменований, ближе к примитивам.

Оговорюсь, чтобы не вводить в заблуждение: это не делает LinkedList внезапно быстрым — его Node остаётся обычным объектом. Но это показывает направление эволюции платформы: меньше разыменований, плотнее размещение данных — та же борьба за cache locality, только на уровне языка. И не обольщайтесь: это preview, выключенное по умолчанию, а полноценная специализация дженериков, из‑за которой ArrayList<Point> всё ещё материализует объекты в куче, — дело будущих релизов. Текущий JDK на момент написания — 26, JDK 27 ожидается в сентябре 2026.

Я смотрю на это так. Тридцать лет индустрия городила обходные пути вокруг одного факта: память дорогая, а прыжки по ней ещё дороже. Сначала интуитивно, а потом и с бенчмарками в руках мы поняли, что плоский ArrayList почти всегда лучше «алгоритмически правильного» LinkedList. Ретроспективно LinkedList оказался не столько «структурой для частых вставок», сколько памятником эпохе, когда указатель был бесплатным.

Эта история старше, чем кажется

Самое отрезвляющее, что наш Java‑спор — частный случай куда более старой и задокументированной истории. Ещё в 2012 году Бьярне Страуструп, создатель C++, на кейноуте Going Native показал залу простой эксперимент: вставлять случайные числа в отсортированную структуру, а потом по одному удалять в случайном порядке. Что быстрее — std::vector (непрерывный массив) или std::list (связный список)?

Зал, как положено, ставил на список — это его «родная» территория. Страуструп показал график, где vector уверенно обгоняет list, причём разрыв растёт с размером данных. Разгадка: основное время съедает не сама вставка, а проход до точки вставки. А обойти непрерывный блок памяти процессор с кэшем и префетчером умеет несоизмеримо быстрее, чем скакать по разбросанным узлам.

Мне попалась под этим докладом честная история разработчика: он написал «быстрый и грязный» тест для выбора между list и vector, получил тот же результат, что и Страуструп, — и всё равно выбрал список, решив, что где‑то ошибся. Узнаю в этом и себя, и половину инженеров. Вера в учебник сильнее графика.

С тех пор появились академические работы с говорящими названиями вроде «RIP Linked List», где авторы признают, что найти убедительный сценарий для связного списка на малых и средних объёмах данных тяжело. Рост RAM и скорости процессоров окончательно сместил баланс к непрерывным структурам. Java здесь не уникальна — она унаследовала ту же физику, что и C++.

Так что же выбирать на практике

Мой вариант, который я советую команде, — несколько простых правил.

По умолчанию берите ArrayList. В большинстве прикладных нагрузок он оказывается быстрее по совокупной стоимости типичных операций доступа, обхода, вставки и расхода памяти, потому что не платит за узел‑обёртку на каждый элемент. Нужна очередь или дек с быстрыми операциями с обоих концов — берите ArrayDeque, в большинстве практических сценариев он обходит LinkedList и здесь. LinkedList оставьте для редких случаев, когда вы упёрлись во вставки в начало больших коллекций и подтвердили это профайлером, а не интуицией.

И главное правило, которое я вынес за годы: не выбирайте структуру по таблице сложностей из головы и тем более не по первому ответу ИИ. Сложность — это гипотеза о производительности, а не сама производительность. Проверяйте на своих данных, своим бенчмарком, на своём железе. ИИ напишет вам этот бенчмарк за минуту — вот в этом он по‑настоящему полезен. А доверять ему финальный вывод пока рано: он слишком хорошо помнит учебники двадцатилетней давности.

Чтобы свести всё к маршруту, ниже — схема выбора, которой я пользуюсь на ревью. Смотрите на рисунок 3 как на короткий чек‑лист: он отвечает не «что быстрее по Big O», а «что взять по умолчанию, чтобы не выстрелить себе в ногу».

Главная мысль схемы: LinkedList здесь не центр, а тупиковая ветка, до которой надо дойти через профайлер. В девяти случаях из десяти маршрут заканчивается на ArrayList или ArrayDeque.

Если соберётесь проверять — начните с харнесса выше. Запустите, посмотрите на свои числа и, скорее всего, удивитесь так же, как я, когда ArrayList обыграл LinkedList на вставке в середину — там, где по учебнику список обязан был победить.

И последнее. Всё разобранное — частные проявления одной темы: как алгоритмическая сложность коллекций соотносится с тем, что реально делает железо. Если хочется разложить это системно, а не на отдельных примерах — на о‑нотацию, на сравнение коллекций по операциям, на осознанный выбор структуры под задачу, — у нас об этом есть отдельный разбор.

Разобраться глубже в том, как Java работает с коллекциями, памятью и производительностью, можно на бесплатных уроках OTUS: их проводят практикующие эксперты, а темы хорошо дополняют разбор ArrayList, LinkedList и выбора структур данных под реальные задачи.

• 1 июля в 20:00. «Алгоритмическая сложность коллекций в Java». Записаться

• 16 июля в 20:00. «Стоит ли учить Java в 2026: куда движется язык и где работают джависты». Записаться

• 23 июля в 20:00. «Основы многопоточности в Java». Записаться

Больше бесплатных уроков по разработке и не только смотрите в дайджесте.