Come valutare la complessità algoritmica dell'operazione di aggiornamento di un elemento in una lista collegata?

L'aggiornamento di un elemento in una lista collegata di solito richiede prima di trovare quell'elemento e poi di modificarne il valore.

• Se hai un puntatore o un riferimento al nodo necessario, l'aggiornamento del valore è un'operazione O(1).
• Se devi prima trovare l'elemento per indice o valore, la ricerca richiede O(n), dove n è il numero di elementi nella lista.

Esempio in 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; // aggiornamento O(1)
  }
}

In totale, la complessità complessiva dell'aggiornamento di un elemento per indice è O(n), se non si ha accesso diretto al nodo.