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

В связном списке LinkedList получение элемента по индексу происходит путём последовательного обхода узлов с начала (или конца, если индекс ближе к концу) списка до нужной позиции. Это значит, что время доступа к элементу по индексу — линейное, то есть O(n), где n — индекс элемента.

В отличие от массивов, где доступ по индексу — константный (O(1)), LinkedList не хранит элементы в непрерывной памяти, поэтому прямого доступа по индексу нет.

Пример на Java:

LinkedList<String> list = new LinkedList<>();
list.add("a");
list.add("b");
list.add("c");

// Для получения элемента с индексом 2 происходит обход первых двух элементов
String element = list.get(2); // "c"

При этом метод get() будет проходить по элементам последовательно до нужного индекса.