linked list good taste
1.0.0
In einem 2016er TED -Interview (14:10) spricht Linus Torvalds über das, was er für einen guten Geschmack in der Codierung betrachtet. Als Beispiel präsentiert er zwei Implementierungen der Elemententfernung in einzigverlinkten Listen (nachstehend wiedergegeben). Um das erste Element aus einer Liste zu entfernen, erfordert eine der Implementierungen einen Sonderfall, der andere nicht. Linus bevorzugt offensichtlich letztere.
Sein Kommentar ist:
[...] Ich möchte nicht, dass du verstehst, warum es nicht die IF -Aussage hat. Aber ich möchte, dass Sie verstehen, dass Sie manchmal ein Problem auf andere Weise sehen und es neu schreiben können, damit ein Sonderfall verschwindet und zum normalen Fall wird, und das ist ein guter Code . [...] - L. Torvalds
Die Code-Ausschnitte, die er präsentiert, sind Pseudocode im C-Stil und sind einfach genug, um zu folgen. Wie Linus jedoch im Kommentar erwähnt, fehlt den Ausschnitten eine konzeptionelle Erklärung und es ist nicht sofort offensichtlich, wie die elegantere Lösung tatsächlich funktioniert.
In den nächsten beiden Abschnitten wird der technische Ansatz im Detail untersucht und zeigen, wie und warum der indirekte Adressansatz so ordentlich ist. Der letzte Abschnitt erweitert die Lösung von der Artikellöschung auf das Einfügen.
Die grundlegende Datenstruktur für eine einzig verknüpfte Liste von Ganzzahlen ist in Abbildung 1 dargestellt.
Abbildung 1 : Nur verknüpfte Liste der Ganzzahlen.
Zahlen werden willkürlich ganzzahlige Werte ausgewählt, und Pfeile geben Zeiger an. head ist ein Zeiger von Typ list_item * und jedes der Felder ist eine Instanz einer list_item -Struktur, die jeweils eine Mitgliedsvariable ( next im Code genannt) von typlist_item list_item * mit dem nächsten Element verweist.
Die C -Implementierung der Datenstruktur lautet:
struct list_item {
int value ;
struct list_item * next ;
};
typedef struct list_item list_item ;
struct list {
struct list_item * head ;
};
typedef struct list list ;Wir enthalten auch eine (minimale) API:
/* The textbook version */
void remove_cs101 ( list * l , list_item * target );
/* A more elegant solution */
void remove_elegant ( list * l , list_item * target ); Schauen wir uns die Implementierungen von remove_cs101() und remove_elegant() an. Der Code dieser Beispiele stimmt dem Pseudocode aus Linus 'Beispiel treu und kompiliert und läuft.
Abbildung 2 : Das konzeptionelle Modell für die Listendatenstruktur im CS101 -Algorithmus.
void remove_cs101 ( list * l , list_item * target )
{
list_item * cur = l -> head , * prev = NULL ;
while ( cur != target ) {
prev = cur ;
cur = cur -> next ;
}
if ( prev )
prev -> next = cur -> next ;
else
l -> head = cur -> next ;
} Der Standard -CS101 -Ansatz nutzt zwei Traversal cur prev markiert die aktuelle bzw. frühere Traversalposition in der Liste. cur beginnt am head und fährt vor, bis das Ziel gefunden wird. prev beginnt bei NULL und wird anschließend jedes Mal mit dem vorherigen Wert von cur aktualisiert, wenn cur vorrückt. Nachdem das Ziel gefunden wurde, testet der Algorithmus, wenn prev nicht NULL ist. Wenn ja, steht der Artikel nicht am Anfang der Liste und die Entfernung besteht darin, die verknüpfte Liste um cur auszurüsten. Wenn prev NULL ist, zeigt cur auf das erste Element in der Liste. In diesem Fall bedeutet das Entfernen des Listenkopfes nach vorne.
Die elegantere Version hat weniger Code und erfordert keine separate Filiale, um mit der Löschung des ersten Elements in einer Liste umzugehen.
void remove_elegant ( list * l , list_item * target )
{
list_item * * p = & l -> head ;
while ( * p != target )
p = & ( * p ) -> next ;
* p = target -> next ;
} Der Code verwendet einen indirekten Zeiger p , der die Adresse eines Zeigers auf ein Listenelement enthält, beginnend mit der Adresse des head . In jeder Iteration wird dieser Zeiger fortgeschritten, um die Adresse des Zeigers zum nächsten Listenelement zu halten, dh die Adresse des next Elements im aktuellen list_item . Wenn der Zeiger auf das Listenelement *p target , beenden wir die Suchschleife und entfernen das Element aus der Liste.
Der wichtigste Einblick ist, dass die Verwendung eines indirekten Zeigers p zwei konzeptionelle Vorteile hat:
head ein integraler Bestandteil der Datenstruktur macht. Dadurch wird die Notwendigkeit eines Sonderfalles beseitigt, um das erste Element zu entfernen.while -Schleife zu bewerten, ohne den Zeiger loslassen zu müssen, der auf target hinweist. Dies ermöglicht es uns, den Zeiger zu ändern, der auf target hinweist und mit einem einzelnen Iterator im Gegensatz zu prev und cur davonkommt.Schauen wir uns jedes dieser Punkte nacheinander an.
head Das Standardmodell interpretiert die verknüpfte Liste als Abfolge von list_item -Instanzen. Der Beginn der Sequenz kann über einen head zugegriffen werden. Dies führt zu dem in Abbildung 2 oben dargestellten konzeptionellen Modell. Der head wird lediglich als Griff betrachtet, um auf den Beginn der Liste zuzugreifen. prev und cur sind Zeiger von Typ list_item * und verweisen immer auf ein Element oder NULL .
Die elegante Implementierung verwendet das indirekte Adressierungsschema, das eine andere Ansicht der Datenstruktur ergibt:
Abbildung 3 : Das konzeptionelle Modell für die Listendatenstruktur im eleganteren Ansatz.
Hier ist p vom Typ list_item ** und hält die Adresse des Zeigers auf das aktuelle Listenelement. Wenn wir den Zeiger vorantreiben, leiten wir uns an die Adresse des Zeigers zum nächsten Listenelement weiter.
In Code bedeutet dies zu p = &(*p)->next , dh wir
(*p) : Dereferenz der Adresse zum Zeiger auf das aktuelle Listenelement->next : Dereferenz, den Zeiger erneut und das Feld ausgewählt, das die Adresse des nächsten Listenelements enthält& : Nehmen Sie die Adresse dieses Adressfelds (dh einen Zeiger auf ihn) Dies entspricht einer Interpretation der Datenstruktur, in der die Liste eine Abfolge von Zeigern ist, um list_item s (vgl. Abbildung 3).
Ein zusätzlicher Vorteil dieser besonderen Interpretation besteht darin, dass sie die Bearbeitung des next Zeigers des Vorgängers des aktuellen Elements während des gesamten Durchlaufs unterstützt.
Wenn p die Adresse eines Zeigers auf ein Listenelement hält, wird der Vergleich in der Suchschleife
while ( * p != target ) Die Suchschleife wird beendet, wenn *p gleich target ist, und sobald dies der Fall ist, können wir immer noch *p ändern, da wir seine Adresse p halten. Trotz der Iteration der Schleife bis zum target führen wir immer noch einen Griff (die Adresse des next Feldes oder des head ), mit dem der Zeiger direkt auf das Element verweist.
Dies ist der Grund, warum wir den eingehenden Zeiger auf ein Element ändern können, um auf einen anderen Ort mit *p = target->next zu verweisen und warum wir keine prev und cur -Zeiger benötigen, um die Liste für die Elemententfernung zu durchqueren.
Es stellt sich heraus, dass die Idee hinter remove_elegant() angewendet werden kann, um eine besonders präzise Implementierung einer anderen Funktion in der List -API zu ergeben: insert_before() , dh ein bestimmtes Element vor einem anderen einfügen.
Fügen wir zunächst die folgende Erklärung zur List -API in list.h : hinzu:
void insert_before ( list * l , list_item * before , list_item * item ); Die Funktion bringt einen Zeiger auf eine Liste l , einen Zeiger before einem Element in dieser Liste und einen Zeiger auf ein neuer item , das die Funktion before eingefügt wird.
Bevor wir weitermachen
static inline list_item * * find_indirect ( list * l , list_item * target )
{
list_item * * p = & l -> head ;
while ( * p != target )
p = & ( * p ) -> next ;
return p ;
} und verwenden Sie diese Funktion in remove_elegant() so
void remove_elegant ( list * l , list_item * target )
{
list_item * * p = find_indirect ( l , target );
* p = target -> next ;
}insert_before() Mit find_indirect() ist es unkompliziert, insert_before() zu implementieren:
void insert_before ( list * l , list_item * before , list_item * item )
{
list_item * * p = find_indirect ( l , before );
* p = item ;
item -> next = before ;
} Ein besonders schönes Ergebnis ist, dass die Implementierung für die Kantenfälle NULL Semantik aufweist: Wenn before dem l vorhanden before , wird das neue Element am Anfang der Liste eingefügt.
Die Prämisse der eleganteren Lösung für die Löschung von Elementen ist eine einzelne, einfache Änderung: Verwenden eines indirekten list_item ** Ziers, um die Zeiger auf die Listenelemente zu iterieren. Alles andere fließt von dort aus: Es besteht keine Notwendigkeit für einen Sonderfall oder eine Verzweigung, und ein einzelner Iterator reicht aus, um das Zielelement zu finden und zu entfernen. Es stellt sich auch heraus, dass der gleiche Ansatz eine elegante Lösung für die Einfügung von Gegenständen im Allgemeinen und für die Einführung vor einem vorhandenen Element im Besonderen bietet.
Also zurück zu Linus 'erstem Kommentar: Ist es ein guter Geschmack? Schwer zu sagen, aber es ist sicherlich eine andere, kreative und sehr elegante Lösung für eine bekannte CS-Aufgabe.
