Какая сложность операции доступа по индексу в LinkedList

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

Пример:

val list = LinkedList<String>().apply {
    add("A")
    add("B")
    add("C")
}
val element = list[1] // O(n) – проходит через первый элемент, чтобы добраться до второго

Оптимальнее использовать ArrayList для частого доступа по индексу (O(1)).