Какая временная сложность delete в связном списке?

Временная сложность delete в связном списке

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

Основные сценарии

1. Удаление элемента ПО ЗНАЧЕНИЮ — O(n)

Если нужно найти и удалить элемент по значению, необходимо:

1. Пройти по списку до нужного элемента — O(n)
2. Удалить элемент (переставить указатель) — O(1)

Итоговая сложность: O(n)

class LinkedListNode<T> {
  T value;
  LinkedListNode<T>? next;
  
  LinkedListNode(this.value, {this.next});
}

class LinkedList<T> {
  LinkedListNode<T>? head;
  
  // Удаление по значению — O(n)
  void deleteByValue(T value) {
    // Случай: голова списка совпадает
    while (head != null && head!.value == value) {
      head = head!.next; // O(1)
    }
    
    // Поиск и удаление во внутренних узлах
    LinkedListNode<T>? current = head;
    while (current?.next != null) {
      if (current!.next!.value == value) {
        current.next = current.next?.next; // O(1)
      } else {
        current = current.next;
      }
    }
  }
}

2. Удаление элемента ПО ИНДЕКСУ — O(n)

При удалении по позиции нужно:

1. Найти элемент по индексу — O(n) (в худшем случае n узлов)
2. Удалить элемент — O(1)

Итоговая сложность: O(n)

// Удаление по индексу — O(n)
void deleteByIndex(int index) {
  if (index == 0) {
    head = head?.next; // O(1)
    return;
  }
  
  LinkedListNode<T>? current = head;
  
  // Поиск узла перед удаляемым — O(n)
  for (int i = 0; i < index - 1 && current != null; i++) {
    current = current.next;
  }
  
  // Удаление — O(1)
  if (current?.next != null) {
    current!.next = current.next?.next;
  }
}

3. Удаление узла со ССЫЛКОЙ на него — O(1)

Это специальный случай: если у вас уже есть ссылка на узел для удаления, операция занимает O(1).

// Удаление со ссылкой на узел — O(1)
void deleteNode(LinkedListNode<T> node) {
  // Копируем данные следующего узла в текущий
  if (node.next != null) {
    node.value = node.next!.value;
    node.next = node.next!.next; // O(1) — просто переставляем указатель
  }
}

Сравнение со связным списком Dart

В стандартной библиотеке Dart есть встроенный LinkedList<T>:

import 'dart:collection';

class LinkedListExample {
  void example() {
    final list = LinkedList<int>();
    
    // Добавление
    final entry1 = _LinkedListEntry(10);
    final entry2 = _LinkedListEntry(20);
    
    list.add(entry1); // O(1)
    list.add(entry2); // O(1)
    
    // Удаление со ссылкой на элемент — O(1)
    entry1.unlink(); // O(1)
    
    print(list.length); // 1
  }
}

class _LinkedListEntry extends LinkedListEntry<int> {
  final int value;
  _LinkedListEntry(this.value);
}

Сравнение с динамическим массивом

Визуальный пример

Удаление элемента B из списка A -> B -> C -> D:

1. Поиск: A -> B (нашли) — требует обхода
2. Переставление указателя: A -> C (опускаем B) — O(1)

Время = поиск (O(n)) + удаление (O(1)) = O(n)

Оптимизация для частого удаления

Если часто нужно удалять элементы:

1. Двусвязный список — позволяет быстрее переходить к соседним узлам, но сложность остаётся O(n) при поиске

class DoublyLinkedNode<T> {
  T value;
  DoublyLinkedNode<T>? next;
  DoublyLinkedNode<T>? prev;
  
  DoublyLinkedNode(this.value, {this.next, this.prev});
}

1. Hash Map + связный список — для быстрого поиска узла

class OptimizedLinkedList<T> {
  final Map<T, LinkedListNode<T>> nodeMap = {};
  LinkedListNode<T>? head;
  
  // Удаление — O(1) благодаря Hash Map
  void delete(T value) {
    final node = nodeMap[value];
    if (node != null) {
      // переставляем указатели — O(1)
      if (node.next != null) {
        node.next!.prev = node.prev;
      }
      nodeMap.remove(value); // O(1)
    }
  }
}

Практическое применение в Flutter

// Удаление из UI списка — O(n)
void removeItem(List<String> items, String itemToRemove) {
  items.removeWhere((item) => item == itemToRemove); // O(n)
}

// Оптимально для связного списка
void removeFromLinkedList(LinkedList<String> list, String value) {
  for (var entry in list) {
    if (entry == value) {
      entry.unlink(); // O(1)
      return;
    }
  }
}

Итоговая таблица сложности для связного списка

Вывод

• Стандартный случай удаления: O(n) — нужен поиск элемента
• С прямой ссылкой на узел: O(1) — просто меняем указатель
• В динамическом массиве: O(n) из-за необходимости сдвига элементов

Связные списки эффективны для частого удаления в начало, но неэффективны при работе с индексами или значениями.