Какая временная сложность операции чтения (доступа по индексу) в связном списке?

Операция чтения элемента по индексу в односвязном списке имеет временную сложность O(n) в худшем и среднем случае, где n — количество элементов в списке.

Почему O(n)? В связном списке элементы не хранятся в непрерывной памяти. Каждый узел содержит указатель на следующий элемент. Чтобы получить доступ к элементу по индексу k, необходимо начать с головы списка и последовательно пройти k узлов по цепочке ссылок next.

Реализация на Dart:

class Node<T> {
  T value;
  Node<T>? next;
  Node(this.value, [this.next]);
}

T? readAt<T>(Node<T>? head, int index) {
  Node<T>? current = head;
  int currentIndex = 0;

  // Линейный обход: O(n)
  while (current != null && currentIndex < index) {
    current = current.next;
    currentIndex++;
  }

  if (current == null) {
    throw RangeError('Index $index out of bounds');
  }
  return current.value;
}

void main() {
  // Создаём список: 10 -> 20 -> 30 -> 40
  var head = Node(10, Node(20, Node(30, Node(40))));

  print(readAt(head, 0)); // 10, проходит 0 узлов
  print(readAt(head, 2)); // 30, проходит 2 узла (20, 30)
  print(readAt(head, 3)); // 40, проходит 3 узла (20, 30, 40)
}

Сравнение с массивом (List) и вывод для Flutter:

• Массив (List): доступ по индексу за O(1).
• Связный список: доступ по индексу за O(n).

В контексте Flutter связные списки не подходят для хранения данных, к которым часто обращаются по индексу (например, элементы в ListView). Их потенциальное применение — очередь задач или история навигации, где основные операции — добавление/удаление с концов.