Qual è la ragione per utilizzare un doppio puntatore quando si aggiunge un nodo in un elenco collegato?

I due esempi di codice seguenti aggiungono entrambi un nodo nella parte superiore di un elenco collegato. Ma mentre il primo esempio di codice usa un doppio puntatore, il secondo esempio di codice usa un singolo puntatore

esempio di codice 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); 

esempio di codice 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) 

Entrambe le strategie funzionano. Tuttavia, molti programmi che utilizzano un elenco collegato utilizzano un doppio puntatore per aggiungere un nuovo nodo. So cos’è un doppio puntatore. Ma se un singolo puntatore sarebbe sufficiente per aggiungere un nuovo nodo, perché molte implementazioni si basano su doppi puntatori?

C’è qualche caso in cui un singolo puntatore non funziona, quindi dobbiamo usare un doppio puntatore?

Alcune implementazioni passano un puntatore al parametro pointer per consentire di cambiare direttamente il puntatore head invece di restituire quello nuovo. Quindi potresti scrivere:

 // 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); 

L’implementazione che non richiede un puntatore al puntatore testa deve restituire il nuovo capo e il chiamante è responsabile dell’aggiornamento stesso:

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

Se non si esegue questo compito quando si chiama questa funzione, si perde i nodes allocati con malloc e il puntatore testa punta sempre allo stesso nodo.

Il vantaggio dovrebbe essere chiaro ora: con il secondo, se il chiamante dimentica di assegnare il nodo restituito al puntatore principale, accadranno cose brutte.

Nel tuo particolare esempio non è necessario il doppio puntatore. Tuttavia può essere necessario, se, ad esempio, dovessi fare qualcosa del genere:

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

Prendiamo questo semplice esempio:

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

Produzione:

 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 

abbiamo questa firma per my_func:

 void my_func(int *p); 

Se guardi l’output, alla fine, il valore a cui punta h è ancora 22 e il valore di h è lo stesso, anche se in my_func è stato modificato. Come mai ?

Bene, in my_func stiamo manipolando il valore di p, che è solo un puntatore locale. dopo aver chiamato:

 my_func(ht); 

in main (), p conterrà il valore che h detiene, che rappresenta l’indirizzo della variabile z, dichiarato nella funzione principale.

In my_func (), quando stiamo cambiando il valore di p per contenere il valore di z, che è un puntatore a una posizione in memoria, per la quale abbiamo assegnato spazio, non stiamo cambiando il valore di h, che abbiamo passato, ma solo il valore del puntatore locale p. Fondamentalmente, p non mantiene più il valore di h, terrà l’indirizzo di una posizione di memoria, a cui punta z.

Ora, se cambiamo un po ‘il nostro esempio:

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

abbiamo l’output seguente:

 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 

Ora, in realtà abbiamo cambiato il valore che h detiene, da my_func, in questo modo:

  1. ha cambiato la firma della funzione
  2. chiamando da main (): my_func (& h); Fondamentalmente stiamo passando l’indirizzo del puntatore h al doppio puntatore p, dichiarato come parametro nella firma della funzione.
  3. in my_func () stiamo facendo: * p = z; stiamo dereferenziando il doppio puntatore p, un livello. Fondamentalmente questo è stato tradotto come si farebbe: h = z;

Il valore di p, ora contiene l’indirizzo del puntatore h. h il puntatore contiene l’indirizzo di z.

Puoi prendere entrambi gli esempi e differirli. Quindi, tornando alla tua domanda, hai bisogno di un doppio puntatore per apportare modifiche al puntatore che hai passato direttamente da quella funzione.

Come @R. Martinho Fernandes ha sottolineato nella sua risposta , utilizzando il puntatore al puntatore come argomento nella void push(struct node** head, int data) consente di modificare il puntatore head direttamente dalla funzione push invece di restituire il nuovo puntatore.

C’è ancora un altro buon esempio che mostra il motivo per cui usando il puntatore al puntatore invece un singolo puntatore può abbreviare, semplificare e velocizzare il codice. Hai chiesto di aggiungere un nuovo nodo all’elenco che, in genere, non ha bisogno del puntatore al puntatore, in contrasto con la rimozione del nodo dalla lista collegata singolarmente. È ansible implementare la rimozione del nodo dall’elenco senza puntatore al puntatore, ma non è ottimale. Ho descritto i dettagli qui . Ti consiglio anche di guardare questo video di YouTube che risolve il problema.

BTW: Se conti con l’ opinione di Linus Torvalds , dovresti imparare a usare il puntatore al puntatore. 😉

Linus Torvalds: (…) All’estremo opposto dello spettro, vorrei davvero che più persone capissero il vero tipo di codifica di basso livello. Cose non grandi e complesse come la ricerca del nome senza blocco, ma semplicemente buon uso di puntatori-puntatori, ecc. Ad esempio, ho visto troppe persone che cancellano una voce di elenco collegata singolarmente tenendo traccia della voce “prev” e quindi per eliminare la voce, facendo qualcosa di simile

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

e ogni volta che vedo un codice del genere, vado semplicemente “Questa persona non capisce i puntatori”. Ed è purtroppo abbastanza comune.

Le persone che comprendono i puntatori utilizzano semplicemente un “puntatore al puntatore di voce” e inizializzano quello con l’indirizzo di list_head. E poi mentre attraversano la lista, possono rimuovere la voce senza usare alcun condizionale, semplicemente facendo “* pp = entry-> next”. (…)


Altre risorse che potrebbero essere utili:

  • C doppi puntatori
  • Puntatori a puntatori
  • Perché usare il doppio puntatore? o Perché utilizzare i puntatori ai puntatori?

Anche se le risposte precedenti sono abbastanza buone, penso che sia molto più facile pensare in termini di “copia per valore”.

Quando si passa un puntatore a una funzione, il valore dell’indirizzo viene copiato sul parametro della funzione. A causa dell’ambito della funzione, quella copia svanirà quando ritorna.

Usando un doppio puntatore, sarai in grado di aggiornare il valore del puntatore originale. Il doppio puntatore verrà comunque copiato dal valore, ma non importa. Tutto quello che ti interessa è modificare il puntatore originale, ignorando così l’ambito o lo stack della funzione.

Spero che questo risponda non solo alla tua domanda, ma anche ad altre domande relative ai puntatori.

La risposta è più ovvia se si prende il tempo di scrivere una funzione di inserimento del nodo funzionante; il tuo non è uno

Devi essere in grado di scrivere sopra la testa per spostarlo in avanti, quindi hai bisogno di un puntatore al puntatore alla testa in modo da poterlo ritrasmettere per ottenere il puntatore alla testa e cambiarlo.

Immagina un caso in cui devi apportare determinate modifiche e tali modifiche dovrebbero riflettere la funzione di chiamata.

Esempio:

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

Allo stesso modo passiamo l’indirizzo di memoria del capo della lista.

In questo modo, se viene aggiunto un nodo e viene modificato il valore della testa, la modifica Riflette indietro e non è necessario ripristinare manualmente la testa all’interno della funzione di chiamata.

Quindi questo approccio riduce le possibilità di perdite di memoria come avremmo perso il puntatore al nuovo nodo assegnato, se ci fossimo dimenticati di aggiornare il capo indietro nella funzione di chiamata.

Accanto a questo, il secondo codice lavorerà più velocemente poiché non si perde tempo a copiare e tornare dal momento che lavoriamo direttamente con la memoria.

Osservazione e individuazione, PERCHÉ …

Ho deciso di fare alcuni esperimenti e fare qualche conclusione,

OSSERVAZIONE 1- Se l’elenco collegato non è vuoto, possiamo aggiungere i nodes (ovviamente alla fine) usando solo un puntatore.

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

È semplice da spiegare (base). Abbiamo un puntatore nella nostra funzione principale che punta al primo nodo (root) della lista. Nella funzione insert() passiamo l’indirizzo del nodo root e usando questo indirizzo raggiungiamo la fine dell’elenco e aggiungiamo un nodo ad esso. Quindi possiamo concludere che se abbiamo un indirizzo di una variabile in una funzione (non la funzione principale) possiamo fare cambiamenti permanenti nel valore di quella variabile da quella funzione che si rifletterebbe nella funzione principale.

OSSERVAZIONE 2- Il suddetto metodo di aggiunta del nodo non è riuscito quando l’elenco era vuoto.

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

Se continui ad aggiungere elementi e infine a visualizzare l’elenco, scoprirai che l’elenco non ha subito modifiche e rimane vuoto. La domanda che mi ha colpito in questo caso è che stiamo passando l’indirizzo del nodo radice, quindi perché le modifiche non stanno avvenendo come modifiche permanenti e l’elenco nella funzione principale non subisce modifiche. PERCHÉ? PERCHÉ? PERCHÉ?

Poi ho osservato una cosa, quando scrivo A=NULL l’indirizzo di A diventa 0. Ciò significa che ora A non punta a nessuna posizione nella memoria. Così ho rimosso la riga A=NULL; e fatto alcune modifiche nella funzione di inserimento.

alcune modifiche, (sotto la funzione insert() ansible aggiungere solo un elemento a una lista vuota, è sufficiente scrivere questa funzione a scopo di test)

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

anche il metodo precedente fallisce perché nella funzione insert() root memorizza lo stesso indirizzo di A nella funzione main() ma dopo la riga root= (struct LinkedList *)malloc(sizeof(struct LinkedList)); l’indirizzo memorizzato nelle modifiche root . Così ora, root (nella funzione insert() ) e A (nella funzione main() ) memorizzano indirizzi diversi.

Quindi il programma finale corretto sarebbe,

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

Ma non vogliamo due funzioni diverse per l’inserimento, una quando l’elenco è vuoto e altro quando l’elenco non è vuoto. Ora arriva il doppio puntatore che semplifica le cose.

Una cosa che ho notato che è importante è che i pointers memorizzano l’indirizzo e quando vengono usati con ‘*’ danno valore a quell’indirizzo ma gli stessi puntatori hanno il loro indirizzo.

Ora ecco il programma completo e in seguito spieghiamo i concetti.

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

di seguito sono le osservazioni,

1. root memorizza l’indirizzo del puntatore A (&A) , *root memorizza l’indirizzo memorizzato dal puntatore A e **root memorizza il valore all’indirizzo memorizzato da A Nella lingua semplice root=&A , *root= A e **root= *A

2. se scriviamo *root= 1528 allora significa che il valore all’indirizzo memorizzato in root diventa 1528 e poiché l’indirizzo memorizzato in root è l’indirizzo del puntatore A (&A) quindi ora A=1528 (cioè l’indirizzo memorizzato in A è 1528) e questo cambiamento è permanente.

ogni volta che cambiamo il valore di *root stiamo effettivamente cambiando il valore all’indirizzo memorizzato in root e poiché root=&A (indirizzo del puntatore A ) stiamo modificando indirettamente il valore di A o l’indirizzo memorizzato in A

così ora se A=NULL (la lista è vuota) *root=NULL , quindi creiamo il primo nodo e memorizziamo il suo indirizzo in *root ovvero indirettamente memorizziamo l’indirizzo del primo nodo in A Se la lista non è vuota, tutto è uguale a quello fatto nelle precedenti funzioni usando un singolo puntatore, tranne che abbiamo cambiato root in *root poiché ciò che è stato memorizzato in root ora è memorizzato in *root .

Quando passiamo il puntatore come parametro in una funzione e vogliamo aggiornare nello stesso puntatore, usiamo il doppio puntatore.

D’altra parte, se passiamo il puntatore come parametro in una funzione e lo prendiamo in un puntatore singolo, dovremo restituire il risultato alla funzione di chiamata per poter utilizzare il risultato.

Pensa alla posizione della memoria per la testa come [HEAD_DATA].

Ora nel secondo scenario, la testa principale della funzione chiamante è il puntatore a questa posizione.

main_head —> [HEAD_DATA]

Nel tuo codice, ha inviato il valore del puntatore main_head alla funzione (cioè l’indirizzo della posizione di memoria di head_data). L’hai copiato in local_head nella funzione. così ora

local_head —> [HEAD_DATA]

e

main_head —> [HEAD_DATA]

Entrambi puntano alla stessa posizione ma sono essenzialmente indipendenti l’uno dall’altro. Quindi quando scrivi local_head = newnode; quello che hai fatto è

local_head – / -> [HEAD_DATA]

local_head —–> [NEWNODE_DATA]

Hai semplicemente sostituito l’indirizzo di memoria della memoria precedente con uno nuovo nel puntatore locale. Il main_head (puntatore) punta ancora al vecchio [HEAD_DATA]

Penso che il punto sia che rende più semplice aggiornare i nodes all’interno di un elenco collegato. Dove normalmente dovresti tenere traccia di un puntatore per il precedente e il corrente, puoi avere un doppio puntatore e occuparti di tutto.

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

Il modo standard per gestire gli elenchi collegati in C è che le funzioni push e pop aggiornino automaticamente il puntatore testa.

C è “Call by value”, ovvero le copie dei parametri vengono trasferite nelle funzioni. Se si passa solo il puntatore testa, qualsiasi aggiornamento locale apportato a quel puntatore non verrà visualizzato dal chiamante. I due workaround sono

1) Passa l’indirizzo del puntatore testa. (Puntatore a puntatore)

2) Restituisce un nuovo puntatore testa e si affida al chiamante per aggiornare il puntatore testa.

L’opzione 1) è la più semplice anche se un po ‘di confusione all’inizio.

Diciamo che ho annotato il tuo indirizzo di casa su una carta-1. Ora se voglio dire il tuo indirizzo di casa a qualcun altro, posso copiare l’indirizzo dalla card-1 alla card-2 e dare la card-2 O posso dare direttamente la card-1. In entrambi i casi, la persona conoscerà l’indirizzo e potrà raggiungerti. Ma quando do la carta-1 direttamente, l’indirizzo può essere cambiato sulla carta-1, ma se ho dato la carta-2 solo l’indirizzo sulla carta-2 può essere cambiato ma non sulla carta-1.

Passare un puntatore al puntatore è simile a dare direttamente l’accesso alla carta-1. Passare un puntatore è simile alla creazione di una nuova copia dell’indirizzo.