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

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

Временная сложность операции обновления (изменение значения) в связном списке зависит от того, известна ли позиция элемента. В Dart связные списки реализованы классом LinkedList.

Временная сложность по типам операций

1. Update, если знаем узел (Node) — O(1)

Если у нас есть прямая ссылка на узел, обновление происходит мгновенно:

// ✅ O(1) — прямой доступ к узлу
node.value = newValue;

2. Update по индексу — O(n)

Если нужно найти элемент по индексу, нужно пройти от начала:

class LinkedListExample {
  LinkedList<int> list = LinkedList<int>();
  
  // O(n) — нужно пройти от начала до позиции
  void updateAtIndex(int index, int newValue) {
    var current = list.first;
    for (int i = 0; i < index; i++) {
      current = current.next as LinkedListEntry<int>;
    }
    current.value = newValue; // O(1) сама операция, но поиск O(n)
  }
}

3. Update по значению — O(n)

Если ищем элемент по значению:

// O(n) — нужно пройти весь список в худшем случае
void updateByValue(int oldValue, int newValue) {
  for (var node in list) {
    if (node.value == oldValue) {
      node.value = newValue;
      break;
    }
  }
}

Полная таблица сложности LinkedList

Операция           | Сложность | Описание
------------------|-----------|----------------------------
Access (к узлу)   | O(1)      | Если есть ссылка на узел
Access (по индексу)| O(n)      | Нужно найти с начала
insert (в начало)  | O(1)      | Вставка перед first
insert (в конец)   | O(1)      | Вставка после last
insert (в позицию) | O(n)      | Нужно найти позицию
delete (узел)      | O(1)      | Если есть ссылка
delete (по индексу)| O(n)      | Нужно найти узел
update (узел)      | O(1)      | Если есть ссылка
update (по индексу)| O(n)      | Нужно найти узел
search             | O(n)      | Линейный поиск

Практические примеры в Dart

Пример 1: O(1) update с известным узлом

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

class LinkedListExample {
  late LinkedListEntry<int> _nodeToUpdate;
  LinkedList<int> list = LinkedList<int>();
  
  void initWithNode() {
    _nodeToUpdate = LinkedListEntry(42);
    list.add(_nodeToUpdate);
  }
  
  // O(1) — прямой доступ к сохранённому узлу
  void quickUpdate(int newValue) {
    _nodeToUpdate.value = newValue;
  }
}

Пример 2: O(n) update по индексу

class LinkedList<T> {
  LinkedListEntry<T>? first;
  
  // O(n) — нужно пройти список
  void updateAtIndex(int index, T newValue) {
    var current = first;
    for (int i = 0; i < index && current != null; i++) {
      current = current.next as LinkedListEntry<T>?;
    }
    if (current != null) {
      current.value = newValue;
    }
  }
}

Пример 3: Оптимизация — список с Map кешем

class OptimizedLinkedList<T> {
  LinkedList<T> _list = LinkedList<T>();
  Map<String, LinkedListEntry<T>> _indexMap = {}; // Кеш для быстрого доступа
  
  // O(1) благодаря кешу
  void updateFast(String key, T newValue) {
    var node = _indexMap[key];
    if (node != null) {
      node.value = newValue;
    }
  }
  
  // O(n) для первого добавления
  void addWithKey(String key, T value) {
    var node = LinkedListEntry(value);
    _list.add(node);
    _indexMap[key] = node;
  }
}

Почему это медленнее чем Array

// Array (List) — O(1) update
var array = [1, 2, 3, 4, 5];
array[2] = 99; // O(1) — прямой доступ по индексу

// LinkedList — O(n) update
var linkedList = LinkedList<int>();
// ... добавили элементы ...
// Нужно 3 шага, чтобы дойти до 3-го элемента: O(n)
var current = linkedList.first;
current = current.next;
current = current.next;
current!.value = 99; // Наконец O(1) обновление

Сравнение структур данных

// ✅ List — быстро для update по индексу
var list = [1, 2, 3];
list[1] = 99; // O(1)

// ✅ LinkedList — быстро если есть ссылка на узел
LinkedListEntry<int> node = ...;
node.value = 99; // O(1)

// ✅ Map — быстро для update по ключу
var map = {'key': 1};
map['key'] = 99; // O(1)

// ❌ LinkedList медленно для update по индексу
var linkedList = LinkedList<int>();
// Нужно пройти весь список: O(n)

Когда использовать LinkedList

Частые операции в начале/конце:

// ✅ LinkedList отличен для этого
var queue = LinkedList<String>();
queue.add(LinkedListEntry('first'));   // O(1)
queue.addFirst(LinkedListEntry('add')); // O(1)
queue.remove(queue.first);              // O(1)

Частые операции в середине:

// ❌ LinkedList медленный
var list = LinkedList<String>();
for (int i = 0; i < 100; i++) {
  list.add(LinkedListEntry('item$i'));
}
// Update элемента в середине — O(n)
var node = ...; // Нужно найти узел
node.value = 'updated'; // O(n) для поиска

// ✅ List быстрее
var list = <String>[];
for (int i = 0; i < 100; i++) {
  list.add('item$i');
}
list[50] = 'updated'; // O(1)

Итоговый вывод

Update в связном списке:

• O(1) если известна ссылка на узел
• O(n) если нужно найти элемент по индексу или значению

Рекомендация: Используй LinkedList только если часто добавляешь/удаляешь в начале/конце. Для остального лучше обычный List.