Suppression d'une liste chaînée

Question

Étant donné seulement un pointeur vers le noeud à supprimer, comment supprimer le noeud dans la liste chaînée ...?

Answer 1

La question est trop ambiguë, et est probablement de ce type pour une raison (par exemple, engendrer une conversation au lieu de tester votre connaissance réelle de la structure de données). Ils s'attendent probablement à ce que vous demandiez "Est-ce une liste doublement liée ou une liste unidirectionnelle?" Si elle est une liste doublement liée, c'est une question simple:

curr->prev->next = curr->next; 
curr->next->prev = curr->prev; 
delete curr; 

Si elle est une liste chaînée, vous devez avoir le nœud de tête afin que vous puissiez trouver le nœud précédent dans la liste. Donc, ils s'attendent probablement à ce que vous demandiez si vous avez un pointeur sur le nœud principal. alors le pseudo-code est:

loop from head to end until test->next == curr 
test->next = curr->next; 
delete curr; 

Alternativement, si vous pouvez modifier la liste (sans le nœud principal):

temp = curr->next; 
curr->data = temp->data; 
curr->next = temp->next; 
delete temp; 

Answer 2

Je pense que c'est presque impossible dans les listes à lien unique si vous n'avez aucun pointeur vers la liste. Vous devriez toujours avoir un pointeur de tête de liste liée.

Answer 3

Dans une implémentation de liste chaînée standard, a pour modifier le noeud qui pointe vers le noeud en cours de suppression. Pour le modifier, vous devez le trouver en premier. Si vous avez un pointeur vers la tête de liste, ou un élément avant celui qui est supprimé, vous pouvez le trouver en parcourant la liste. Sinon, il n'y a pas de solution générale à ce problème. Vous pouvez sortir de la situation en modifiant la définition d'une liste liée pour marquer les nœuds supprimés (par exemple, avec un attribut booléen deleted), et à son tour modifier la traversée de la liste pour ignorer ces nœuds.

Answer 4

Eh bien, c'est juste un truc.

En supposant curr est l'adresse indiquée, suivant serait le code pseudo:

to_delete = curr->next 
curr->data = to_delete->data 
curr->next = to_delete->next 
delete to_delete 

essentiellement ces données seulement des copies et pointeur suivant du nœud suivant dans la liste au noeud courant et supprime le nœud suivant.

Answer 5

You have a pointer to that node (say, node N). Meaning, you have access on that node. 
If that node has pointer to it's front node and it's back node, then simply point the back node to the front node. And the front node to the back of your node N. 

To illustrate: 
step 1: 
---> [ node ] ---> [ node ] ---> [ node ] ---> 
<--- [ M ] <--- [ N ] <--- [ O ] <--- etc... 

step 2: 
---> [ node ] -----------------> [ node ] ---> 
<--- [ M ] <--- [node N] <--- [ O ] <--- etc... 

step 3: 
---> [ node ] -----------------> [ node ] ---> 
<--- [ M ] <----------------- [ O ] <--- etc... 

            [ node ] ---> (still points to node O) 
     (still points to node M) <--- [ N ] 

step 4: 
just point Node N to NULL 
            [ node ] ---> NULL 
          NULL <--- [ N ] 

result: 
---> [ node ] -----------------> [ node ] ---> 
<--- [ M ] <----------------- [ O ] <--- etc... 

Answer 6

J'ai une solution si ce n'est pas la queue.

S'il s'agit d'une liste à liaison unique, il vous suffit de "permuter" avec le nœud à côté du vôtre et de supprimer celui-ci à la place.

En supposant que je

struct Node 
{ 
    T value; 
    Node * next; 
}; 

solution serait quelque chose comme:

void freeNode(Node * node) 
{ 
    Node * next = node->next; 
    if(next) 
    { 
     node->value = next->value; 
     node->next = next->next; 
     free(next); 
    } 
    // else I'm stuck! 
} 

Le genre de mélange ci-dessus pseudo de C et C++. Si le nœud que nous avons est la queue, et en supposant que la queue est indiquée par node-> next == NULL, je ne peux pas faire le nœud précédent dans la queue, donc je ne peux pas résoudre.