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

ArrayList хранит элементы в массиве, поэтому вычисляет адрес элемента по индексу за O(1). LinkedList хранит элементы в связанных узлах, поэтому для доступа по индексу нужно пройти по ссылкам; в худшем случае это O(n).

Исторический контекст

Интерфейс List отделяет контракт последовательности элементов от способа хранения данных. Это позволяет выбирать реализацию под характер операций: быстрый индексный доступ, вставки, удаления или работу с концами последовательности.

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

Постановка проблемы

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

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

Подробное решение

В ArrayList элементы находятся во внутреннем массиве. Для индекса i реализация обращается к ячейке с соответствующим смещением, поэтому стоимость get(i) не зависит от положения элемента и составляет O(1). Расширение внутреннего массива происходит не на каждом добавлении, а при нехватке места; это влияет прежде всего на амортизированную стоимость добавления в конец.

В LinkedList каждый элемент представлен узлом со ссылками на соседние узлы. Чтобы получить элемент по индексу, нужно начать с начала или конца списка и переходить по ссылкам; реализация выбирает более близкий конец. Поэтому точная оценка — O(min(i, n - i)), а общая и худшая — O(n).

У ArrayList вставка или удаление в середине обычно имеют сложность O(n) из-за сдвига элементов. У LinkedList изменение связей после уже найденного узла занимает O(1), но поиск этого узла по индексу сам по себе стоит O(n).

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

Минимальный пример показывает, почему одна и та же операция интерфейса List имеет разную стоимость:

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

class Demo {
    public static void main(String[] args) {
        List<Integer> array = new ArrayList<>();
        List<Integer> linked = new LinkedList<>();
        for (int i = 0; i < 1_000_000; i++) {
            array.add(i);
            linked.add(i);
        }
        int a = array.get(900_000);  // O(1)
        int b = linked.get(900_000); // O(n) в общем случае
    }
}

Для ArrayList индекс непосредственно связан с позицией в массиве. Для LinkedList требуется пройти по цепочке узлов от ближайшего конца.

Ситуация из практики

Сервис хранит десятки тысяч записей и строит страницу результатов, обращаясь к элементам списка по индексам. Рассматривались LinkedList, ArrayList и структура для работы только с концами последовательности.

LinkedList отклонили: индексный доступ требует обхода узлов и ухудшается с ростом списка. Структура для концов последовательности также не подходит, если приложению нужны произвольные индексы.

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

Что кандидаты часто упускают

Всегда ли вставка в LinkedList имеет сложность O(1)?

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

Нет, O(1) описывает асимптотику, а не конкретное время. Доступ к LinkedList по индексу всё равно требует обхода, но для небольших списков это может быть незаметно. Кроме того, практическая скорость зависит от локальности памяти, размера объектов и поведения процессорного кэша; обычно здесь преимущество у ArrayList.
Какое последствие имеет многократный индексный доступ к LinkedList в цикле?

Если цикл последовательно получает элементы через get(i), каждый вызов может заново проходить по узлам. Суммарная работа может стать O(n²), тогда как последовательный обход через итератор выполняется за O(n). Поэтому для последовательного чтения LinkedList следует обходить итератором, а если приложению нужен частый индексный доступ, обычно лучше выбрать ArrayList.