Hogyan értékeljük a láncolt lista elemének frissítési műveletének algoritmikus összetettségét?

Egy elem frissítése egy összekapcsolt listában általában először megköveteli, hogy megtalálja ezt az elemet, majd megváltoztassa az értékét.

• Ha van mutató vagy hivatkozás a szükséges csomópontra, az érték frissítése O(1) művelet.
• Ha először meg kell találni az elemet index vagy érték szerint, a keresés O(n), ahol n a lista elemeinek száma.

Példa 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) frissítés
  }
}

Összességében, az index szerint történő elemfrissítés összetettsége — O(n), ha nincs közvetlen hozzáférés a csomóponthoz.