La bonne façon de supprimer un élément d'une liste chaînée

Dans cette interview à Slashdot, Linus Torvalds aurait déclaré:

J'ai vu trop de gens qui suppriment une entrée de liste à liaison unique en gardant une trace de l'entrée "prev", puis en supprimant l'entrée, en faisant quelque chose comme

if (prev)
  prev-> next = entry-> next;
else
  list_head = entry-> next;

et chaque fois que je vois du code comme ça, je dis simplement "Cette personne ne comprend pas les pointeurs". Et c'est malheureusement assez courant.

Les personnes qui comprennent les pointeurs utilisent simplement un "pointeur vers le pointeur d'entrée" et l'initialisent avec l'adresse de list_head. Et puis, au fur et à mesure qu'ils parcourent la liste, ils peuvent supprimer l'entrée sans utiliser de conditions, en faisant simplement un "* pp = entry-> next".

En tant que développeur PHP, je n'ai pas touché de pointeurs depuis l' introduction au C à l'université il y a dix ans. Cependant, je pense que c'est un type de situation que je devrais au moins connaître. De quoi parle Linus? Pour être honnête, si on me demandait de mettre en œuvre une liste chaînée et de supprimer un élément, la «mauvaise» manière ci-dessus est la façon dont je procéderais. Que dois-je savoir pour coder comme Linus le dit le mieux?

Je demande ici plutôt que sur Stack Overflow car je n'ai pas vraiment de problème avec cela dans le code de production.

Utilisation de mes compétences L331 MS Paint:

La solution originale consiste à pointer vers Nodes via curr. Dans ce cas, vous vérifiez si le nœud suivant currpossède la valeur de suppression et, si tel est le cas, réinitialisez le pointeur de currnœud next. Le problème est qu'il n'y a aucun nœud qui pointe vers la tête de la liste. Cela signifie qu'il doit y avoir un cas spécial pour le vérifier.

Ce que Linus propose (probablement) à la place n'est pas d'enregistrer le pointeur sur le nœud actuellement examiné, mais plutôt le pointeur sur le pointeur sur le nœud actuel (étiqueté pp). L'opération est la même - si le pppointeur pointe vers un nœud avec la bonne valeur, vous réinitialisez le pppointeur.

La différence vient au tout début de la liste. Bien qu'il n'y ait aucun nœud qui pointe vers le début de la liste, il y a, en fait, un pointeur vers le début de la liste. Et c'est tout de même un pointeur vers un nœud, tout comme un autre nextpointeur de nœuds . Il n'est donc pas nécessaire de prévoir une clause spéciale pour le début de la liste.

Exemple de code

// ------------------------------------------------------------------
// Start by pointing to the head pointer.
// ------------------------------------------------------------------
//    (next_ptr)
//         |
//         v
// [head]----->[..]----->[..]----->[..]----->[to_remove]----->[....]
Node** next_ptr = &list->head;

// ------------------------------------------------------------------
// Search the list for the matching entry.
// After searching:
// ------------------------------------------------------------------
//                                  (next_ptr)
//                                       |
//                                       v
// [head]----->[..]----->[..]----->[..]----->[to_remove]----->[next]
while (*next_ptr != to_remove) // or (*next_ptr)->val != to_remove->val
{
    Node* next_node = *next_ptr
    next_ptr = &next_node->next;
}

// ------------------------------------------------------------------
// Dereference the next pointer and set it to the next node's next
// pointer.
// ------------------------------------------------------------------
//                                           (next_ptr)
//                                                |
//                                                v
// [head]----->[..]----->[..]----->[..]---------------------->[next]
*next_ptr = to_remove->next;

Si nous avons besoin de logique pour détruire le nœud, nous pouvons simplement ajouter une ligne de code à la fin:

// Deallocate the node which is now stranded from the list.
free(to_remove);