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

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

Как это работает

ArrayList внутри хранит элементы в обычном Java-массиве (Object[]). При добавлении элемента в конец, если массив заполнен, создается новый массив большего размера, и элементы копируются — это амортизированная операция O(1). Доступ по индексу — это прямое обращение к элементу массива, поэтому выполняется за O(1). Однако вставка или удаление элемента в середине требует сдвига всех последующих элементов, что занимает O(n) времени.

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

Сравнение операций

Когда использовать

ArrayList — выбор по умолчанию для большинства задач. Он эффективен для чтения по индексу, итерации и добавления в конец. Памяти потребляет меньше, а операции выполняются быстрее благодаря локальности данных в массиве.

LinkedList оправдан в редких случаях:

• Частые вставки или удаления в начале или середине списка, когда важна скорость этих операций, а доступ по индексу не критичен.
• Реализация очереди или стека вручную с использованием методов addFirst, removeFirst, addLast, removeLast.

Однако даже для очередей и стеков в Java есть специализированные классы (ArrayDeque), которые обычно работают быстрее LinkedList.

Подводные камни

• LinkedList не всегда быстрее при вставке в середину: операция add(index, element) сначала ищет узел по индексу (O(n)), и только потом вставляет (O(1)). Поэтому выигрыш проявляется только при работе с итератором или ссылкой на узел.
• ArrayList при частых вставках в начало приводит к постоянному сдвигу всех элементов — это очень медленно.
• Оба класса не синхронизированы. Для многопоточного доступа используйте CopyOnWriteArrayList или обертки из Collections.synchronizedList.

Коротко

• ArrayList — массив, быстрый доступ по индексу, медленная вставка/удаление в середине.
• LinkedList — двусвязный список, быстрая вставка/удаление с известной позицией, медленный доступ по индексу.
• По умолчанию выбирайте ArrayList; LinkedList — только для специфических сценариев с частыми вставками в начало/середину.