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

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

优点现在应该很清楚了:第二个，如果调用者忘记将返回的节点分配给头指针，就会发生不好的事情。

编辑:

指向指针的指针(双指针)还允许在同一程序中创建多个用户定义的数据类型(示例:创建 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 %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);