La suppression d'un noeud aléatoire à partir des deux listes des liaisons simples et des liaisons doubles liées

Question

Je suis un moment difficile à venir avec la logique pour enlever un nœud à la fois une liste doublement et chaînée. Je l'ai regardé en ligne d'aide, mais je ne pouvais pas trouver un exemple simple de celui-ci. Voici ce que j'ai:

---

suppression Doublement liés. dCurrent est le nœud que nous voulons supprimer.

if (dCurrent == dHead){
   dHead = dCurrent->next;
   dHead->prev = NULL;
}
else if(dCurrent == dTail){
   dTail = dCurrent->prev;
   dTail->next = NULL;
}
else{
   dCurrent->next->prev = dCurrent->prev;
   dCurrent->prev->next = dCurrent->next;   
}

---

Voici ce que j'ai pour la liste chaînée. Encore une fois, sCurrent est le nœud à supprimer. et sPrev = sCurrent->prev.

if(sPrev == NULL){
   sHead = sCurrent->next;
}
else{
   sPrev->next = sCurrent->next;
}

---

Le problème est que, après supprimer une collection de nœuds aléatoires à partir des deux listes, les correctement de la tête affiche la liste doublement liés à la queue, mais pas la queue à la tête. La liste chaînée n'affiche pas correctement, que ce soit.

Answer 1

Votre logique liste doublement liée semble bien à moi. Mon seul souci est que si dCurrent est le seul élément de la liste, alors ceci:

if (dCurrent == dHead){
    dHead = dCurrent->next;
    dHead->prev = NULL;
}

sera très probablement essayer de faire référence à un pointeur NULL. (Cela dépend de la façon dont vous concevez votre liste. Mais dans un design typique, si dCurrent est le seul noeud, dCurrent->next est NULL.)

Votre logique liste simplement chaînée ressemble aussi bien à moi, dans l'abstrait, compte tenu de l'hypothèse que « sPrev = sCurrent-> prev »; mais je ne comprends pas comment cette hypothèse peut être correcte. Si c'est une liste simplement chaînée, alors sCurrent ne pas Vous un pointeur prev.

Answer 2

Les seules questions que je peux voir que votre code ne fonctionnera pas correctement pour les cas où la tête ou la queue sont mis à jour à NULL.

En gros, si vous supprimez le seul noeud, dHead pointera vers nulle, de sorte que vous devez mettre « gardiens » des déclarations autour suivantes comme

dHead->prev = NULL;

comme si

if (dHead != NULL) {
  dHead->prev = NULL;
}

Une façon de « contourner » ayant tant de conditionals est d'attribuer un élément NIL (pas un type).

NIL est le "nœud" qui remplace NULL. Il représente « au large de la partie de données de la liste » pour son prochain est toujours NIL (une référence circulaire) et il est toujours NIL précédente est (une référence circulaire). Dans de tels cas, assurez-vous que NIL est jamais accessible à l'extérieur de la liste, et que BANDEAUX> prev == NIL et de queue> suivant == NIL. De cette façon, vous pouvez éviter les nombreuses déclarations de type if (tail != null) { ... }.

Dans le cadre d'une telle construction, une liste vide est celui où head == NIL && tail == NIL. Cela réduit considérablement le nombre de déclarations de if (something == null), mais vous avez encore une instruction if à considérer, lorsque la tête est NIL (après la suppression de quelque chose), vous devez la queue ensemble à NIL pour souci de cohérence.