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

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

Понимаете ли вы, что дело не в приёмах обхода, а в выборе структуры данных. Правильный ответ обычно звучит как «не использовать LinkedList для доступа по индексу».

Как отвечать

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

Что делать:

• сменить структуру: если нужен доступ по индексу, берётся ArrayList с постоянным временем. Это правильный ответ в подавляющем большинстве случаев;
• обходить итератором, а не индексом: цикл for (int i = 0; i < list.size(); i++) с вызовом get(i) превращается в квадратичный. Обход через for-each или явный итератор линеен;
• вставка и удаление по итератору: ListIterator вставляет и удаляет за постоянное время, потому что позиция уже найдена. Именно ради этого список и берут;
• очередь с двух концов: если нужны только добавления и снятия с краёв, подойдёт ArrayDeque, и он быстрее LinkedList за счёт локальности данных.

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

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

Пишут цикл с get(i) по связному списку и получают квадратичную сложность на ровном месте.

Выбирают LinkedList ради быстрой вставки в середину, забывая, что позицию сначала нужно найти за линейное время.

Считают, что теоретическая сложность решает всё, и не учитывают работу с памятью.