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

Question

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

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

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

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

Answer 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分配的节点,并且头指针将始终指向同一节点.

现在的优势应该很明显:第二种,如果调用者忘记将返回的节点分配给头指针,那么就会发生不好的事情.

Answer 2

在您的特定示例中，不需要双指针。但是，如果您要执行以下操作，则可能需要它：

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

Answer 3

作为@R。Martinho Fernandes在他的回答中指出，使用指向指针的指针作为参数void push(struct node** head, int data)允许您head直接从push函数内部更改指针，而不是返回新指针。

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

顺便说一句：如果你用Linus Torvalds 的 意见来计算，你最好学习如何使用指针到指针。;-)

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

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

每当我看到这样的代码时，我就会说“这个人不懂指针”。可悲的是，这很常见。

了解指针的人只使用“指向入口指针的指针”，并使用 list_head 的地址对其进行初始化。然后当他们遍历列表时，他们可以在不使用任何条件的情况下删除条目，只需执行“*pp = entry->next”即可。（……）

其他可能有用的资源：

• C 双指针
• 指向指针的指针
• 为什么要使用双指针？或者为什么使用指向指针的指针？

Answer 4

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

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

通过使用双指针，您将能够更新原始指针的值。双指针仍将按值复制，但这没关系。您真正关心的只是修改原始指针，从而绕过函数的作用域或堆栈。

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