Est-il possible de supprimer un nœud central dans la liste chaînée unique lorsque la seule information dont nous disposons est le pointeur vers le nœud à supprimer et non le pointeur vers le nœud précédent ? Après la suppression, le nœud précédent devrait pointer vers le nœud suivant le nœud supprimé.
Réponses
Trop de publicités?
Ben Combee
Points
7193
Supposons une liste ayant la structure suivante
A -> B -> C -> D
Si vous n'aviez qu'un pointeur sur B et que vous vouliez le supprimer, vous pourriez faire quelque chose comme
tempList = B->next;
*B = *tempList;
free(tempList);La liste serait alors la suivante
A -> B -> D
mais B contiendrait l'ancien contenu de C, supprimant effectivement ce qui était dans B. Cela ne fonctionnera pas si un autre morceau de code détient un pointeur vers C. Cela ne fonctionnera pas non plus si vous essayez de supprimer le noeud D. Si vous voulez faire ce genre d'opération, vous devrez construire la liste avec un noeud de queue factice qui n'est pas vraiment utilisé afin de garantir qu'aucun noeud utile n'aura un pointeur NULL next. Cela fonctionne également mieux pour les listes où la quantité de données stockées dans un nœud est faible. Une structure comme
struct List { struct List *next; MyData *data; };serait acceptable, mais une où c'est
struct HeavyList { struct HeavyList *next; char data[8192]; };serait un peu lourd.
codaddict
Points
154968
Pas possible.
Il y a des astuces pour imiter la suppression.
Mais aucune d'entre elles ne supprimera réellement le nœud sur lequel pointe le pointeur.
La solution populaire consistant à supprimer le suivant et de copier son contenu vers le noeud réel pour être supprimé a des effets secondaires si vous avez pointeurs externes pointant sur des noeuds de la liste, auquel cas un pointeur externe pointant sur le noeud suivant deviendra dangling.
Alex B
Points
21
J'apprécie l'ingéniosité de cette solution (suppression du nœud suivant), mais elle ne répond pas à la question du problème. Si c'est la solution réelle, la question correcte devrait être "supprimer de la liste liée la VALEUR contenue dans un noeud sur lequel le pointeur est donné". Mais bien sûr, la question correcte vous donne un indice sur la solution. Le problème, tel qu'il est formulé, a pour but d'embrouiller la personne (ce qui m'est d'ailleurs arrivé, d'autant plus que l'enquêteur n'avait même pas mentionné que le nœud était au milieu).
Joe Hildebrand
Points
6666
Allan Wind
Points
1133
La suggestion initiale était de transformer :
a -> b -> c
à :
a ->, c
Si vous gardez l'information autour, par exemple, d'une carte de l'adresse du noeud à l'adresse du noeud suivant, vous pouvez fixer la chaîne la prochaine fois que vous traversez la liste. Si vous devez supprimer plusieurs éléments avant la prochaine traversée, vous devez garder la trace de l'ordre des suppressions (c'est-à-dire une liste de modifications).
La solution standard est de considérer d'autres structures de données comme une liste de saut.
