下面的两个代码示例都在链表的顶部添加一个节点。但是，第一个代码示例使用双指针，而第二个代码示例使用单个指针
代码示例 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);
不采用指向 head 指针的指针的实现必须返回新的 head，调用方负责更新它本身：
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 分配的节点，并且头部指针将始终指向同一节点。
现在的优势应该很明显：对于第二个，如果调用者忘记将返回的节点分配给头指针，就会发生不好的事情。
编辑：
指针到指针(双指针(还允许在同一程序中创建多个用户定义的数据类型(例如：创建 2 个链表(
为了避免双指针的复杂性，我们始终可以使用结构(用作内部指针(。
您可以通过以下方式定义列表：
typedef struct list {
struct node* root;
} List;
List* create() {
List* templ = malloc(sizeof(List));
templ->root = NULL;
return templ;
}
在链接列表函数中，按以下方式使用上述列表：(推送函数的示例(
void Push(List* l, int x) {
struct node* n = malloc(sizeof(struct node));
n->data = x;
n->link = NULL;
printf("Node created with value %dn", 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;
}
}
在你的main((函数中，以如下方式声明列表：
List* list1 = create();
push(list1, 10);
虽然前面的答案已经足够好了，但我认为从"按值复制"的角度思考要容易得多。
传入指向函数的指针时，地址值将复制到函数参数。由于函数的作用域，该副本一旦返回就会消失。
通过使用双指针，您将能够更新原始指针的值。双指针仍将按值复制，但这并不重要。您真正关心的是修改原始指针，从而绕过函数的作用域或堆栈。
希望这不仅回答了您的问题，还回答了其他与指针相关的问题。
正如@R. Martinho Fernandes在他的回答中指出的那样，在void push(struct node** head, int data)中使用指针到指针作为参数允许您直接从函数内部更改head指针push而不是返回新指针。
还有另一个很好的例子说明了为什么使用指针到指针而不是单个指针可以缩短、简化和加快代码。您询问了向列表中添加新节点的问题，与从单向链表中删除节点相比，该节点通常不需要指针指向指针。您可以在没有指针指向指针的情况下实现从列表中删除节点，但它是次优的。我在这里描述了细节。我建议您也观看此YouTube视频，该视频解决了该问题。
顺便说一句：如果你用Linus Torvalds的观点来计算，你最好学习如何使用指针到指针。
莱纳斯·托瓦兹： (...在光谱的另一端，我实际上希望更多的人理解真正核心的低级编码。不是大而复杂的东西，如无锁名称查找，但只是很好地使用指针到指针等。例如，我见过太多人通过跟踪"prev"条目来删除单链表条目，然后删除该条目，执行类似操作
if (prev) prev->next = entry->next; else list_head = entry->next;每当我看到这样的代码时，我都会说"这个人不理解指针"。可悲的是，这很常见。
理解指针的人只是使用"指向入口指针的指针"，并使用list_head的地址对其进行初始化。然后，当他们遍历列表时，他们可以在不使用任何条件的情况下删除条目，只需执行"*pp = entry->next"。(...)
其他可能有帮助的资源：
- C 双指针 指针
- 到指针 为什么要使用双指针？
- 或者为什么使用指向指针的指针？
在您的特定示例中，不需要双指针。但是，例如，如果您要执行以下操作，则可能需要它：
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;
}
观察和发现，* 为什么...
我决定做一些实验并得出一些结论，
观察 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 insertedn"; cin>>m;
insert(A,m);
return 0;
}
解释起来很简单(基本(。我们在 main 函数中有一个指针，它指向列表的第一个节点(根(。在insert()函数中，我们传递根节点的地址，并使用此地址到达列表末尾并向其添加一个节点。因此，我们可以得出结论，如果我们在一个函数(不是主函数(中有变量的地址，我们可以对该函数的值进行永久性更改，这将反映在主函数中。
**观察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 insertedn";
cin>>m;
insert(A,m);
return 0;
}
如果您继续添加元素并最终显示列表，那么您会发现列表没有发生任何更改，并且仍然是空的。
我想到的问题是，在这种情况下，我们也传递了根节点的地址，那么为什么修改不会作为永久修改发生，并且主函数中的列表没有发生任何变化。为什么？为什么？为什么？
然后我观察到一件事，当我写A=NULL时，A的地址变成了 0。这意味着现在A不会指向内存中的任何位置。所以我删除了行A=NULL;，并对插入功能进行了一些修改。
一些修改(下面的insert()函数只能将一个元素添加到空列表中，只是出于测试目的编写了这个函数(：
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 insertedn";
cin>>m;
insert(A,m);
return 0;
}
上述方法也失败了，因为在insert()函数中，根存储的地址与main()函数中的A相同，但在行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 insertedn";
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 insertedn";
cin>>n;
while(n--){
cin>>m;
insert(&A,m);
}
display(A);
return 0;
}
以下是观察结果，
1. 根存储指针 A (&A)的地址，*root存储指针 A 存储的地址，**root存储A存储的地址的值。在简单的语言root=&A中，*root= A和**root= *A。
2. 如果我们写*root= 1528那么这意味着存储在 root 中的地址的值变为 1528，并且由于存储在 root 中的地址是指针 A 的地址，因此现在A=1528 (&A)(即存储在 A 中的地址是 1528(，并且此更改是永久性的。
每当我们改变*root的值时，我们确实在改变存储在root中的地址的值，并且由于root=&A(指针A的地址(，我们间接地改变了A的值或存储在A中的地址。
所以现在如果A=NULL(列表为空(*root=NULL，那么我们创建第一个节点并将其地址存储在*root即间接地将第一个节点的地址存储在A。如果 list 不为空，则一切都与以前使用单个指针的函数中所做的相同，只是我们已将 root 更改为 *root，因为存储在 root 中的内容现在存储在 *root 中。
像 [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]
您只需在本地指针中将先前内存的内存地址替换为新内存地址即可。main_head(指针(仍然指向旧的 [HEAD_DATA]
在 C 语言中处理链表的标准方法是让 push 和 pop 函数自动更新头部指针。
C 是"按值调用"，这意味着参数的副本被传递到函数中。如果只传入 head 指针，则调用方不会看到对该指针所做的任何本地更新。两种解决方法是
1( 传递头部指针的地址。(指针指向头部指针(
2( 返回一个新的头部指针，并依靠调用方来更新头部指针。
选项 1( 是最简单的，即使一开始有点混乱。
让我们举这个简单的例子：
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: %dn", *z);
printf("my_func - value of p: %pn", 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 zn");
printf("my_func - addr of z %pn", &*z);
printf("my_func - value of p %pn", p);
printf("my_func - value of what p points to: %dn", *p);
free(z);
}
int main(int argc, char *argv[])
{
// Our variable
int z = 10;
int *h = &z;
// Print the value of z
printf("main - value of z: %dn", z);
// Print the address of val
printf("main - addr of z: %pn", &z);
// Print the value of h.
printf("main - value of h: %pn", h);
// Print the value of what h points to
printf("main - value of what h points to: %dn", *h);
// Change the value of var z by dereferencing h
*h = 22;
// Print value of val
printf("main - value of z: %dn", z);
// Print value of what h points to
printf("main - value of what h points to: %dn", *h);
my_func(h);
// Print value of what h points to
printf("main - value of what h points to: %dn", *h);
// Print value of h
printf("main - value of h: %pn", 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 的值是相同的，尽管它被更改了my_func。怎么来了？
好吧，在my_func中，我们正在操纵 p 的值，它只是一个局部指针。致电后：
my_func(ht);
在 main(( 中，p 将保存 h 保存的值，该值表示在 main 函数中声明的 z 变量的地址。
在 my_func(( 中，当我们更改 p 的值以保存 z 的值时，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: %dn", *z);
printf("my_func - value of p: %pn", p);
printf("my_func - value of h: %pn", *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 zn");
printf("my_func - addr of z %pn", &*z);
printf("my_func - value of p %pn", p);
printf("my_func - value of h %pn", *p);
printf("my_func - value of what p points to: %dn", **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 variable
int z = 10;
int *h = &z;
// Print value of z
printf("main - value of z: %dn", z);
// Print address of val
printf("main - addr of z: %pn", &z);
// Print value of h.
printf("main - value of h: %pn", h);
// Print value of what h points to
printf("main - value of what h points to: %dn", *h);
// Change the value of var z by dereferencing h
*h = 22;
// Print value of val
printf("main - value of z: %dn", z);
// Print value of what h points to
printf("main - value of what h points to: %dn", *h);
my_func(&h);
// Print value of what h points to
printf("main - value of what h points to: %dn", *h);
// Print value of h
printf("main - value of h: %pn", 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
现在，我们实际上已经通过这样做改变了 h 从 my_func 中保存的值：
- 更改了函数签名
- 从主((： my_func(&h(;基本上，我们将 h 指针的地址传递给双指针 p，在函数签名中声明为参数。
- 在 my_func(( 中，我们正在做：*p = z;我们正在取消引用双指针 p，一个级别。基本上，这被翻译为你会做的：h = z;
，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);
}
类似地，我们传递列表头部的内存地址。
这样，如果添加了任何节点并且 Head 的值发生了变化，则该更改将反射回来，我们不必在调用函数内部手动重置 Head。
因此，这种方法减少了内存泄漏的机会，因为如果我们忘记在调用函数中更新 Head，我们将丢失指向新分配节点的指针。
除此之外，第二个代码将更快地工作，因为我们直接使用内存，因此不会浪费时间在复制和返回上。
关键是它使更新链表中的节点变得更加容易。您通常必须跟踪以前和当前的指针，您可以让双指针来处理这一切。
#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;
}
}
};
您的困惑可能来自两个函数都有一个名为 head 的参数这一事实。这两个head实际上是不同的东西。 head在第一个代码中存储头节点指针的地址(它本身存储头节点结构的地址(。而第二个head直接存储头节点结构的地址。而且由于这两个函数都返回新创建的节点(应该是新头(，我认为没有必要采用第一种方法。此函数的调用方负责更新他们拥有的头引用。我认为第二个足够好，看起来很简单。我会选择第二个。
命名约定 - Head 是造成混淆的原因。
头是尾巴，尾巴是头。尾巴摇头。
头部只是一个指针，数据为空 - 尾部只是数据，指针为空。
因此，您有一个指向结构指针的指针。 结构指针指向链表中的第一个节点结构。此指向第一个结构节点指针的指针称为 Head。它最好称为startptr或headptr。
当你抓住了startptr时，你就抓住了链表。 然后，您可以遍历所有结构节点。
假设我在卡片-1上记下了您的住址。现在，如果我想把你的住址告诉别人，我可以把地址从卡-1复制到卡-2，然后给卡-2，或者我可以直接给卡-1。无论哪种方式，此人都会知道地址并可以与您联系。但是当我直接给卡-1时，卡-1上的地址可以更改，但是如果我给卡-2，则只能更改卡-2上的地址，而不能更改卡-1上的地址。
将指针传递到指针类似于直接授予对 card-1 的访问权限。传递指针类似于创建地址的新副本。
当我们将指针作为函数中的参数传递并希望在同一指针中更新时，我们使用双指针。
另一方面，如果我们在函数中将指针作为参数传递并在单个指针中捕获它，则必须将结果返回给调用函数才能使用结果。