Link-Liste: Einfügen eines Knotens mit Rekursion

Question

Ich frage mich, wie machen die folgenden zwei Teile des Codes die gleiche Aufgabe, einen neuen Knoten in eine Linkliste einzufügen?

verison1

version2

In Version1 gibt es einen prev Zeiger, der den vorhergehenden Knoten zu dem neuen Knoten wickeln kann.

Aber ich sehe das nicht in Version2. In Version 2 ist die vorherige Verknüpfung unterbrochen (d. H., Es wird nicht mit dem neuen Knoten verknüpft). Fehle ich etwas?

Answer 1

Lassen Sie uns in Ihre version2 Insertion graben:

void RecInsertSorted(Entry*& list, Entry* newOne) { 
    if (list == nullptr || newOne->name < list->name) { 
     newOne->next = list; 
     list = newOne; 
    else { 
     RecInsertSorted(list->next, newOne); 
    } 
} 

Sie benötigen keine prev brauchen, da die Arbeit der Anruf erfolgt. Warum das? Weil der list Parameter eine Referenz auf einen Zeiger ist.

Nehmen wir an, wir fügen newOne zwischen dem ersten und dem zweiten Element ein. Am Ende wollen Sie Ihre Liste wie folgt aussehen:

element1 -> Newone -> element2

Wenn die Bedingung newOne->name < list->name erfüllt ist, list element2 bezieht. Aber das ist eine Referenz auf einen Zeiger, die Referenz bezieht sich auf element1-> next! Wenn also die Anweisung list = newOne; ausgeführt wird, aktualisiert sie element1->next entsprechend und Ihre Liste ist gut gebildet.

Ähnlich, wenn newOne am Ende eingefügt wird, ist listnullptr. Aber wieder ist es eine Referenz, so newOne->next wird nullptr und newOne wird das Ende der Liste.

Auch wenn newOne vor dem ersten Element eingefügt werden muss, aktualisiert es einige head Zeiger Sie behalten den Kopf Ihrer Liste zu verfolgen ... daher wird das erste Element Ihrer Liste.