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

Короткий ответ

Различие — во внутренней структуре. ArrayList построен на динамическом массиве Object[]: доступ по индексу — O(1), вставка или удаление в середине — O(n) из-за сдвига, добавление в конец — амортизированно O(1). LinkedList — двусвязный список: каждый элемент обёрнут в узел со ссылками на соседей; вставка в найденную позицию сводится к перестановке ссылок, но поиск позиции идёт перебором за O(n).

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

ArrayList хранит элементы в массиве, который автоматически расширяется при заполнении; элементы лежат подряд, поэтому итерация быстрая и хорошо используется кэш процессора. LinkedList на каждый элемент создаёт отдельный объект-узел со ссылками на предыдущий и следующий; узлы разбросаны по памяти, поэтому структура проигрывает и ArrayList, и более современным коллекциям.

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

Пример кода

ListDemo.javaКопировать

List<String> list = new ArrayList<>();
list.add("a");            // в конец, в среднем O(1)
String s = list.get(0);    // по индексу O(1)
LinkedList<String> linked = new LinkedList<>();
linked.add("a");
linked.add(0, "b");       // поиск позиции перебором — O(n)

Что использовать на практике

• По умолчанию берите ArrayList: он быстрее в большинстве сценариев — доступ по индексу, итерация, добавление в конец.
• LinkedList оправдан при работе преимущественно с началом или концом списка, но для таких задач в Java есть ArrayDeque.
• Если нужна очередь или дек — используйте ArrayDeque, а не LinkedList.

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

• Вставка в произвольную позицию у LinkedList дешёвая только после того, как узел найден, а сам поиск позиции — O(n).
• Вставка в середину ArrayList стоит O(n) даже при найденном индексе — из-за сдвига элементов.
• Выбор LinkedList «ради быстрых вставок» без учёта стоимости поиска позиции — частая ошибка на собеседованиях.

Как отвечать на собеседовании

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