Jaki jest powód użycia podwójnego wskaźnika podczas dodawania węzła do listy połączonej?

W twoim konkretnym przykładzie nie ma potrzeby stosowania podwójnego wskaźnika. Jednak może to być potrzebne, jeśli, na przykład, miałbyś zrobić coś takiego:

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;
}

Weźmy to proste np:

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;
}

Wyjście:

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

Mamy ten podpis dla my_func:

void my_func(int *p);

Jeśli spojrzysz na wyjście, na końcu wartość, na którą wskazuje h, jest nadal 22 i wartość h jest taka sama, ale w my_func została zmieniona. Jak to ?

Cóż, w my_func manipulujemy wartością p, która jest tylko lokalnym wskaźnikiem. po wywołaniu:

my_func(ht);

W main(), P przechowuje wartość H, która reprezentuje adres z zmienna, zadeklarowana w funkcji głównej.

W my_func (), kiedy zmieniamy wartość p na wartość z, która jest wskaźnikiem do miejsca w pamięci, dla którego przydzielono nam miejsce, nie zmieniamy wartości h, którą przekazaliśmy, ale tylko wartość lokalnego wskaźnika P. zasadniczo, p nie przechowuje już wartości h, przechowuje adres lokalizacji pamięci, na którą wskazuje z.

Teraz, jeśli zmienimy trochę nasz przykład:

#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;
}

Mamy "follwoing output": {]}

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

W rzeczywistości zmieniliśmy wartość H z my_func, wykonując to:

1. zmieniona sygnatura funkcji
2. wywołanie z main (): my_func (&h); zasadniczo przekazujemy adres wskaźnika h do podwójnego wskaźnika p, zadeklarowanego jako parametr w sygnaturze funkcji.
3. w my_func() robimy: * P = z; dereferujemy Podwójny wskaźnik p, jeden poziom. Zasadniczo to zostało przetłumaczone tak, jak byś to zrobił: h = z;

Wartość p zawiera teraz adres wskaźnika H. wskaźnik H przechowuje adres z.

Możesz wziąć oba przykłady i je rozróżnić. Wracając do pytania, potrzebujesz podwójnego wskaźnika, aby dokonać modyfikacji wskaźnika, który przekazałeś bezpośrednio z tej funkcji.

Jako @R. Martinho Fernandes wskazał w jego odpowiedź , użycie pointer to pointer jako argumentu w void push(struct node** head, int data) pozwala na zmianę head wskaźnika bezpośrednio z push zamiast zwracania nowego wskaźnika.

Jest jeszcze jeden dobry przykład, który pokazuje, dlaczego użycie Wskaźnik do wskaźnika zamiast pojedynczego wskaźnika może skrócić, uprościć i przyspieszyć kod. Pytałeś o dodanie nowego węzła do listy, który prawdopodobnie zazwyczaj nie wymaga wskaźnika do wskaźnika w przeciwieństwie do usuwania węzła z listy pojedynczo połączonych. Możesz zaimplementować usuwanie węzła z listy bez wskaźnika do wskaźnika, ale jest to nieoptymalne. Opisałem szczegóły tutaj . Polecam również obejrzeć ten filmik na YouTube , który porusza problem.

BTW: jeśli liczyć z Linus Torvalds opinion , lepiej naucz się używać wskaźnika do wskaźnika. ;-)

Linus Torvalds: (...) Na przeciwległym końcu spektrum, chciałbym, aby więcej ludzi zrozumiało naprawdę rdzeń niskopoziomowego rodzaju kodowania. Nie duże, skomplikowane rzeczy, takie jak wyszukiwanie nazw bez blokady, ale po prostu dobre wykorzystanie wskaźników do wskaźników itp. Na przykład widziałem zbyt wiele osób, które usuwają pojedynczo połączony wpis listy, śledząc wpis "prev", a następnie usuwając wpis, robiąc coś w stylu

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

I ilekroć widzę taki kod, po prostu odchodzę "Ta osoba nie rozumie wskazówek". I to niestety dość powszechne.

Ludzie, którzy rozumieją wskaźniki, po prostu używają "wskaźnika do wskaźnika wejścia" i inicjalizują go adresem list_head. A następnie, gdy przemierzają listę, mogą usunąć wpis bez użycia żadnych warunków, po prostu wykonując "* pp = wpis- > następny". (...)

Inne zasoby, które mogą być pomocne:

• C Podwójne wskaźniki
• wskaźniki do Wskaźniki
• dlaczego warto używać podwójnego wskaźnika? albo po co używać wskaźników do wskaźników?

Chociaż poprzednie odpowiedzi są wystarczająco dobre, myślę, że o wiele łatwiej jest myśleć w kategoriach "Kopiuj według wartości".

Kiedy przekazujesz wskaźnik do funkcji, wartość adresu jest kopiowana do parametru funkcji. Ze względu na zakres funkcji, Kopia zniknie po jej powrocie.

Używając podwójnego wskaźnika, będziesz mógł zaktualizować oryginalną wartość wskaźnika. Podwójny wskaźnik nadal będzie kopiowany według wartości, ale to nie ma znaczenia. Wszystko, co cię naprawdę obchodzi, to modyfikowanie oryginalnego wskaźnika, a tym samym omijanie zakresu funkcji lub stosu.

Mam nadzieję, że to odpowiada nie tylko na twoje pytanie, ale również na inne pytania związane z wskaźnikiem.

Odpowiedź jest bardziej oczywista, jeśli poświęcisz czas na napisanie działającej funkcji wstawiania węzłów; twoja nie jest jedną z nich.

Musisz być w stanie napisać nad głową, aby przesunąć go do przodu, więc potrzebujesz wskaźnika do wskaźnika do głowy, aby można było go dereferować, aby uzyskać wskaźnik do głowy i zmienić go.

Wyobraź sobie przypadek, w którym musisz wprowadzić pewne zmiany i te zmiany powinny odzwierciedlać się w funkcji wywołującej.

Przykład:

void swap(int* a,int* b){
  int tmp=*a;
  *a=*b;
  *b=tmp;
}

int main(void){
  int a=10,b=20;

  // To ascertain that changes made in swap reflect back here we pass the memory address
  // instead of the copy of the values

  swap(&a,&b);
}

Podobnie przekazujemy adres pamięci nagłówka listy.

W ten sposób, jeśli jakiś węzeł zostanie dodany i wartość Head zostanie zmieniona, to zmiana ta odbija się Wstecz i nie musimy ręcznie resetować głowy wewnątrz funkcji wywołującej.

Poza tym drugi kod będzie działał szybciej, ponieważ nie marnujemy czasu na kopiowanie i zwracanie, ponieważ pracujemy bezpośrednio z pamięcią.

Obserwacja i odkrycie, dlaczego...

Obserwacja 1 - jeśli połączona lista nie jest pusta, możemy dodać do niej węzły (oczywiście na końcu) używając tylko jednego wskaźnika.

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;
}

Its simple to explain (Basic). Mamy wskaźnik w naszej głównej funkcji, który wskazuje na pierwszy węzeł (root) listy. W funkcji insert() przekazujemy adres węzła głównego i używając tego adres docieramy do końca listy i dodajemy do niej węzeł. Możemy więc wnioskować, że jeśli mamy adres zmiennej w funkcji (nie funkcji głównej) możemy dokonać trwałych zmian wartości tej zmiennej z tej funkcji, które odzwierciedlałyby w funkcji głównej.

Obserwacja 2 - powyższa metoda dodawania węzła nie powiodła się, gdy lista była pusta.

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;
}

Jeśli nadal dodajesz elementy i ostatecznie wyświetlasz listę, zauważysz, że lista ma bez zmian i nadal jest pusta. Pytanie, które przyszło mi do głowy, było w tym przypadku również przekazujemy adres węzła głównego, to dlaczego modyfikacje nie dzieją się jako stałe modyfikacje i lista w głównej funkcji nie ulega zmianom. Dlaczego? Dlaczego? Dlaczego?

Wtedy zauważyłem jedną rzecz, kiedy piszę A=NULL adres A staje się 0. Oznacza to, że teraz A nie wskazuje na żadne miejsce w pamięci. Usunąłem więc linię A=NULL; i dokonałem jakiejś modyfikacji w funkcja insert.

Niektóre modyfikacje,(poniżej insert() funkcja może dodać tylko jeden element do pustej listy, po prostu napisał tę funkcję w celu testowania)

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;
}

Powyższa metoda również się nie powiedzie, ponieważ w funkcji insert() root przechowuje ten sam adres co A w funkcji main(), ale po linii root= (struct LinkedList *)malloc(sizeof(struct LinkedList)); zmienia się adres przechowywany w root. Tak więc teraz root (w funkcji insert()) i A (w funkcji main()) przechowują różne adresy.

Więc poprawny finał program będzie,

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;
}

Ale nie chcemy dwóch różnych funkcji do wstawiania, jednej, gdy lista jest pusta, a drugiej, gdy lista nie jest pusta. Teraz przychodzi Podwójny wskaźnik, który ułatwia sprawę.

Jedną z rzeczy, które zauważyłem, co jest ważne, jest to, że pointers adres sklepu a gdy używane z ' * ' dają wartość pod tym adresem, ale wskaźniki sami mają swój własny adres.

Teraz tutaj jest kompletny program, a później wyjaśnić koncepcje.

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;
}

Poniżej znajdują się spostrzeżenia,

1. root przechowuje adres wskaźnika A (&A) , *root przechowuje adres przechowywany przez wskaźnik A i **root przechowuje wartość pod adresem przechowywanym przez A. W prostym języku root=&A, *root= A i **root= *A.

2. jeśli napiszemy *root= 1528 to oznacza to, że wartość pod adresem zapisanym w root staje się 1528, a ponieważ adres zapisany w root jest adresem wskaźnika a (&A) tak więc teraz A=1528 (tzn. adres przechowywany w A to 1528) i ta zmiana jest stała.

Gdy zmieniamy wartość *root zmieniamy wartość na adres przechowywany w root, a od root=&A (adres wskaźnika A) pośrednio zmieniamy wartość A lub adres przechowywany w A.

Więc teraz, Jeśli A=NULL (lista jest pusta) *root=NULL, tworzymy pierwszy węzeł i przechowujemy jego adres pod *root tzn. pośrednio przechowujemy adres pierwszego węzła pod A. Jeśli lista nie jest puste, wszystko jest takie samo jak w poprzednich funkcjach za pomocą pojedynczego WSKAŹNIKA, z wyjątkiem tego, że zmieniliśmy root na *root, ponieważ to, co było przechowywane w root jest teraz przechowywane w *root.

Kiedy przekazujemy wskaźnik jako parametr w funkcji i chcemy zaktualizować w tym samym wskaźniku, używamy podwójnego wskaźnika.

Z drugiej strony, jeśli przekażemy wskaźnik jako parametr w funkcji i złapiemy go w jednym wskaźniku, to będziemy musieli zwrócić wynik do wywołania funkcji z powrotem, aby użyć wyniku.

Pomyśl o lokalizacji pamięci dla głowy jak [HEAD_DATA].

Teraz w drugim scenariuszu, main_head funkcji wywołującej jest wskaźnikiem do tej lokalizacji.

main_head - - - >[HEAD_DATA]

W Twoim kodzie wysłano wartość wskaźnika main_head do funkcji (tj. adres lokalizacji pamięci head_data) Skopiowałeś to do local_head w funkcji. so now

local_head - - - > [HEAD_DATA]

I

main_head - - -> [HEAD_DATA]

Oba wskazują na to samo miejsce, ale są zasadniczo niezależne od siebie. Więc kiedy piszesz local_head = newnode; what you did is

local_head-- / -- >[HEAD_DATA]

local_head - - - - - > [NEWNODE_DATA]

Po prostu zamieniłeś adres pamięci poprzedniej pamięci na nowy w lokalnym wskaźniku. Main_head (wskaźnik) nadal wskazuje na stary [HEAD_DATA]

Myślę, że chodzi o to, że ułatwia to aktualizowanie węzłów w powiązanej liście. Gdzie normalnie trzeba śledzić wskaźnik dla poprzedniego i bieżącego można mieć Podwójny wskaźnik dbać o to wszystko.

#include <iostream>
#include <math.h>

using namespace std;

class LL
{
    private:
        struct node 
        {
            int value;
            node* next;
            node(int v_) :value(v_), next(nullptr) {};
        };
        node* head;

    public:
        LL() 
        {
            head = nullptr;
        }
        void print() 
        {
            node* temp = head;
            while (temp) 
            {
                cout << temp->value << " ";
                temp = temp->next;
            }
        }
        void insert_sorted_order(int v_) 
        {
            if (!head)
                head = new node(v_);
            else
            {
                node* insert = new node(v_);
                node** temp = &head;
                while ((*temp) && insert->value > (*temp)->value)
                    temp = &(*temp)->next;
                insert->next = (*temp);
                (*temp) = insert;
            }
        }

        void remove(int v_)
        {
            node** temp = &head;
            while ((*temp)->value != v_)
                temp = &(*temp)->next;
            node* d = (*temp);
            (*temp) = (*temp)->next;
            delete d;
        }

        void insertRear(int v_)//single pointer
        {
            if (!head)
                head = new node(v_);
            else
            {
                node* temp = new node(v_);
                temp->next = head;
                head = temp;
            }
        }
};

Standardowym sposobem obsługi połączonych list w C jest automatyczne aktualizowanie wskaźnika głowy przez funkcje push i pop.

C jest "wywołanie przez wartość", co oznacza, że kopie parametrów są przekazywane do funkcji. Jeśli przekażesz tylko wskaźnik głowy, Żadna lokalna aktualizacja dokonana do tego wskaźnika nie będzie widoczna przez dzwoniącego. Dwa obejścia to

1) Podaj adres głównego wskaźnika. (Pointer to head pointer)

2) zwraca nowy wskaźnik głowy i polega na tym, że rozmówca zaktualizuj wskaźnik głowy.

Opcja 1) jest najłatwiejsza, choć na początku trochę myląca.

Powiedzmy, że zapisałem Twój adres na kartce 1. Teraz, jeśli chcę przekazać swój adres domowy komuś innemu, mogę albo skopiować adres z karty - 1 do karty-2 i podać kartę-2, albo mogę podać kartę-1 bezpośrednio. Tak czy inaczej osoba będzie znać adres i może się z Tobą skontaktować. Ale kiedy podam card-1 Bezpośrednio, adres można zmienić na card-1, ale jeśli podałem card-2 tylko adres na card-2 można zmienić, ale nie na card-1.

Przekazanie wskaźnika do wskaźnika jest podobne do podania dostęp do karty-1 bezpośrednio. Przekazanie wskaźnika jest podobne do utworzenia nowej kopii adresu.