Kako proceniti algoritamsku složenost operacije ažuriranja elementa u povezanoj listi?

Ažuriranje elementa u povezanoj listi obično zahteva prvo pronalaženje tog elementa, a zatim promenu njegove vrednosti.

• Ako imate pokazivač ili referencu na potrebni čvor, ažuriranje vrednosti je operacija O(1).
• Ako prvo morate pronaći element po indeksu ili vrednosti, pretraga traje O(n), gde je n broj elemenata u listi.

Primer u 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) ažuriranje
  }
}

Ukupna složenost ažuriranja elementa po indeksu je O(n), ako nema direktan pristup čvoru.