Kuidas hinnata seotud nimekirja elemendi uuendamise operatsiooni algoritmilist keerukust?

Seotud nimekirja elementi uuendamine nõuab tavaliselt esmalt selle elemendi leidmist ja seejärel selle väärtuse muutmist.

• Kui teil on viit või viide vajaliku sõlme juurde, on väärtuse uuendamine O(1) operatsioon.
• Kui peate esmalt leidma elemendi indeksi või väärtuse järgi, kestab otsing O(n), kus n on nimekirja elementide arv.

Dart (Flutter) näide:

class Node {
  int value;
  Node? next;

  Node(this.value);
}

void updateNodeValue(Node head, int index, int newValue) {
  Node? current = head;
  int i = 0;
  while (current != null && i < index) {
    current = current.next;
    i++;
  }
  if (current != null) {
    current.value = newValue; // O(1) uuendus
  }
}

Kokkuvõttes on indeksi järgi elemendi uuendamise üldine keerukus — O(n), kui otsest juurdepääsu sõlmele pole.