在链表中添加节点时使用双指针的原因是什么？

下面的两个代码示例都在链表的顶部添加了一个节点。 但是，第一个代码示例使用双指针，而第二个代码示例使用单指针

代码示例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)

这两种策略都有效。但是，许多使用链表的程序使用双指针来添加新节点。我知道双指是什么。但是，如果单个指针就足以添加一个新节点，那么为什么许多实现都依赖于双指针呢？

有没有一个单指针不工作的情况，所以我们需要去双指针？

87347 次浏览
小开
最佳答案

有些实现传递一个指向指针参数的指针，以允许直接更改头指针，而不是返回新的头指针。你可以这样写:

// 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 分配的节点，而 head 指针总是指向同一个节点。

优势现在应该很明显了: 对于第二种情况，如果调用者忘记将返回的节点分配给 head 指针，就会发生糟糕的事情。

编辑:

指针到指针(双指针)还允许在同一个程序中创建多个用户定义的数据类型(例如: 创建2个链表)

为了避免双指针的复杂性，我们总是可以利用结构(作为内部指针)。

您可以按以下方式定义列表:

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


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

在链接列表函数中，以下方式使用上面的列表: (例如 Push 函数)

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

在 main ()函数中，按以下方式声明列表:

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

如果您花时间编写一个工作节点插入函数，那么答案就更明显了; 您的函数不是一个工作节点插入函数。

你需要能够将 写作移动到头部上方，所以你需要一个指向头部指针的指针，这样你就可以取消引用它来得到指向头部的指针并改变它。

小开

在您的特定示例中，不需要双指针。然而，如果你要做这样的事情，它是必要的:

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

我认为问题的关键在于它使得更新链表中的节点变得更加容易。在通常情况下，你需要跟踪前面和当前的指针，你可以用一个双指针来处理这一切。

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

想象一下这样一种情况: 您必须进行某些更改，而这些更改应该反映在调用函数中。

例如:

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，我们就会丢失指向新分配节点的指针。

除此之外，第二段代码将工作得更快，因为我们直接处理内存，所以在复制和返回时不会浪费时间。

小开

观察与发现，为什么..

我决定做一些实验，得出一些结论,

意见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()函数中，我们传递根节点的地址，使用这个地址，我们到达列表的末尾并向其添加一个节点。因此，我们可以得出结论，如果我们有一个变量的地址在一个函数(而不是主函数) ，我们可以作出永久的变化，该变量的值从该函数将反映在主函数。

意见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;行，并对 insert 函数进行了一些修改。

一些修改，(下面的 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 inserted\n";
cin>>m;
insert(A,m);
return 0;
}

上面的方法也失败了，因为在 insert()函数中 root 存储的地址与 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 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或地址的值。

现在如果 A=NULL(list 为空) *root=NULL，那么我们创建第一个节点并将它的地址存储在 *root，也就是间接地将第一个节点的地址存储在 A。如果 list 不是空的，那么所有的操作都和前面的函数一样，只不过我们把 root 改成了 *root，因为之前存储在 root 中的内容现在都存储在 *root中了。

小开

让我们看看这个简单的例子:

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 的值是相同的，尽管在 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: %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 保持的值:

  1. 改变的函数签名
  2. 从 main ()调用: my _ func (& h) ; 基本上我们将 h 指针的地址传递给双指针 p，在函数的签名中声明为参数。
  3. 在 my _ func ()中，我们正在做: * p = z; 我们正在取消对双指针 p 的引用，一级。基本上可以这样翻译: h = z;

现在 p 的值包含 h 指针的地址。 h 指针包含 z 的地址。

你可以举这两个例子并且区分它们。 所以，回到你的问题，你需要双指针来修改你从那个函数直接传入的指针。

小开

当我们将指针作为函数中的参数传递，并且希望在同一个指针中更新时，我们使用双指针。

另一方面，如果我们将指针作为函数中的参数传递，并在单指针中捕获它，那么为了使用结果，必须将结果返回给调用函数。

小开

可以考虑头部的内存位置，比如[ 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 ]

小开

正如 @ R. Martinho Fernandes在 他的回答中指出的，在 void push(struct node** head, int data)中使用 指针指向指针作为参数，可以直接从 push函数中更改 head指针，而不必返回新指针。

还有另一个很好的例子，说明为什么使用 指针指向指针而不是一个单指针可以缩短，简化和加速您的代码。您询问了关于 增加的列表的一个新节点，与单链表中的节点 移除相比，这个节点通常不需要指针到指针。您可以实现从列表中删除节点而不需要指针指向，但这是次优的。我描述了细节 给你。我建议你也看看 这个 YouTube 视频，它解决了这个问题。

顺便说一句: 如果你用 莱纳斯 · 托瓦兹 意见计数，你最好学习如何使用指针到指针。 ; -)

Linus Torvalds: (...)在光谱的另一端，我实际上希望更多的人理解真正核心的低级编码。不像无锁名称查找那样庞大而复杂，只是很好地利用了指针到指针等。例如，我见过太多的人通过跟踪“ prev”条目来删除单链表条目，然后再删除条目，比如

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

每当我看到这样的代码，我就会说“这个人不懂指针”。

理解指针的人只需使用“指向入口指针的指针”，并用 list _ head 的地址初始化它。然后，当他们遍历列表时，他们可以删除条目而不使用任何条件，只需执行“ * pp = entry-> next”。(...)

其他可能有帮助的资源:

小开

虽然前面的答案已经足够好了，但是我认为从“按价值复制”的角度来考虑要容易得多。

当您传入指向函数的指针时，地址值将被复制到函数参数。由于函数的作用域，该副本一旦返回就会消失。

通过使用双指针，您将能够更新原始指针的值。双指针仍然会被值复制，但这并不重要。您真正关心的是修改原始指针，从而绕过函数的作用域或堆栈。

希望这不仅能回答你的问题，还能回答其他与指针相关的问题。

小开

在 C 中处理链表的标准方法是让 push 和 pop 函数自动更新 head 指针。

C 是“按值调用”，意思是将参数的副本传递给函数。如果只传递头指针，则调用方将看不到对该指针所做的任何本地更新。这两个变通方法是

1)传递头指针的地址。(头指针到头指针)

2)返回一个新的头指针，并依靠调用者来更新头指针。

选项1)是最简单的，即使一开始有点混乱。

小开

假设我在一张卡片上记下了你的家庭住址。如果我想把你家的地址告诉别人，我可以把地址从第一张卡复制到第二张卡，或者直接给第一张卡。不管是哪种方式，对方都会知道地址并能联系到你。但是当我直接给出卡片 -1时，地址可以在卡片 -1上改变，但是如果我给出卡片 -2，只有卡片 -2上的地址可以改变，而不能在卡片 -1上改变。

将指针传递给指针类似于直接给予卡 -1的访问权限。传递指针类似于创建地址的新副本。

小开

我认为您的困惑可能来自这样一个事实，即两个函数都有一个名为 head的参数。这两个 head实际上是不同的东西。第一个代码中的 head存储头节点指针的地址(它本身存储头节点结构的地址)。而第二个 head直接存储头节点结构的地址。由于这两个函数都返回新创建的节点(应该是新的 head) ，因此我认为没有必要使用第一种方法。此函数的调用方负责更新它们拥有的头引用。我认为第二个已经足够好了，还有 看起来很简单。我会选第二个。

小开

变数命名原则是造成混乱的原因。

头就是尾巴，尾巴就是头，尾巴摇头。

头部只是一个指针，数据为空-尾部只是数据，指针为空。

所以你有一个指向结构指针的指针。结构指针指向“链接”列表中的第一个节点结构。 这个指向第一个结构节点指针的指针叫做 Head，最好叫做 startptr 或 headptr。

当您抓住 startptr 时，您已经抓住了 linkedlist。然后您可以遍历所有的 struct 节点。


提交答案