Как получить элемент по индексу в LinkedList

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

Понимаете ли вы, что у LinkedList нет прямого доступа по индексу и во что это превращается в реальном коде. Следом почти всегда просят сравнить с ArrayList и спрашивают, чем плох цикл for (i in 0 until list.size) list[i].

Как отвечать

Технически всё просто: list.get(index) или list[index] в Kotlin, который компилируется в тот же вызов. Интересно, что происходит внутри:

• проверка границ: при индексе вне допустимого диапазона летит IndexOutOfBoundsException;
• обход узлов: java.util.LinkedList двусвязный, внутренний метод node(index) сравнивает индекс с половиной размера и идёт от головы или от хвоста, смотря что ближе. В худшем случае это n/2 шагов, то есть O(n);
• концы дешёвые: getFirst() и getLast() работают за O(1), список хранит ссылки на оба конца;
• нет RandomAccess: ArrayList этот маркерный интерфейс реализует, LinkedList нет, и библиотечные алгоритмы вроде Collections.binarySearch на больших списках переходят на обход итератором.

Если нужно пройти по всем элементам, используйте итератор, цикл for-each или listIterator(index): он встаёт на позицию один раз, дальше каждый шаг O(1).

Для Android добавьте практический вывод. Каждый элемент это отдельный объект Node с двумя лишними ссылками, узлы разбросаны по куче, поэтому даже линейный проход медленнее, чем по массиву, а нагрузка на сборщик мусора выше. В адаптере RecyclerView, где onBindViewHolder берёт элемент по позиции, LinkedList даёт O(n) на показ каждой строки. Обычно берут ArrayList (в Kotlin его возвращает mutableListOf()), а для очереди с двух концов ArrayDeque.

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

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

Говорят, что LinkedList быстрее вставляет в середину. Сама перестановка ссылок стоит O(1), но до нужной позиции надо дойти за O(n), так что выигрыш есть при вставке в концы или через итератор, который уже стоит на месте.

Уверенно называют «ровно n шагов» и не знают, что обход идёт с ближайшего конца. Асимптотика та же, но эта деталь показывает, что вы заглядывали в исходники.