Ako hodnotiť algoritmickú zložitosť operácie aktualizácie prvku v spojenom zozname?

Aktualizácia prvku v prepojenej zozname zvyčajne vyžaduje najskôr nájsť tento prvok a potom zmeniť jeho hodnotu.

• Ak máte ukazovateľ alebo odkaz na potrebný uzol, aktualizácia hodnoty je operácia O(1).
• Ak je potrebné najskôr nájsť prvok podľa indexu alebo hodnoty, vyhľadávanie trvá O(n), kde n je počet prvkov v zozname.

Príklad v Dart (Flutter):

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) aktualizácia
  }
}

Celková zložitosť aktualizácie prvku podľa indexu je O(n), ak nie je priame prístup k uzlu.