Comment évaluer la complexité algorithmique de l'opération de mise à jour d'un élément dans une liste chaînée?

La mise à jour d’un élément dans une liste chaînée nécessite généralement de d’abord trouver cet élément, puis de modifier sa valeur.

• Si vous avez un pointeur ou une référence au nœud nécessaire, la mise à jour de la valeur est une opération O(1).
• Si vous devez d’abord rechercher l’élément par index ou valeur, la recherche prend O(n), où n est le nombre d’éléments dans la liste.

Exemple en 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; // mise à jour O(1)
  }
}

En résumé, la complexité totale de la mise à jour d’un élément par index est O(n), en l’absence d’accès direct au nœud.