Entfernen eines zufälligen Knoten

Question

Es fällt mir schwer, die Logik zu entwickeln, um einen Knoten sowohl aus einer doppelten als auch von einer einzig verknüpften Liste zu entfernen. Ich habe online von Hilfe gesucht, aber ich konnte kein einfaches Beispiel dafür finden. Hier ist was ich habe:

---

Doppelt verknüpfte Löschung. dCurrent ist der Knoten, den wir löschen wollen.

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;   
}

---

Hier ist, was ich für die einzig verknüpfte Liste habe. Wieder, sCurrent Ist der Knoten zu löschen. und sPrev = sCurrent->prev.

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

---

Das Problem ist, dass nach dem Löschen einer Sammlung zufälliger Knoten aus beiden Listen die doppelt verknüpfte Liste korrekt vom Kopf zu Schwanz, jedoch nicht von Schwanz zu Kopf angezeigt wird. Die einzig verknüpfte Liste wird auch nicht richtig angezeigt.

Answer 1

Ihre doppelt verknüpfte List-Logik sieht für mich gut aus. Meine einzige Sorge ist, dass wenn dCurrent ist das einzige Element in der Liste, dann Folgendes:

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

Wird höchstwahrscheinlich versuchen, auf einen Null-Zeiger zu verweisen. (Es hängt davon ab, wie Sie Ihre Liste entwerfen. Aber in einem typischen Design, wenn dCurrent ist dann der einzige Knoten dCurrent->next ist NULL.)

In der Zusammenfassung sieht auch für mich auch für mich gut aus, angesichts der Annahme, dass "sprev = scurrent-> precing" in Ordnung ist. Aber ich verstehe nicht, wie diese Annahme korrekt sein kann. Wenn es sich um eine einzeln verknüpfte Liste handelt, dann sCurrent nicht haben a prev Zeiger.

Answer 2

Die einzigen Probleme, die ich sehen kann, ist, dass Ihr Code nicht ordnungsgemäß für Szenarien funktioniert, in denen Kopf oder Schwanz auf Null aktualisiert werden.

Wenn Sie den einzigen Knoten löschen, verweist Dhead im Grund

dHead->prev = NULL;

Wie so

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

Eine Möglichkeit, so viele Bedingungen zu "umgehen", besteht darin, ein NIL -Element (kein Typ) zuzuweisen.

Nil ist der "Knoten", der Null ersetzt. Es stellt "aus dem Datenabschnitt der Liste" dar, sodass es immer Null ist (eine kreisförmige Referenz) und es ist vorher immer nil (eine zirkuläre Referenz). In solchen Fällen stellen Sie sicher, dass NIL außerhalb der Liste niemals zugänglich ist und dass Head-> Prev == NIL und Tail-> Weiter == nil. Auf diese Weise können Sie die vielen vermeiden if (tail != null) { ... } Tippen Sie an.

Unter einem solchen Konstrukt ist eine leere Liste eine, bei der head == NIL && tail == NIL. Dies reduziert die Anzahl der Anzahl von dramatisch if (something == null) Aussagen, aber Sie haben noch eine Anweisung zu berücksichtigen, wenn der Kopf NIL ist (nach dem Löschen von etwas), müssen Sie den Schwanz für die Konsistenz willen an Null einstellen.