为什么我们要在front/back中使用双指针添加节点，而不是在中间？

Question

我有在最前面创建新节点的代码：

void push(struct Node** head_ref, int new_data)
{
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
   
    new_node->data  = new_data;
   
    new_node->next = (*head_ref);
   
    (*head_ref)    = new_node;
}

我有这段代码可以创建一个接一个的新节点：

void insertAfter(struct Node* prev_node, int new_data) 
{ 
    if (prev_node == NULL) 
    { 
       printf("the given previous node cannot be NULL");     
       return; 
    } 
          
    struct Node* new_node =(struct Node*) malloc(sizeof(struct Node)); 
  
    new_node->data = new_data; 
  
    new_node->next = prev_node->next; 
  
    prev_node->next = new_node; 
}

我明白如果我们传递一个指针a.k.a。 head 在第一种情况下，更改只会在 push 函数中生效，而不是整个程序。这就是为什么我们使用对 head 的引用来更改它指向的内容。

不过，在第二种情况下，我们传递了一个指针。我只是不明白为什么当我们不使用对前一个节点的引用时，即使我们正在更改 next 以指向新节点，代码仍然有效。

这些更改不应该只保留在 insertAfter 函数中吗？

Answer 1

对这两种情况的解释在于，指针与 C 中的任何其他变量一样，是按值传递的。

当您更改作为参数传递的指针的值时，在函数内，您需要传递指向该指针的指针，因为您将更改指针本身。

如果你想改变它指向的变量的值，你可以传递一个指针的副本。它仍然有效，因为您将更改存储在该指针中的地址中的值，地址的副本就可以了。

示例：

void func(int *ptr)
{
    static int a = 20;
    *ptr = 10; // changing the value stored in the address pointed by ptr
    ptr = &a;  // changing ptr itself, (spoiler, won't reflect in the original)
}

int main()
{
    int var;
    int *ptr = &var;

    func(ptr);
    printf("%d", *ptr);
}

你会看到 ptr 指向的变量仍然是 var，而不是 a，输出将是 10，因为，再次，您可以更改指针指向的变量的值。

而如果您将指针传递给指针：

void func(int **ptr)
{
    static int a;
    *ptr = &a;  // changing the value of the pointer
    **ptr = 20; // changing the value of the variable stored int the address stored in ptr
}

int main()
{
    int var = 10;
    int *ptr = &var;
  
    func(&ptr);
    printf("%d", *ptr);
}

现在 ptr 将指向 a，而不是 var，输出将是 20，我们可以同时更改指针值和存储在指针中的地址中的值。

Answer 2

在第一种情况下，您正在修改指针指向的内容head_ref。

在第二种情况下，您正在修改指针prev_node指向的内容。（A->B 表示 (*A).B）

这两个函数都指向应该修改的内容和修改所指向的内容。

Answer 3

在第一个函数中

void push(struct Node** head_ref, int new_data)
{
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
   
    new_node->data  = new_data;
   
    new_node->next = (*head_ref);
   
    (*head_ref)    = new_node;
}

将指针本身更改为头节点。所以函数需要处理原始指针而不是其值的副本。

因此您需要通过引用将指针传递给头节点。

在 C 中，按引用传递意味着通过指向对象的指针间接传递对象。在这种情况下，像函数的这条语句中那样取消引用指针

    (*head_ref)    = new_node;

该函数可以直接访问原始传递的对象。

在第二个函数中

void insertAfter(struct Node* prev_node, int new_data) 
{ 
    if (prev_node == NULL) 
    { 
       printf("the given previous node cannot be NULL");     
       return; 
    } 
          
    struct Node* new_node =(struct Node*) malloc(sizeof(struct Node)); 
  
    new_node->data = new_data; 
  
    new_node->next = prev_node->next; 
  
    prev_node->next = new_node; 
}

指针 prev_node 本身没有被改变。正在更改的是指针指向的节点。所以不需要通过引用将原始指针传递给函数。另一方面，指针 prev_node 指向的节点由于指针的原因通过引用传递。并使用指针可以更改指向节点的数据成员。

为什么我们要在front/back中使用双指针添加节点，而不是在中间？

Why should we use double pointer for adding node in front/back, but not in the middle?

c

pointers

pass-by-reference

singly-linked-list

function-definition