Supprimer un nœud dans la liste de liens unique

Comment supprimer un nœud dans une liste de liens unique avec un seul pointeur pointant sur le nœud à supprimer?

[Les pointeurs de début et de fin ne sont pas connus, les informations disponibles sont le pointeur sur le nœud qui doit être supprimé]

Vous pouvez supprimer un nœud sans récupérer le nœud précédent, en le faisant imiter et en le supprimant à la place:

void delete(Node *n) { if (!is_sentinel(n->next)) { n->content = n->next->content; Node *next = n->next; n->next = n->next->next; free(next); } else { n->content = NULL; free(n->next); n->next = NULL; } } 

Comme vous pouvez le constater, vous devrez vous occuper spécialement du dernier élément. J’utilise un nœud spécial en tant que nœud sentinelle pour marquer la fin qui a un content et qui doit next être NULL .

UPDATE: les lignes Node *next = n->next; n->next = n->next->next Node *next = n->next; n->next = n->next->next mélange fondamentalement le contenu du nœud et libère le nœud: Image dans laquelle vous obtenez une référence au nœud B à supprimer:

  A / To be deleted next ---> B next ---> C next ---> *sentinel* 

La première étape est n->content = n->next->content : copiez le contenu du noeud suivant sur le noeud à “supprimer”:

  A / To be deleted next ---> C next ---> C next ---> *sentinel* 

Ensuite, modifiez les points next :

  A / To be deleted next ---> C /---------------- next ---| C | next ---> *sentinel* 

Le réellement libre l’élément suivant, pour arriver au cas final:

  A / To be deleted next ---> C next ---> *sentinel* 

Pas possible.

Il y a des astuces pour imiter la suppression.

Mais aucun de ceux-ci ne supprimera réellement le nœud pointé par le pointeur.

La solution habituelle consistant à supprimer le noeud suivant et à copier son contenu sur le noeud à supprimer a des effets secondaires si vous avez des pointeurs externes pointant vers des noeuds de la liste. Dans ce cas, un pointeur externe pointant vers le noeud suivant deviendra suspendu.

Vous pouvez trouver quelques discussions sur SO ici .

La seule option judicieuse et sûre dans le cadre de telles ressortingctions consiste à marquer le nœud supprimé sans réellement le dissocier, en le reportant à une date ultérieure.