Was ist der Grund für die Verwendung eines Doppelzeigers beim Hinzufügen eines Knotens in einer verknüpften Liste?

Die beiden folgenden Codebeispiele fügen beide einen Knoten am Anfang einer verknüpften Liste hinzu. Aber während das erste Codebeispiel einen doppelten Zeiger verwendet, verwendet das zweite Codebeispiel einen einzelnen Zeiger

Codebeispiel 1:

struct node* push(struct node **head, int data)
{
        struct node* newnode = malloc(sizeof(struct node));
        newnode->data = data;
        newnode->next = *head;
        return newnode;
}

push(&head,1);

Codebeispiel 2:

struct node* push(struct node *head, int data)
{
        struct node* newnode = malloc(sizeof(struct node));
        newnode->data = data;
        newnode->next = head;
        return newnode;
}

push(head,1)

Beide Strategien funktionieren. Viele Programme, die eine verknüpfte Liste verwenden, verwenden jedoch einen Doppelzeiger, um einen neuen Knoten hinzuzufügen. Ich weiß, was ein Doppelzeiger ist. Aber wenn ein einzelner Zeiger ausreichen würde, um einen neuen Knoten hinzuzufügen, warum verlassen sich viele Implementierungen auf doppelte Zeiger?

Gibt es einen Fall, in dem ein einzelner Zeiger nicht funktioniert, sodass wir uns für einen doppelten Zeiger entscheiden müssen?

Einige Implementierungen übergeben einen Zeiger-zu-Zeiger-Parameter, um eine direkte Änderung des Kopfzeigers zu ermöglichen, anstatt den neuen zurückzugeben. So könnte man schreiben:

// note that there's no return value: it's not needed
void push(struct node** head, int data)
{
    struct node* newnode = malloc(sizeof(struct node));
    newnode->data=data;
    newnode->next=*head;
    *head = newnode; // *head stores the newnode in the head
}

// and call like this:
push(&head,1);

Die Implementierung, die keinen Zeiger auf den Head-Zeiger verwendet, muss den neuen Head zurückgeben, und der Aufrufer ist dafür verantwortlich, ihn selbst zu aktualisieren:

struct node* push(struct node* head, int data)
{
    struct node* newnode = malloc(sizeof(struct node));
    newnode->data=data;
    newnode->next=head;
    return newnode;
}

// note the assignment of the result to the head pointer
head = push(head,1);

Wenn Sie diese Zuweisung beim Aufrufen dieser Funktion nicht vornehmen, verlieren Sie die Knoten, die Sie mit malloc zugewiesen haben, und der Kopfzeiger zeigt immer auf denselben Knoten.

Der Vorteil sollte jetzt klar sein: Wenn der Aufrufer beim zweiten vergisst, den zurückgegebenen Knoten dem Head-Zeiger zuzuweisen, passieren schlimme Dinge.

Bearbeiten:

Zeiger auf Zeiger (Doppelzeiger) ermöglicht auch die Erstellung mehrerer benutzerdefinierter Datentypen innerhalb desselben Programms (Beispiel: Erstellen von 2 verknüpften Listen)

Um die Komplexität von Doppelzeigern zu vermeiden, können wir immer eine Struktur verwenden (die als interner Zeiger fungiert).

Sie können eine Liste folgendermaßen definieren:

typedef struct list {
    struct node* root;    
} List;

List* create() {
    List* templ = malloc(sizeof(List));
    templ->root = NULL;
    return templ;
}

Verwenden Sie in Linklistenfunktionen die obige Liste auf folgende Weise: (Beispiel für Push-Funktion)

void Push(List* l, int x) {         
    struct node* n = malloc(sizeof(struct node));
    n->data = x;
    n->link = NULL;
    
    printf("Node created with value %d\n", n->data);
    if (l->root == NULL) {
        l->root = n;
    } else {
        struct node* i = l->root;
        while (i->link != NULL){
            i = i->link;
        }
        i->link = n;
    }
}

Deklarieren Sie in Ihrer Funktion main () die Liste folgendermaßen:

List* list1 = create(); 
push(list1, 10);

      

Obwohl die vorherigen Antworten gut genug sind, denke ich, dass es viel einfacher ist, in Bezug auf “Kopieren nach Wert” zu denken.

Wenn Sie einen Zeiger an eine Funktion übergeben, wird der Adresswert in den Funktionsparameter kopiert. Aufgrund des Umfangs der Funktion verschwindet diese Kopie, sobald sie zurückkehrt.

Durch die Verwendung eines Doppelzeigers können Sie den Wert des ursprünglichen Zeigers aktualisieren. Der Doppelzeiger wird immer noch nach Wert kopiert, aber das spielt keine Rolle. Alles, was Sie wirklich interessiert, ist das Ändern des ursprünglichen Zeigers, wodurch der Gültigkeitsbereich oder Stapel der Funktion umgangen wird.

Ich hoffe, dies beantwortet nicht nur Ihre Frage, sondern auch andere Fragen im Zusammenhang mit Zeigern.

Als @R. Martinho Fernandes wies in seiner Antwort darauf hin, mit Zeiger auf Zeiger als Argument in void push(struct node** head, int data) erlaubt Ihnen, die zu ändern head Zeiger direkt von innen push -Funktion, anstatt den neuen Zeiger zurückzugeben.

Es gibt noch ein weiteres gutes Beispiel, das zeigt, warum man verwendet Zeiger auf Zeiger Stattdessen kann ein einzelner Zeiger Ihren Code verkürzen, vereinfachen und beschleunigen. Du hast gefragt Hinzufügen ein neuer Knoten in der Liste, der im Gegensatz zu normalerweise keinen Zeiger-zu-Zeiger benötigt entfernen der Knoten aus der einfach verketteten Liste. Sie können das Entfernen von Knoten aus der Liste ohne Zeiger-zu-Zeiger implementieren, dies ist jedoch suboptimal. Die Details habe ich hier beschrieben. Ich empfehle dir auch zuzuschauen dieses YouTube-Video was das Problem behebt.

BTW: Wenn Sie mitzählen Linus Torvalds Meinung, sollten Sie besser lernen, wie man Pointer-to-Pointer verwendet. 😉

Linus Torvalds: (…) Am anderen Ende des Spektrums wünschte ich mir tatsächlich, dass mehr Menschen die wirklich grundlegende Art der Codierung auf niedriger Ebene verstehen würden. Kein großes, komplexes Zeug wie die sperrenlose Namenssuche, sondern einfach eine gute Verwendung von Zeigern auf Zeiger usw. Zum Beispiel habe ich zu viele Leute gesehen, die einen einfach verknüpften Listeneintrag löschen, indem sie den “vorherigen” Eintrag verfolgen , und dann den Eintrag zu löschen, tun Sie so etwas wie

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

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

Leute, die Zeiger verstehen, verwenden einfach einen “Zeiger auf den Eintragszeiger” und initialisieren diesen mit der Adresse von list_head. Und wenn sie dann die Liste durchlaufen, können sie den Eintrag ohne Bedingung entfernen, indem sie einfach ein “*pp = Eintrag->Weiter” ausführen. (…)

Andere Ressourcen, die hilfreich sein können:

• C-Doppelzeiger
• Zeiger auf Zeiger
• Warum Doppelzeiger verwenden? oder Warum Zeiger auf Zeiger verwenden?

In Ihrem speziellen Beispiel ist der Doppelzeiger nicht erforderlich. Es kann jedoch erforderlich sein, wenn Sie beispielsweise Folgendes tun würden:

struct node* push(struct node** head, int data)
{
    struct node* newnode = malloc(sizeof(struct node));
    newnode->data=data;
    newnode->next=*head;
    //vvvvvvvvvvvvvvvv
    *head = newnode; //you say that now the new node is the head.
    //^^^^^^^^^^^^^^^^
    return newnode;
}

Beobachten und Finden, WARUM…

Ich beschloss, einige Experimente durchzuführen und einige Schlussfolgerungen zu ziehen,

BEOBACHTUNG 1- Wenn die verknüpfte Liste nicht leer ist, können wir die Knoten darin (offensichtlich am Ende) hinzufügen, indem wir nur einen einzigen Zeiger verwenden.

int insert(struct LinkedList *root, int item){
    struct LinkedList *temp = (struct LinkedList*)malloc(sizeof(struct LinkedList));
    temp->data=item;
    temp->next=NULL;
    struct LinkedList *p = root;
    while(p->next!=NULL){
        p=p->next;
    }
    p->next=temp;
    return 0;
}


int main(){
    int m;
    struct LinkedList *A=(struct LinkedList*)malloc(sizeof(struct LinkedList));
    //now we want to add one element to the list so that the list becomes non-empty
    A->data=5;
    A->next=NULL;
    cout<<"enter the element to be inserted\n"; cin>>m;
    insert(A,m);
    return 0;
}

Es ist einfach zu erklären (Basic). Wir haben einen Zeiger in unserer Hauptfunktion, der auf den ersten Knoten (Wurzel) der Liste zeigt. In dem insert() übergeben wir die Adresse des Wurzelknotens und mit dieser Adresse erreichen wir das Ende der Liste und fügen einen Knoten hinzu. Wir können also schlussfolgern, dass wir, wenn wir die Adresse einer Variablen in einer Funktion (nicht der Hauptfunktion) haben, dauerhafte Änderungen am Wert dieser Variablen von dieser Funktion vornehmen können, die sich in der Hauptfunktion widerspiegeln würden.

BEOBACHTUNG 2- Die obige Methode zum Hinzufügen von Knoten ist fehlgeschlagen, wenn die Liste leer war.

int insert(struct LinkedList *root, int item){
    struct LinkedList *temp = (struct LinkedList*)malloc(sizeof(struct LinkedList));
    temp->data=item;
    temp->next=NULL;
    struct LinkedList *p=root;   
    if(p==NULL){
        p=temp;
    }
    else{
      while(p->next!=NULL){
          p=p->next;
      }
      p->next=temp;
    }
    return 0;
}



int main(){
    int m;
    struct LinkedList *A=NULL; //initialise the list to be empty
    cout<<"enter the element to be inserted\n";
    cin>>m;
    insert(A,m);
    return 0;
}

Wenn Sie weitere Elemente hinzufügen und schließlich die Liste anzeigen, werden Sie feststellen, dass die Liste keine Änderungen erfahren hat und immer noch leer ist. Die Frage, die mir in den Sinn kam, war, dass wir in diesem Fall auch die Adresse des Root-Knotens übergeben, warum Änderungen nicht als dauerhafte Änderungen vorgenommen werden und die Liste in der Hauptfunktion keine Änderungen erfährt. WARUM? WARUM? WARUM?

Eines habe ich dann beim Schreiben beobachtet A=NULL die Adresse von A wird 0. Das bedeutet jetzt A zeigt auf keinen Speicherort. Also habe ich die Linie entfernt A=NULL; und einige Änderungen an der Einfügefunktion vorgenommen.

Einige Modifikationen (unten insert() Funktion kann nur ein Element zu einer leeren Liste hinzufügen, habe diese Funktion nur zu Testzwecken geschrieben)

int insert(struct LinkedList *root, int item){
    root= (struct LinkedList *)malloc(sizeof(struct LinkedList));
    root->data=item;
    root->next=NULL;
    return 0;
}



int main(){
    int m;
    struct LinkedList *A;    
    cout<<"enter the element to be inserted\n";
    cin>>m;
    insert(A,m);
    return 0;
}

Die obige Methode schlägt auch fehl, weil in der insert() Funktion root speichert dieselbe Adresse wie A in dem main() Funktion aber nach der Zeile root= (struct LinkedList *)malloc(sizeof(struct LinkedList)); die darin gespeicherte Adresse root Änderungen. Also jetzt, root (in insert() Funktion) und A (in main() Funktion) verschiedene Adressen speichern.

Das richtige endgültige Programm wäre also

int insert(struct LinkedList *root, int item){
    root->data=item;
    root->next=NULL;
    return 0;
}



int main(){
    int m;
    struct LinkedList *A = (struct LinkedList *)malloc(sizeof(struct LinkedList));
    cout<<"enter the element to be inserted\n";
    cin>>m;
    insert(A,m);
    return 0;
}

Aber wir wollen nicht zwei verschiedene Funktionen zum Einfügen, eine, wenn die Liste leer ist, und die andere, wenn die Liste nicht leer ist. Jetzt kommt der Doppelzeiger, der die Sache vereinfacht.

Eine wichtige Sache, die mir aufgefallen ist, ist, dass Zeiger Adressen speichern und wenn sie mit ‘*’ verwendet werden, geben sie einen Wert an dieser Adresse, aber Zeiger selbst haben ihre eigene Adresse.

Hier nun das komplette Programm und später die Konzepte erklären.

int insert(struct LinkedList **root,int item){
    if(*root==NULL){
        (*root)=(struct LinkedList *)malloc(sizeof(struct LinkedList));
        (*root)->data=item;
        (*root)->next=NULL;
    }
    else{
        struct LinkedList *temp=(struct LinkedList *)malloc(sizeof(struct LinkedList));
        temp->data=item;
        temp->next=NULL;
        struct LinkedList *p;
        p=*root;
        while(p->next!=NULL){
            p=p->next;
        }
        p->next=temp;
    }
    return 0;
}


int main(){
    int n,m;
    struct LinkedList *A=NULL;
    cout<<"enter the no of elements to be inserted\n";
    cin>>n;
    while(n--){
        cin>>m;
        insert(&A,m);
    }
    display(A);
    return 0;
}

Nachfolgend die Beobachtungen,

1. root speichert die Adresse von Zeiger A (&A) , *root speichert die vom Zeiger gespeicherte Adresse A und **root speichert den Wert an der Adresse gespeichert von A. In einfacher Sprache root=&A, *root= A und **root= *A.

2. wenn wir schreiben *root= 1528 dann bedeutet es, dass der Wert an der Adresse gespeichert ist root wird 1528 und seit Adresse gespeichert in root ist die Adresse von Zeiger A (&A) also jetzt A=1528 (dh Adresse gespeichert in A ist 1528) und diese Änderung ist dauerhaft.

wann immer wir den Wert von ändern *root Wir ändern tatsächlich den Wert an der in gespeicherten Adresse root und da root=&A (Adresse des Zeigers A) ändern wir indirekt den Wert von A oder Adresse gespeichert in A.

also jetzt wenn A=NULL (Liste ist leer) *root=NULL also erstellen wir den ersten Knoten und speichern seine Adresse unter *root dh indirekt speichern wir die Adresse des ersten Knotens bei A. Wenn list nicht leer ist, ist alles dasselbe wie in den vorherigen Funktionen mit einem einzelnen Zeiger, außer dass wir root in geändert haben *root da das, was in root gespeichert war, jetzt in gespeichert wird *root.

Nehmen wir das einfach zB:

void my_func(int *p) {
        // allocate space for an int
        int *z = (int *) malloc(sizeof(int));
        // assign a value
        *z = 99;

        printf("my_func - value of z: %d\n", *z);

        printf("my_func - value of p: %p\n", p);
        // change the value of the pointer p. Now it is not pointing to h anymore
        p = z;
        printf("my_func - make p point to z\n");
        printf("my_func - addr of z %p\n", &*z);
        printf("my_func - value of p %p\n", p);
        printf("my_func - value of what p points to: %d\n", *p);
        free(z);
}

int main(int argc, char *argv[])
{
        // our var
        int z = 10;

        int *h = &z;

        // print value of z
        printf("main - value of z: %d\n", z);
        // print address of val
        printf("main - addr of z: %p\n", &z);

        // print value of h.
        printf("main - value of h: %p\n", h);

        // print value of what h points to
        printf("main - value of what h points to: %d\n", *h);
        // change the value of var z by dereferencing h
        *h = 22;
        // print value of val
        printf("main - value of z: %d\n", z);
        // print value of what h points to
        printf("main - value of what h points to: %d\n", *h);


        my_func(h);

        // print value of what h points to
        printf("main - value of what h points to: %d\n", *h);

        // print value of h
        printf("main - value of h: %p\n", h);


        return 0;
}

Ausgabe:

main - value of z: 10
main - addr of z: 0x7ffccf75ca64
main - value of h: 0x7ffccf75ca64
main - value of what h points to: 10
main - value of z: 22
main - value of what h points to: 22
my_func - value of z: 99
my_func - value of p: 0x7ffccf75ca64
my_func - make p point to z
my_func - addr of z 0x1906420
my_func - value of p 0x1906420
my_func - value of what p points to: 99
main - value of what h points to: 22
main - value of h: 0x7ffccf75ca64

wir haben diese Signatur für my_func:

void my_func(int *p);

Wenn Sie sich die Ausgabe ansehen, ist der Wert, auf den h zeigt, immer noch 22 und der Wert von h ist derselbe, obwohl er in my_func geändert wurde. Woher ?

Nun, in my_func manipulieren wir den Wert von p, der nur ein lokaler Zeiger ist. nach Anruf:

my_func(ht);

in main() enthält p den Wert von h, der die Adresse der z-Variablen darstellt, die in der Hauptfunktion deklariert ist.

Wenn wir in my_func() den Wert von p ändern, um den Wert von z zu halten, das ein Zeiger auf eine Speicherstelle ist, für die wir Speicherplatz zugewiesen haben, ändern wir nicht den Wert von h, den wir haben übergeben, sondern nur den Wert des lokalen Zeigers p. Grundsätzlich enthält p nicht mehr den Wert von h, sondern die Adresse eines Speicherplatzes, auf den z zeigt.

Nun, wenn wir unser Beispiel ein wenig ändern:

#include <stdio.h>
#include <stdlib.h>

void my_func(int **p) {
    // allocate space for an int
    int *z = (int *) malloc(sizeof(int));
    // assign a value
    *z = 99;

    printf("my_func - value of z: %d\n", *z);

    printf("my_func - value of p: %p\n", p);
    printf("my_func - value of h: %p\n", *p);
    // change the value of the pointer p. Now it is not pointing to h anymore
    *p = z;
    printf("my_func - make p point to z\n");
    printf("my_func - addr of z %p\n", &*z);
    printf("my_func - value of p %p\n", p);
    printf("my_func - value of h %p\n", *p);
    printf("my_func - value of what p points to: %d\n", **p);
    // we are not deallocating, because we want to keep the value in that
    // memory location, in order for h to access it.
    /* free(z); */
}

int main(int argc, char *argv[])
{
    // our var
    int z = 10;

    int *h = &z;

    // print value of z
    printf("main - value of z: %d\n", z);
    // print address of val
    printf("main - addr of z: %p\n", &z);

    // print value of h.
    printf("main - value of h: %p\n", h);

    // print value of what h points to
    printf("main - value of what h points to: %d\n", *h);
    // change the value of var z by dereferencing h
    *h = 22;
    // print value of val
    printf("main - value of z: %d\n", z);
    // print value of what h points to
    printf("main - value of what h points to: %d\n", *h);


    my_func(&h);

    // print value of what h points to
    printf("main - value of what h points to: %d\n", *h);

    // print value of h
    printf("main - value of h: %p\n", h);
    free(h);


    return 0;
}

wir haben die folgende Ausgabe:

main - value of z: 10
main - addr of z: 0x7ffcb94fb1cc
main - value of h: 0x7ffcb94fb1cc
main - value of what h points to: 10
main - value of z: 22
main - value of what h points to: 22
my_func - value of z: 99
my_func - value of p: 0x7ffcb94fb1c0
my_func - value of h: 0x7ffcb94fb1cc
my_func - make p point to z
my_func - addr of z 0xc3b420
my_func - value of p 0x7ffcb94fb1c0
my_func - value of h 0xc3b420
my_func - value of what p points to: 99
main - value of what h points to: 99
main - value of h: 0xc3b420

Jetzt haben wir tatsächlich den Wert, den h hält, von my_func geändert, indem wir Folgendes tun:

1. geänderte Funktionssignatur
2. Aufruf von main(): my_func(&h); Grundsätzlich übergeben wir die Adresse des h-Zeigers an den Doppelzeiger p, der als Parameter in der Signatur der Funktion deklariert ist.
3. in my_func() machen wir: *p = z; wir dereferenzieren den Doppelzeiger p, eine Ebene. Im Grunde wurde dies so übersetzt, wie Sie es tun würden: h = z;

Der Wert von p enthält nun die Adresse des h-Zeigers. h-Zeiger enthält die Adresse von z.

Sie können beide Beispiele nehmen und sie unterscheiden. Um auf Ihre Frage zurückzukommen, benötigen Sie einen doppelten Zeiger, um Änderungen an dem Zeiger vorzunehmen, den Sie direkt von dieser Funktion übergeben haben.

Denken Sie an den Speicherort für Kopf wie [HEAD_DATA].

In Ihrem zweiten Szenario ist main_head der aufrufenden Funktion nun der Zeiger auf diesen Speicherort.

main_head —>[HEAD_DATA]

In Ihrem Code hat es den Wert des Zeigers main_head an die Funktion gesendet (dh die Adresse des Speicherplatzes von head_data). Sie haben das in die Funktion local_head kopiert. also jetzt

local_head —> [HEAD_DATA]

und

main_head —> [HEAD_DATA]

Beide zeigen auf denselben Ort, sind aber im Wesentlichen unabhängig voneinander. Wenn Sie also local_head = newnode; was du getan hast ist

local_head–/–>[HEAD_DATA]

local_head —–> [NEWNODE_DATA]

Sie haben einfach die Speicheradresse des vorherigen Speichers durch eine neue im lokalen Zeiger ersetzt. Der main_head (Zeiger) zeigt immer noch auf den alten [HEAD_DATA]