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

Временная сложность удаления элемента из односвязного списка зависит от условий:

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

Реализация на Dart и объяснение:

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

class LinkedList<T> {
  Node<T>? head;

  // Удаление по значению: O(n) в худшем случае
  void remove(T value) {
    if (head == null) return;

    // Удаление головы: O(1)
    if (head!.value == value) {
      head = head!.next;
      return;
    }

    // Поиск узла для удаления: O(n)
    Node<T>? current = head;
    while (current!.next != null) {
      if (current.next!.value == value) {
        current.next = current.next!.next; // Связываем предыдущий с следующим
        return;
      }
      current = current.next;
    }
  }
}

Применение в Flutter: Связные списки редко используются напрямую в UI-слое Flutter из-за O(n) доступа по индексу, но могут быть полезны для реализации специфических структур данных (например, кэшей типа LRU, где требуется быстрое удаление из начала/конца). Пакет collection предоставляет готовые реализации.