ArrayList или LinkedList: чем отличаются и что выбрать
Что такое List
List — интерфейс из java.util, наследник Collection и Iterable. В отличие от Set, он гарантирует порядок элементов и доступ по индексу. В нём разрешены дубликаты и null — это отличает его от большинства реализаций Map и Set, где с null всё сложнее.
List — это контракт «упорядоченная последовательность с индексами», а не конкретная структура данных. Как именно она хранится в памяти — решает реализация, и от этого решения зависит вся производительность.
Что обязан уметь List
Контракт интерфейса включает базовые операции: add(E) и add(int, E), get(int), set(int, E), remove(int) и remove(Object), indexOf, contains, size, isEmpty, iterator и listIterator, subList. С Java 8 добавились дефолтные методы sort(Comparator) и removeIf.
Отдельно стоит запомнить пару remove(int) и remove(Object) — это два разных метода с разной сигнатурой, и путаница между ними — классическая ловушка, о которой ниже.
Кто реализует List
Основные реализации: ArrayList, LinkedList, устаревшие Vector и Stack (синхронизированные, но морально устаревшие), и CopyOnWriteArrayList для потокобезопасного чтения-без-блокировок. В прикладном коде почти всегда выбор идёт между ArrayList и LinkedList — их и сравниваем.
ArrayList изнутри
Внутри — обычный массив ссылок Object[] elementData, плюс поля size (сколько элементов реально занято) и modCount (счётчик структурных модификаций для fail-fast итератора).
Ёмкость по умолчанию — 10, но массив выделяется не в конструкторе, а лениво, при первом add. Пустой new ArrayList<>() первое время держит статический пустой массив.
Когда массив заполняется, он растёт в полтора раза:
newCapacity = oldCapacity + (oldCapacity >> 1);
Затем данные копируются в новый массив через System.arraycopy. Это амортизированная O(1) операция для добавления в конец: копирования случаются редко, а между ними — просто запись в ячейку.
Вставка и удаление в середине или начале — другая история: приходится сдвигать весь хвост массива через arraycopy, это O(n). Есть методы ensureCapacity(int) — заранее расширить массив, если знаете примерный размер, и trimToSize() — обрезать лишний запас, если список больше не будет расти.
LinkedList изнутри
LinkedList — двусвязный список. Каждый элемент — отдельный объект Node с полями item, prev, next. Сам список хранит ссылки first, last, а также size и modCount. Заодно LinkedList реализует Deque, поэтому умеет работать как очередь и как стек.
get(index) не хранит массив со случайным доступом — приходится идти по цепочке ссылок. Реализация оптимизирована: если индекс меньше size/2, обход стартует с first, иначе — с last. Это уменьшает число шагов вдвое, но всё равно даёт O(n), а не O(1).
Таблица сложностей
- Доступ по индексу (get): ArrayList — O(1), LinkedList — O(n).
- Добавление в конец: ArrayList — амортизированное O(1), LinkedList — O(1) (есть прямая ссылка на last).
- Вставка/удаление в начало: ArrayList — O(n) (сдвиг всего массива), LinkedList — O(1).
- Вставка/удаление в середину: ArrayList — O(n) (сдвиг хвоста), LinkedList — O(n) (нужно сначала дойти до места, только сама вставка O(1)).
- Поиск по значению (contains, indexOf): O(n) у обоих — линейный перебор в любом случае.
Ключевой нюанс: вставка в середину у LinkedList теоретически «дешевле» — сама операция O(1), — но чтобы до этой середины дойти, всё равно нужен линейный проход. На практике итоговая стоимость сопоставима с ArrayList, а часто и хуже.
Память и процессор — где LinkedList проигрывает по-настоящему
ArrayList — это один сплошной массив ссылок в памяти, с некоторым запасом пустых ячеек сверх size. Данные лежат подряд, современный процессор с предвыборкой (prefetch) читает такие структуры очень эффективно — попадания в кэш почти гарантированы.
LinkedList — это отдельный объект-узел на каждый элемент, с тремя полями-ссылками (item, prev, next), и эти узлы создаются в куче в произвольном порядке — они разбросаны по памяти. Проход по такой структуре means постоянные кэш-миссы: процессор прыгает по случайным адресам, вместо того чтобы читать соседние ячейки одним заходом.
Именно поэтому на практике LinkedList проигрывает ArrayList даже в тех операциях, где по асимптотике формально должен выигрывать — например, во вставке в начало списка при небольших и средних объёмах данных. Разница в реальных бенчмарках может быть в разы не в пользу LinkedList из-за оверхеда на создание объектов узлов и промахи кэша.
Что выбирать на практике
Почти всегда — ArrayList. Это дефолтный выбор для 95% задач: он компактнее по памяти, быстрее по чтению и в среднем быстрее даже там, где LinkedList «должен» выигрывать.
LinkedList оправдан, когда список используется как очередь или дек с частыми добавлениями/удалениями на обоих концах и без доступа по индексу. Но и в этом случае почти всегда лучше подойдёт ArrayDeque — он построен на кольцевом массиве, не создаёт объекты-узлы под каждый элемент и по производительности обычно превосходит LinkedList даже в его «родной» роли очереди.
Типичные ошибки
list.remove(5) удаляет элемент по индексу 5, а не значение 5. Если нужно удалить именно значение, пишут list.remove(Integer.valueOf(5)) — тогда компилятор выберет перегрузку remove(Object). Путают эти две сигнатуры регулярно, особенно с автоупаковкой int/Integer.ConcurrentModificationException — итератор фиксирует modCount на старте и проверяет его на каждом next(). Правильный способ — iterator.remove() через явный Iterator, либо метод removeIf(Predicate), появившийся в Java 8 и корректно работающий со structural modification.List.of(...) возвращает неизменяемый список — любой mutator бросит UnsupportedOperationException. Arrays.asList(...) возвращает список фиксированного размера — можно менять элементы через set, но нельзя add/remove.Если известен примерный размер коллекции — стоит сразу указать ёмкость в конструкторе: new ArrayList<>(1000). Это избавит от нескольких перевыделений массива и копирований по мере роста.