Der richtige Weg, um ein Element aus einer verknüpften Liste zu entfernen

In diesem Slashdot-Interview wird Linus Torvalds mit folgenden Worten zitiert:

Ich habe zu viele Leute gesehen, die einen einfach verknüpften Listeneintrag löschen, indem sie den Eintrag "prev" verfolgen und dann den Eintrag löschen, indem sie so etwas tun

if (prev)
  prev-> next = entry-> next;
sonst
  list_head = entry-> next;

und wenn ich solchen Code sehe, gehe ich einfach zu "Diese Person versteht keine Zeiger". Und es ist leider ziemlich häufig.

Personen, die Zeiger verstehen, verwenden einfach einen "Zeiger auf den Eintragszeiger" und initialisieren diesen mit der Adresse des Listenkopfs. Und dann, wenn sie die Liste durchlaufen, können sie den Eintrag entfernen, ohne Bedingungen zu verwenden, indem sie einfach "* pp = entry-> next" ausführen.

Als PHP-Entwickler habe ich seit Einführung in C an der Universität vor einem Jahrzehnt keine Hinweise mehr berührt . Ich bin jedoch der Meinung, dass dies eine Art Situation ist, mit der ich zumindest vertraut sein sollte. Worüber spricht Linus? Um ehrlich zu sein, wenn ich gebeten würde, eine verknüpfte Liste zu implementieren und ein Element zu entfernen, würde ich den oben genannten "falschen" Weg einschlagen. Was muss ich wissen, um zu codieren, wie Linus am besten sagt?

Ich frage hier eher als bei Stack Overflow, da ich im Produktionscode eigentlich kein Problem damit habe.

Verwenden meiner L331 MS Paint-Kenntnisse:

Die ursprüngliche Lösung besteht darin, auf Knoten über zu zeigen curr. In diesem Fall prüfen Sie, ob der nächste nachfolgende Knoten currden Löschwert hat, und setzen in diesem Fall den currKnotenzeiger zurück next. Das Problem ist, dass es keinen Knoten gibt, der auf den Kopf der Liste zeigt. Das heißt, es muss einen Sonderfall geben, um dies zu überprüfen.

Was Linus (wahrscheinlich) stattdessen vorschlägt, ist nicht, den Zeiger auf den aktuell untersuchten Knoten zu speichern, sondern den Zeiger auf den Zeiger auf den aktuellen Knoten (beschriftet pp). Die Operation ist dieselbe - wenn der ppZeiger auf einen Knoten mit dem richtigen Wert zeigt, setzen Sie den ppZeiger zurück.

Der Unterschied steht ganz am Anfang der Liste. Während es keinen Knoten gibt, der auf den Kopf der Liste zeigt, gibt es tatsächlich einen Zeiger auf den Kopf der Liste. Und es ist genauso ein Zeiger auf einen Knoten wie ein Zeiger eines anderen Knotens next. Daher ist für den Beginn der Liste keine spezielle Klausel erforderlich.

Codebeispiel

// ------------------------------------------------------------------
// Start by pointing to the head pointer.
// ------------------------------------------------------------------
//    (next_ptr)
//         |
//         v
// [head]----->[..]----->[..]----->[..]----->[to_remove]----->[....]
Node** next_ptr = &list->head;

// ------------------------------------------------------------------
// Search the list for the matching entry.
// After searching:
// ------------------------------------------------------------------
//                                  (next_ptr)
//                                       |
//                                       v
// [head]----->[..]----->[..]----->[..]----->[to_remove]----->[next]
while (*next_ptr != to_remove) // or (*next_ptr)->val != to_remove->val
{
    Node* next_node = *next_ptr
    next_ptr = &next_node->next;
}

// ------------------------------------------------------------------
// Dereference the next pointer and set it to the next node's next
// pointer.
// ------------------------------------------------------------------
//                                           (next_ptr)
//                                                |
//                                                v
// [head]----->[..]----->[..]----->[..]---------------------->[next]
*next_ptr = to_remove->next;

Wenn wir eine Logik benötigen, um den Knoten zu zerstören, können wir am Ende einfach eine Codezeile hinzufügen:

// Deallocate the node which is now stranded from the list.
free(to_remove);