ArrayList против LinkedList

Классика собеседований: два списка, одна и та же задача, но совсем разное поведение под нагрузкой.

Вопрос с собеседования: «У вас список из миллиона элементов. Нужно часто вставлять элементы в начало. Что выберете — ArrayList или LinkedList и почему?»

Большинство кандидатов сразу отвечают «LinkedList, у него вставка быстрее». И это только половина правды — а на собеседовании важна именно вторая половина.

Что выведет этот код?

Начнём с кода, чтобы увидеть проблему своими глазами.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> arrayList = new ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();

        for (int i = 0; i < 100000; i++) {
            arrayList.add(0, i);   // вставка в начало
            linkedList.add(0, i);  // вставка в начало
        }

        System.out.println("ArrayList size: " + arrayList.size());
        System.out.println("LinkedList size: " + linkedList.size());
    }
}

Вывод:

ArrayList size: 100000
LinkedList size: 100000

Результат одинаковый, а вот время выполнения — нет. На реальной машине вставка ста тысяч элементов в начало ArrayList займёт заметно больше времени, чем в LinkedList. Разберёмся, почему.

Как это работает под капотом

ArrayList внутри — это обычный массив, который сайт хранит в приватном поле. Когда ты обращаешься по индексу, Java просто вычисляет адрес ячейки и берёт значение — это одна операция, не важно, элемент это номер 5 или номер 500000. Поэтому доступ по индексу у ArrayList — O(1), константное время.

Но у массива фиксированный размер. Когда ты вставляешь элемент в середину или в начало, Java физически сдвигает все элементы справа от точки вставки на одну позицию вправо (через System.arraycopy), а потом уже кладёт новый элемент. Вставить в начало массива из миллиона элементов — значит сдвинуть весь миллион. Это O(n), линейное время, и чем длиннее список, тем дольше.

LinkedList устроен иначе — это двусвязный список: каждый элемент («узел») хранит своё значение и две ссылки — на предыдущий и следующий узел. Вставка в начало — это просто создать новый узел и переставить пару ссылок у соседних узлов. Не важно, сколько элементов в списке — операция всегда занимает одно и то же время, O(1).

А вот доступ по индексу у LinkedList — это, наоборот, слабое место. Чтобы получить элемент номер 500000, Java должна пройти по цепочке ссылок от начала (или от конца, если так короче) ровно 500000 раз. Это O(n) — и именно поэтому linkedList.get(i) в цикле — частая ошибка начинающих, превращающая обход списка в квадратичную сложность.

Таблица-памятка

Почему LinkedList «быстрая вставка» — не всегда правда на практике

Вот тут кроется главная ловушка вопроса. Формула «вставка в LinkedList — O(1)» верна только тогда, когда у тебя уже есть ссылка на нужный узел — например, ты используешь Iterator и вставляешь прямо во время обхода. А метод linkedList.add(index, value) сначала должен дойти до этого индекса — то есть проходит O(n), а потом уже вставляет за O(1). Итоговая сложность всё равно O(n), точно как у ArrayList.

Более того, из-за современных процессоров с кэшированием ArrayList на практике часто быстрее LinkedList даже там, где теория обещает обратное. Массив лежит в памяти одним непрерывным куском, и процессор эффективно подгружает его в кэш. А узлы LinkedList разбросаны по кучe как попало — каждый переход по ссылке может быть промахом кэша, что на практике заметно медленнее «в теории быстрой» O(1)-операции.

Частые ошибки на собеседовании

• Отвечать шаблоном без объяснения. «LinkedList быстрее для вставки» — правда лишь наполовину. Хороший ответ объясняет: быстрее — только если вставка идёт через итератор, а не по индексу.
• Забывать про доступ по индексу. Если в задаче преобладает чтение по индексу (например, ты часто обращаешься к элементу в середине списка), LinkedList будет вообще неудачным выбором — несмотря на «быструю вставку».
• Не упоминать память. Каждый узел LinkedList — это отдельный объект в куче с двумя ссылками, а значит, накладные расходы на память выше, чем у плотного массива в ArrayList.
• Игнорировать реальные измерения. На собеседовании ценится ответ «в 90% случаев по умолчанию беру ArrayList, а LinkedList — только если знаю, что паттерн доступа это оправдывает» — это показывает практическое мышление, а не зубрёжку Big O.

Итоги-шпаргалка

• ArrayList — быстрый доступ по индексу O(1), медленная вставка в начало/середину O(n).
• LinkedList — быстрая вставка/удаление O(1), но только если у тебя уже есть ссылка на узел (например, через итератор); доступ по индексу — O(n).
• По умолчанию в реальных проектах чаще берут ArrayList — из-за кэш-дружелюбности памяти и того, что доступ по индексу нужен чаще, чем вставка в произвольное место.
• LinkedList оправдан, когда ты постоянно добавляешь/удаляешь элементы на краях (как очередь или дек) — не зря он реализует интерфейс Deque.