In einem Interview auf der TED 2016 (14.10 Uhr) spricht Linus Torvalds über einen guten Codierungsstil. Als Beispiel gibt er zwei Möglichkeiten an, um Elemente aus einfach verknüpften Listen zu entfernen (siehe unten). Die erste Option hat einen Sonderfall, die andere nicht. Linus bevorzugt letzteres.



Sein Kommentar:

[...] Sie müssen nicht darüber nachdenken, warum es hier keine if-Anweisung gibt. Es ist wichtig, das Problem aus einer anderen Perspektive zu betrachten und neu zu schreiben, damit der Sonderfall verschwindet und zu einem normalen Fall wird, und das ist guter Code . - L. Torvalds

Linus zeigt als Beispiel einen ziemlich einfachen Pseudocode im C-Stil. Bietet aber keine konzeptionelle Erklärung. Daher ist nicht sofort klar, wie ein indirekter Zeiger funktioniert.



Schauen wir uns diese Lösung und ihre Vorteile genauer an. Als Bonus wird nicht nur das Löschen, sondern auch das Einfügen eines Elements über die indirekte Adressierung angezeigt.

Der Code

Die grundlegende Datenstruktur für eine einfach verknüpfte Liste von ganzen Zahlen ist in Fig. 4 gezeigt. 1.





Abb. 1. Eine einfach verknüpfte Liste von Ganzzahlen



Zahlen sind zufällig ausgewählte Ganzzahlwerte, und Pfeile entsprechen Zeigern: head



 - Dies ist ein Typzeiger IntListItem*



. Alle Blöcke sind Instanzen einer Struktur IntListItem



mit jeweils einer eigenen Variablen ( next



im Code) des Typs IntListItem*



, die auf das nächste Element verweist.



Implementierung der Datenstruktur in C:

struct IntListItem {
    int value;
    struct IntListItem* next;
};
typedef struct IntListItem IntListItem;

struct IntList {
    IntListItem* head;
};
typedef struct IntList IntList;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Auch die (minimale) API:

/* The textbook version */
void remove_cs101(IntList* l, IntListItem* target);
/* A more elegant solution */
void remove_elegant(IntList* l, IntListItem* target);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Schauen wir uns nun die Implementierungen remove_cs101()



und an remove_elegant()



. Der Code der Beispiele widerspricht nicht dem Pseudocode aus Linus 'Beispiel, sondern wird kompiliert und ausgeführt.

Basisversion

Zahl: 2. Konzeptionelles Modell der Listendatenstruktur im Basisalgorithmus

void remove_cs101(IntList *l, IntListItem *target)
{
    IntListItem *cur = l->head, *prev = NULL;
    while (cur != target) {
        prev = cur;
        cur = cur->next;
    }
    if (prev) {
        prev->next = cur->next;
    } else {
        l->head = cur->next;
    }
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Im Standardansatz zwei Durchlaufzeiger cur



und prev



, die die aktuelle bzw. vorherige Durchlaufposition in der Liste markieren. cur



Beginnt am Anfang der Liste head



und bewegt sich vorwärts, bis das Ziel gefunden ist. Es prev



beginnt wiederum mit NULL



und wird anschließend cur



jedes Mal, wenn es vorwärts geht, auf den vorherigen Wert aktualisiert . Wenn das Ziel gefunden wird, prüft der Algorithmus, ob es nicht prev



Null ist. cur



In diesem Fall zeigt es auf das erste Element in der Liste. In diesem Fall bedeutet Löschen, dass der Kopf der Liste nach vorne verschoben wird.

Eine elegantere Lösung

Die elegantere Version hat weniger Code und erfordert keinen separaten Zweig, um das erste Element in der Liste zu entfernen.

void remove_elegant(IntList *l, IntListItem *target)
{
    IntListItem **p = &l->head;
    while ((*p) != target) {
        p = &(*p)->next;
    }
    *p = target->next;
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Der Code verwendet einen indirekten Zeiger p



, der die Adresse des Zeigers auf das Listenelement enthält, beginnend mit der Adresse head



. In jeder Iteration wird dieser Zeiger erweitert, um die Adresse des Zeigers auf das nächste Element in der Liste aufzunehmen, dh die Adresse des Elements next



im aktuellen Element IntListItem



. Wenn der Zeiger auf das Listenelement (*p)



gleich ist target



, verlassen wir die Suchschleife und entfernen das Element aus der Liste.

Wie es funktioniert?

Ein indirekter Zeiger hat p



zwei konzeptionelle Vorteile:

1. Ermöglicht die Interpretation einer verknüpften Liste so, dass der Zeiger head
   
   
   
   ein integraler Bestandteil der Datenstruktur wird. Dadurch entfällt die Notwendigkeit eines Sonderfalls zum Entfernen des ersten Elements.
   
   
2. Außerdem können Sie den Status der Schleife auswerten, while
   
   
   
   ohne den Zeiger loslassen zu müssen, auf den gezeigt wird target
   
   
   
   . Auf diese Weise können Sie den Zeiger ändern target
   
   
   
   und mit einem einzigen Iterator auskommen, im Gegensatz zu prev
   
   
   
   und cur
   
   
   
   .

Schauen wir uns nacheinander die einzelnen Elemente an.

Kopfzeiger-Integration

Das Standardmodell interpretiert eine verknüpfte Liste als eine Folge von Instanzen IntListItem



. Der Beginn der Sequenz kann mit einem Zeiger erhalten werden head



. Dies führt zu dem in Abb. 2. Der Zeiger wird head



einfach als Handle behandelt, um auf den Anfang der Liste zuzugreifen. prev



und cur



sind Typzeiger IntListItem*



und zeigen immer auf oder NULL



.



Bei der eleganten Implementierung wird ein indirektes Adressierungsschema verwendet, das eine andere Ansicht der Datenstruktur bietet:





Abb. 3. Konzeptionelles Modell der Listendatenstruktur in einer eleganteren Lösung



Hier wird p



der Typ dargestelltIntListItem**



und enthält die Adresse des Zeigers auf das aktuelle Listenelement. Wenn sich der Zeiger vorwärts bewegt, ändert sich seine Adresse zum nächsten Element.



Im Code sieht es so aus p = &(*p)->next



:

1. (*p)
   
   
   
   : Dereferenzieren Sie die Adresse des Zeigers auf das aktuelle Listenelement.
   
   
2. ->next
   
   
   
   : diesen Zeiger erneut dereferenzieren und das Feld mit der Adresse des nächsten Elements auswählen.
   
   
3. &
   
   
   
   : Nehmen Sie die Adresse dieses Feldes (dh holen Sie sich einen Zeiger darauf).

Dies steht im Einklang mit der Interpretation einer Datenstruktur, bei der eine Liste eine Folge von Zeigern auf Elemente ist IntListItem



(Abbildung 3).

Feinschliff

Ein zusätzlicher Vorteil dieser speziellen Interpretation besteht darin, dass der Zeiger während des gesamten Durchlaufs next



für den Vorgänger des aktuellen Elements bearbeitet werden kann .



Wenn p



die Adresse eines Zeigers auf ein Element der Liste enthält, wird der Vergleich in der Suchschleife wie folgt:

while ((*p) != target) {
    ...
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Der Suchzyklus endet, wenn er (*p)



gleich ist target



, und sobald dies geschieht, können wir ihn noch ändern (*p)



, da wir seine Adresse behalten p



. Somit wird, obwohl die Schleife bis zum Ende iteriert, ein Deskriptor (Feldadresse next



oder Zeiger head



) gespeichert , mit dem der Zeiger direkt auf ein Element geändert werden kann.



Aus diesem Grund können wir die Eingabe in den Elementzeiger so ändern, dass sie auf eine andere Position zeigt. *p = target->next



Daher benötigen wir keine Bypass-Zeiger prev



und müssen cur



das Element entfernen.

Neue Bewerbung

Es stellt sich heraus, dass dieselbe Idee auf eine extrem lakonische Implementierung einer anderen Funktion in verknüpften Listen angewendet werden kann: insert_before()



das Einfügen dieses Elements vor einem anderen.

Einfügen vor vorhandenem Element

Fügen wir zunächst die folgende Deklaration hinzu list.h



:

void insert_before(IntList *l, IntListItem *before, IntListItem *item);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Die Funktion nimmt einen Zeiger auf die Liste l, einen Zeiger vor einem Element in dieser Liste und einen Zeiger auf ein neues Listenelement, das die Funktion davor einfügt.

Schnelles Refactoring

Bevor wir fortfahren, machen wir die Suchschleife zu einer separaten Funktion:

static inline IntListItem **find_indirect(IntList *l, IntListItem *target)
{
    IntListItem **p = &l->head;
    while ((*p) && (*p) != target) {
        p = &(*p)->next;
    }
    return p;
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

und benutze es in remove_elegant()



:

void remove_elegant(IntList *l, IntListItem *target)
{
    IntListItem **p = find_indirect(l, target);
    *p = target->next;
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Implementierung von Insert_before ()

Die Verwendung find_indirect()



ist einfach zu implementieren insert_before()



:

void insert_before(IntList *l, IntListItem *before, IntListItem *item)
{
    IntListItem **p = find_indirect(l, before);
    *p = item;
    item->next = before;
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Besonders erfreulich ist die solide Semantik für Randfälle: Wenn sie before



auf den Kopf der Liste zeigt, wird am Anfang ein neues Element eingefügt, wenn es before



null oder ungültig ist (dh in nicht vorhanden ist l



), wird am Ende ein neues Element hinzugefügt.

Fazit

Die Voraussetzung für eine elegantere Lösung zum Löschen von Elementen ist eine einfache Änderung: ein indirekter Zeiger IntListItem**



, der über Zeiger auf Listenelemente iteriert. Alles andere fließt von dort: Sonderfälle oder Zweige sind nicht erforderlich. Ein Iterator reicht aus, um das Zielelement zu finden und zu entfernen. Und es stellt sich heraus, dass der gleiche Ansatz eine elegante Lösung für das Einfügen im Allgemeinen und das Einfügen vor einem vorhandenen Element im Besonderen bietet .



Zurück zu Linus 'anfänglicher Bemerkung: Ist dies ein Indikator für guten Geschmack? Schwer zu sagen. Aber es gibt eindeutig eine kreative und sehr elegante Lösung für ein bekanntes Problem.