了解在C中使用双指针创建单链表的代码

Question

我试图了解下面创建单链表的代码是如何使用双指针工作的。

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

void push(struct Node** headRef, int data) {

    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;   
    newNode->next = *headRef;
    *headRef = newNode;
}

//Function to implement linked list from a given set of keys using local references
struct Node* constructList(int keys[], int n) {
    struct Node *head = NULL; 
    struct Node **lastPtrRef = &head; 
    int i, j;
    for(i = 0; i < n; i++) {
        push(lastPtrRef, keys[i]);
        lastPtrRef = &((*lastPtrRef)->next); //this line
        if((*lastPtrRef) == NULL) {
            printf("YES\n");
        }
    }

    return head;
}

int main() {
    int keys[] = {1, 2, 3, 4};
    int n = sizeof(keys)/sizeof(keys[0]);

    //points to the head node of the linked list
    struct Node* head = NULL;

    head = constructList(keys, n); //construct the linked list

    struct Node *temp = head;

    while(temp != NULL) { //print the linked list
        printf(" %d -> ", temp->data);
        temp = temp->next;
    }
}

我理解在函数push（）中使用双指针的目的，它允许您更改指针headRef在函数中指向的内容。但是，在函数constructList（）中，我不理解以下行是如何工作的：

lastPtrRef = &((*lastPtrRef)->next);

最初lastPtrRef将指向指向NULL的head。在对推送（）的第一次调用中，在构造列表（）中的for循环中，head指向的值发生了变化（它指向包含值1的新节点）。因此，在第一次调用推送（）之后，lastPtrRef将指向指向值为1的节点的head。但是，之后执行以下行：

最后PtrRef=

其中lastPtrRef被赋予新添加节点的下一个成员指向的任何内容的地址。在这种情况下，头-

我真的不知道调用push（）后更改lastprref的目的是什么。如果要构建链表，难道不希望lastprref具有指向包含1的节点的指针的地址，因为要将下一个节点（将包含2）推到列表的头部（即1）？

在constructList中for循环中对push（）的第二次调用中，我们将传入指向head的lastprref-

也许我对代码的理解是错误的，但通过更改lastprref指向的内容，似乎忽略了包含1的节点。如果我们更改lastprref的地址，我看不出链表是如何创建的。

如果您能深入了解此代码的工作原理，我将不胜感激。非常感谢。

Answer 1

这使用了一种称为前向链接的技术，我相信您已经理解了这一点（使用指向链接列表构造的前向链接的指针）。

这个实现之所以让人困惑，是因为推送函数似乎是为了将项目填充到列表的开头，但在本例中，它将项目填充到了列表的尾部。那么它是如何做到的呢？

重要的是要理解推送中这句看似微不足道的小语句：

newNode->next = *headRef

这似乎并不重要，但我向你保证这很重要。在这种情况下，push函数对该函数的实际功能造成了严重的不公正。实际上，它更像是一种通用的插入。关于该函数的一些事实

• 它接受一个指向指针headRef的指针作为参数，以及一些要放入正在管理的链表中的数据
• 在分配一个新节点并在其中保存数据后，它将新节点的下一个指针设置为当前存储在取消引用的headRef中的任何值（so..指针），这就是我上面提到的行所实现的
• 然后，它将新节点的地址存储在刚刚从中提取之前地址的相同位置；i、 e.头枕
• 有趣的是，它没有返回值（它是void），这让人更加困惑。事实证明它不需要

返回调用者后，起初似乎什么都没有改变。lastPtrRef仍然指向某个指针（实际上与以前相同的指针；它必须，因为它是按值传递给函数的）。但现在该指针指向刚刚分配的新节点。此外，该新节点的Next指针指向函数调用前*lastPtrRef中的任何内容（即函数调用前lastPtrRef指向的指针中的任何值）。

这很重要。这就是该行代码所强制执行的，这意味着如果您使用lastprref对指向NULL的指针（例如初始循环条目上的头）进行寻址来调用它，那么该指针将接收新节点，新节点的下一个指针将为NULL。如果随后更改最后插入的节点的地址，使其指向最后插入的节点的下一个指针（该指针指向NULL；我们刚刚介绍过），并重复该过程，它将在那里挂起另一个节点，将该节点的下一个指针设置为NULL等。每次迭代时，最后插入的节点的下一个指针都将被挂起，它始终为空。

这就是推送用于构建前向链表的方式。最后一个想法。如果你有这个链表，你会得到什么：

#include <stdio.h>
#include <stdlib.h>

struct Node
{
    int data;
    struct Node* next;
};

void push(struct Node** headRef, int data)
{
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = *headRef;
    *headRef = newNode;
}

int main()
{
    //points to the head node of the linked list
    struct Node* head = NULL;
    push(&head, 1);
    push(&head->next, 2);
    push(&head->next, 3);

    for (struct Node const *p = head; p; p = p->next)
        printf("%p ==> %d\n", p, p->data);
}

这个看似无辜的例子进一步说明了为什么我说推送更像是一种通用的插入。这只是填充初始头部节点。

push(&head, 1);

然后将新节点的next指针的地址作为第一个参数附加到该节点，这与您的constructList类似，但没有lastprref变量（此处不需要）：

push(&head->next, 2);

但接下来：

push(&head->next, 3);

Hmmm.与前一个调用相同的指针地址，那么它会做什么呢？提示：记住那是什么-

上述程序的输出如下（显然，实际地址值会有所不同，具体取决于您的实例和实现）：

0x100705950 ==> 1
0x10073da90 ==> 3
0x100740b90 ==> 2

希望这有帮助。