Как избежать высокой сложности доступа по индексу в LinkedList?

Что проверяют

Понимаете ли вы, как устроен LinkedList внутри и почему get(i) у него дорогой, а не просто помните табличку сложностей. Следом обычно спрашивают, когда LinkedList вообще оправдан и почему в реальном коде его почти не встретишь.

Как отвечать

Начните с устройства: java.util.LinkedList это двусвязный список, каждый узел хранит элемент и ссылки prev и next. Массива под ним нет, поэтому get(index) идёт по ссылкам. Реализация немного хитрит: если индекс в первой половине, обход начинается с first, иначе с last, но это всё равно O(n), просто в худшем случае n/2 шагов.

Дальше способы не платить эту цену:

• не обращаться по индексу вовсе: проходить список через Iterator или for-each, тогда каждый шаг O(1), а весь проход O(n);
• ListIterator для вставок и удалений: add() и remove() через итератор выполняются за O(1) в текущей позиции, и именно тут список честно выигрывает;
• сменить структуру: для доступа по индексу ArrayList (O(1), данные лежат подряд и хорошо ложатся в кэш процессора), для очереди и стека ArrayDeque;
• скопировать один раз: если индексный доступ нужен в отдельной фазе, new ArrayList<>(linkedList) стоит O(n) один раз вместо O(n) на каждое обращение.

Полезно сказать и про маркерный интерфейс RandomAccess: ArrayList его реализует, LinkedList нет. Библиотечный код вроде Collections.binarySearch проверяет этот маркер и для последовательного списка переключается на обход итератором.

Где спотыкаются

Пишут цикл for (int i = 0; i < list.size(); i++) с list.get(i) внутри и не замечают, что на LinkedList это O(n²). На сотне тысяч элементов разница с итератором видна без профилировщика.

Считают, что вставка в середину LinkedList всегда O(1). Сама перелинковка дешёвая, но до нужной позиции надо дойти, и add(index, e) в итоге тоже O(n).

Предлагают «кэшировать элементы по индексу» в отдельной структуре. Это и есть самодельный ArrayList, который ещё и расходится с оригиналом при каждой вставке.