sottoУстройство
LinkedList — двусвязный список: каждый элемент завёрнут в узел Node с ссылками prev и next и ссылкой на значение. Список хранит ссылки на первый и последний узлы.
Реализует и List, и Deque, поэтому добавление/снятие с обоих концов — честное O(1) по ссылкам на голову/хвост.
Реальная стоимость операций
Доступ по индексу get(i) — O(n): нужно пройти по ссылкам от ближайшего конца. Поиск contains — O(n). Вставка/удаление O(1) только если у вас уже есть ссылка на узел (например, через ListIterator).
Ключевой нюанс: «вставка в середину O(1)» почти всегда вводит в заблуждение, потому что сначала надо до этой середины дойти за O(n). Чистая O(1) достижима лишь при итераторной вставке.
List<String> list = new LinkedList<>(...);
// O(n) на каждый вызов: список каждый раз идёт от ближайшего конца
for (int i = 0; i < list.size(); i++) sum += list.get(i).length(); // итого O(n^2)
// честная O(1) вставка — только когда позиция уже в руках у итератора
ListIterator<String> it = list.listIterator();
while (it.hasNext()) {
if (it.next().isBlank()) it.set("—"); // без повторного поиска позиции
}Цена памяти и кэша
Каждый элемент требует отдельный объект-узел с двумя ссылками и заголовком объекта — это в разы больше памяти, чем плотный массив ArrayList. Узлы разбросаны по куче, поэтому обход — это pointer chasing с постоянными промахами кэша.
Из-за этого на практике LinkedList часто медленнее ArrayList даже там, где «по асимптотике» должен выигрывать: константа и поведение кэша решают.
Когда выбирать
Почти никогда как List общего назначения — по умолчанию берут ArrayList. Если нужна очередь/дек, современный выбор — ArrayDeque (плотный массив, лучше кэш), а не LinkedList.
Реальные ниши LinkedList узки: интенсивные вставки/удаления строго через итератор по ходу обхода, или когда нужны одновременно List и Deque в одном объекте.
Как отвечать на собеседовании
Сильный ход — развенчать миф: назвать O(n) на доступ и на достижение позиции вставки, объяснить оверхед узлов и промахи кэша, и сделать вывод, что ArrayList/ArrayDeque почти всегда предпочтительнее. Это отличает понимание от заученного «LinkedList хорош для вставок».