Utilisation de pointeurs pour supprimer un élément d'une liste à lien simple

Question

Dans un récent Interview de Slashdot Linus Torvalds a donné un exemple de la façon dont certaines personnes utilisent les pointeurs d'une manière qui indique qu'elles ne comprennent pas vraiment comment les utiliser correctement.

Malheureusement, comme je fais partie des personnes dont il parle, je n'ai pas non plus compris son exemple :

J'ai vu trop de personnes qui suppriment une entrée de liste à lien unique en gardant la trace de l'entrée "prev", puis pour supprimer l'entrée, en faisant quelque chose du genre

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

et à chaque fois que je vois du code comme ça, je me dis "Cette personne ne comprend pas les pointeurs". Et c'est malheureusement assez commun. Les personnes qui comprennent les pointeurs utilisent simplement un "pointeur vers le pointeur d'entrée", et l'initialisent avec l'adresse de la tête de liste. Puis, en parcourant la liste, ils peuvent supprimer l'entrée sans utiliser de conditionnel, en faisant simplement

*pp = entry->next

Quelqu'un peut-il expliquer un peu plus pourquoi cette approche est meilleure, et comment elle peut fonctionner sans une déclaration conditionnelle ?

Answer 1

Au début, vous faites

pp = &list_head;

et, au fur et à mesure que vous parcourez la liste, vous faites avancer ce "curseur" à l'aide des touches

pp = &(*pp)->next;

De cette façon, vous gardez toujours la trace du point d'où "vous venez" et pouvez modifier le pointeur qui y vit.

Donc, quand vous trouvez l'entrée à supprimer, vous pouvez simplement faire

*pp = entry->next

De cette façon, vous vous occupez des 3 cas. Afaq mentionnée dans une autre réponse, éliminant ainsi le NULL vérifier prev .

Answer 2

Reconnecter la liste une fois qu'un nœud doit être retiré est plus intéressant. Considérons au moins 3 cas :

1. suppression d'un nœud du début.

2. retirer un nœud du milieu.

3. retirer un nœud de l'extrémité.

Suppression du début

Lorsque l'on supprime le nœud situé au début de la liste, il n'y a pas de réassociation de nœuds à effectuer, puisque le premier nœud n'a pas de nœud précédent. Par exemple, en supprimant le nœud avec un :

link
 |
 v
---------     ---------     ---------
| a | --+---> | b | --+---> | c | 0 |
---------     ---------     ---------

Cependant, nous devons fixer le pointeur au début de la liste :

link
 |
 +-------------+
               |
               v
---------     ---------     ---------
| a | --+---> | b | --+---> | c | 0 |
---------     ---------     ---------

Retirer du milieu

Pour retirer un nœud du milieu, il faut que le nœud précédent saute par-dessus le nœud à retirer. Par exemple, en retirant le nœud avec b :

link
 |
 v
---------     ---------     ---------
| a | --+--+  | b | --+---> | c | 0 |
---------  |  ---------     ---------
           |                ^
           +----------------+

Cela signifie que nous avons besoin d'un moyen de faire référence au nœud précédant celui que nous voulons supprimer.

Suppression de la fin

Pour retirer un nœud de la fin, il faut que le nœud précédent devienne la nouvelle fin de la liste (c'est-à-dire qu'il ne pointe vers rien après lui). Par exemple, la suppression du nœud avec c :

link
 |
 v
---------     ---------     ---------
| a | --+---> | b | 0 |     | c | 0 |
---------     ---------     ---------

Notez que les deux derniers cas (milieu et fin) peuvent être combinés en disant que "le nœud précédant celui à supprimer doit pointer là où se trouve celui à supprimer."

Answer 3

Je préfère l'approche du nœud factice, un exemple de mise en page :

|Dummy|->|node1|->|node2|->|node3|->|node4|->|node5|->NULL
                     ^        ^
                     |        |
                    curr   curr->next // << toDel

et ensuite, vous traversez jusqu'au noeud à supprimer (toDel = curr>next)

tmp = curr->next;
curr->next = curr->next-next;
free(tmp);

De cette façon, il n'est pas nécessaire de vérifier s'il s'agit du premier élément, car le premier élément est toujours Dummy et n'est jamais supprimé.