在链表中添加节点时使用双指针的原因是什么？
下面的两个代码示例都在链表顶部添加一个节点。 但是，第一个代码示例使用双指针，而第二个代码示例使用单个指针
代码示例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); 代码示例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)
两种策略都有效。 但是，很多使用链表的程序使用双指针来添加新节点。 我知道双指针是什么。 但是，如果单个指针就足以添加一个新节点，为什么很多实现依赖于双指针呢？
有没有一个单一的指针不工作的情况下，所以我们需要去一个双指针？
有些实现将指针指向指针参数，以允许直接改变头指针，而不是返回新的头指针。 因此你可以写：
// 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);
不带指针指向头指针的实现必须返回新头，调用者负责自己更新它：
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);
如果在调用这个函数的时候你没有做这个任务，那么你将会使用malloc来分配节点，并且头指针总是指向同一个节点。
现在的优势应该是清楚的：第二，如果调用者忘记将返回的节点分配给头指针，则会发生不好的事情。
在你的例子中，不需要双指针。 但是，如果您要做这样的事情，那么可能需要这样做：
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; }
让我们来看看这个简单的例子：
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; }
输出：
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
我们有这个签名my_func：
void my_func(int *p);
如果你看看输出结果，那么h指向的值仍然是22，而h的值是相同的，尽pipe在my_func中它被改变了。 怎么来的 ？
那么，在my_func中，我们正在操纵p的值，这只是一个本地指针。 打电话后：
my_func(ht);
在main（）中，p将保存h所保持的值，它表示在main函数中声明的zvariables的地址。
在my_func（）中，当我们改变p的值来保存z的值，这是一个指向内存中一个位置的指针，我们已经为其分配了空间，我们并没有改变h的值，传入，但只是本地指针p的值。 基本上，p不再保持h的值，它将保存z指向的内存位置的地址。
现在，如果我们稍微改变我们的例子：
#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; }
我们有以下的输出：
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
现在，我们通过这样做，实际上已经从my_func改变了h的值：
- 改变了function签名
- 从main（）调用：my_func（＆h）; 基本上我们将h指针的地址传递给double指针p，声明为函数签名中的一个参数。
- 在my_func（）中我们正在做：* p = z; 我们正在引用双指针p，一个级别。 基本上这是翻译，你会这样做：h = z;
p的值现在保存着h指针的地址。 h指针保存z的地址。
你可以把这两个例子和差异。 所以，回到你的问题，你需要双指针，以修改你直接从该函数传入的指针。
如果花时间写一个工作节点插入函数，答案会更加明显; 你不是一个。
你需要能够在头上写下来移动它，所以你需要一个指针指向头的指针，所以你可以取消引用它来获取头的指针并改变它。
想象一下，你必须做一些改变，这些改变应该反映在调用函数中。
例：
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); }
同样，我们传递列表头的内存地址。
这样，如果添加了任何节点并且头部的值被改变，那么改变reflection回来，并且我们不必在调用函数内部手动地重置头部。
因此，这种方法减less了内存泄漏的机会，因为我们已经丢失了指向新分配的节点的指针，忘记了在调用函数中更新头部。
除此之外，第二个代码将更快运行，因为我们直接使用内存不会浪费任何时间来复制和返回。
观察和发现，为什么…
我决定做一些实验并做出一些结论，
观察1-如果链表不是空的，那么我们可以使用一个单一的指针来添加节点（显然在最后）。
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; }
其简单的解释（基本）。 我们的主函数中有一个指向列表的第一个节点（根）的指针。 在insert()函数中，我们传递根节点的地址，使用这个地址我们到达列表的末尾并向它添加一个节点。 所以我们可以得出这样的结论：如果我们在一个函数（而不是主函数）中有一个variables的地址，那么我们就可以在该函数中对那个函数的值进行永久性的改变，这个函数将反映在主函数中。
OBSERVATION 2-当列表为空时，上述添加节点的方法失败。
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; }
如果你继续添加元素，并最终显示列表，那么你会发现列表已经没有变化，仍然是空的。 在这种情况下，我想到的问题也是我们传递根节点的地址，那么为什么修改不会发生，因为永久修改和主函数中的列表不会发生变化。 为什么？ 为什么？ 为什么？
然后我观察到一件事情，当我写A=NULL ， A的地址变为0.这意味着现在A不指向内存中的任何位置。 所以我删除了行A=NULL; 并对插入function做了一些修改。
一些修改，（在insert()函数下面只能添加一个元素到一个空的列表中，只是为了testing目的而写这个函数）
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; }
上面的方法也失败了，因为在insert()函数中，root用户在main()函数中存储了与A相同的地址，但是在该行的root= (struct LinkedList *)malloc(sizeof(struct LinkedList));后面存放着相同的地址root= (struct LinkedList *)malloc(sizeof(struct LinkedList)); 存储在root的地址发生变化。 因此，现在， root （在insert()函数中）和A （在main()函数中）存储不同的地址。
所以正确的最终计划是，
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; }
但是我们不希望插入两个不同的函数，一个是列表是空的，另一个是列表不是空的。 现在来了双指针，使事情变得简单。
有一件事我注意到了，重要的是指针存储地址，当和'*'一起使用时，地址赋值，而指针本身有自己的地址。
现在这里是完整的程序，稍后解释这些概念。
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; }
以下是观察，
1. root存储指针A (&A)的地址， *root存储指针A存储的地址， **root存储A存储的地址的值。 用简单的语言root=&A ， *root= A和**root= *A
2.如果我们写*root= 1528则意味着存储在root中的地址的值变为1528，并且因为存储在root中的地址是指针A (&A)的地址，所以现在A=1528 （即，存储在A地址是1528）而这种变化是永久的。
每当我们改变*root值时，我们确实改变了存储在root中的地址的值，并且由于root=&A （指针A地址），我们间接地改变A存储的值或地址的值。
所以现在如果A=NULL （list是空的） *root=NULL ，那么我们创build第一个节点并将它的地址存储在*root即间接地将第一个节点的地址存储在A 。 如果列表不是空的，除了我们已经将根改为*root以外，所有内容都与前面使用单个指针的函数完全相同，因为存储在根中的内容现在存储在*root 。
当我们将指针作为parameter passing给一个函数，并且希望在同一个指针中更新时，我们使用双指针。
另一方面，如果我们将指针作为parameter passing给函数，并将其捕获到单个指针中，则必须将结果返回给调用函数以便使用结果。
考虑头像[HEAD_DATA]的内存位置。
现在在第二种情况下，调用函数的main_head是指向这个位置的指针。
main_head —> [HEAD_DATA]
在你的代码中，它将指针main_head的值发送给函数（即head_data的存储单元的地址），将它复制到函数中的local_head。 所以现在
local_head —> [HEAD_DATA]
和
main_head —> [HEAD_DATA]
两者都指向相同的位置，但基本上彼此独立。 所以当你写local_head = newnode; 你做了什么
local_head – / – > [HEAD_DATA]
local_head —–> [NEWNODE_DATA]
您只需用本地指针中的新内存replace之前内存的内存地址即可。 main_head（指针）仍然指向旧的[HEAD_DATA]
我认为重点是它可以更容易地更新链接列表中的节点。 你通常必须跟踪前一个和当前的指针，你可以有一个双指针来处理这一切。
#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; } } };
