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

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

Почему O(n)? Связный список не поддерживает произвольный доступ. Чтобы обновить элемент по индексу i, необходимо последовательно пройти от головного узла через i связей, что требует линейного времени.

Пример реализации и обновления на Dart:

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

/// Обновляет значение узла по индексу (счёт с 0).
/// Сложность: O(n), где n - индекс целевого узла.
void updateAt<T>(ListNode<T>? head, int index, T newValue) {
  ListNode<T>? current = head;
  int currentIndex = 0;

  while (current != null && currentIndex < index) {
    current = current.next;
    currentIndex++;
  }

  if (current != null) {
    // Само обновление значения - O(1)
    current.value = newValue;
  } else {
    throw RangeError('Index $index out of bounds');
  }
}

void main() {
  final list = ListNode(1, ListNode(2, ListNode(3)));
  updateAt(list, 1, 99); // Меняем второй элемент (индекс 1) с 2 на 99.
  // Требовался проход через 1 узел.
}

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