原始头指针在 printList 函数中没有改变，但在插入节点时列表确实改变了

Question

我已经阅读了这两个 posts/answers 关于双 pointers/passing 的使用

When printing out a linked list, why is the original head pointer not changed

Linked list head double pointer passing

但有一件事仍然困扰着我。

printList 函数中的头指针（使用 head = head->next 遍历）在 main 中没有改变，因为即使我们通过引用传递它，该函数也会收到 pointer/address 的副本。我能理解。

但是为什么在插入像

这样的节点时整个列表会发生变化（更新）

struct node* addLast(struct node* head, struct node* new_node) {
    if (head == NULL)
    {
        head = new_node;
        return head;
    }

    struct node* current = head;
    while (current->next != NULL)
    {
        current = current->next;
    }

    current->next = new_node;

    return head;
}

我们在 main

中调用它

head = addLast(head, node)

我知道该原则适用于 head == NULL 的情况（因为我们 return “新”头），但如果不是，那么我们再次遍历列表并插入节点。

为什么列表会更新（不一定只在这个特定的添加函数中）？那么new_node（由另一个函数用malloc()创建的节点）不也是一个“副本”吗？

Answer 1

how come then the whole list gets changed (updated) when inserting a node?

如您所说，这里有两种情况：

I get that the principle applies to the case when head == NULL (because we return the "new" head)

确实如此。所以你的问题是关于列表不为空并且节点附加到它的其余情况。

在这种情况下，返回值与作为参数给出的指针相同：head 不变。

但是，head指向的节点有自己的next指针，那个指针可能已经从NULL变成了指向新节点的指针。因此，虽然 head 没有改变，但 next 指针链将变得更长 .

想象一下当我们从一个空列表开始时会发生什么，然后使用以下脚本向其中添加节点：

node* createNode(int value) {
    node* newNode = malloc(sizeof(node));
    newNode->value = value;
    newNode->next = NULL;
    return newNode;
}

int main() {
    node* head = NULL;
    head = addLast(head, createNode(1));
    head = addLast(head, createNode(2));
    head = addLast(head, createNode(3));
    // ...
    return 0;
}

我刚刚添加了一个函数来创建节点实例：没有惊喜（我希望！）

所以当脚本启动时，我们有 head:

head: NULL

然后我们调用createNode(1)其中returns一个指向节点的指针。我们可以用一个方框表示该节点：

┌────────────┐
│ value: 1   │
│ next: NULL │
└────────────┘

指向此节点的指针作为第二个参数传递给 addList，因此在该函数中我们有：

 new_node         head: NULL
  ↓
┌────────────┐
│ value: 1   │
│ next: NULL │
└────────────┘

正如您正确注意到的那样，此节点引用从函数 addList 返回给调用者，调用者将其分配给自己的 head 变量。所以在主程序中我们现在有这个状态：

 head
  ↓
┌────────────┐
│ value: 1   │ 
│ next: NULL │
└────────────┘

现在到第二个节点：它是用 createNode(2) 创建的，然后用这些参数调用 addList：

 head                new_node
  ↓                   ↓
┌────────────┐      ┌────────────┐
│ value: 1   │      │ value: 2   │ 
│ next: NULL │      │ next: NULL │
└────────────┘      └────────────┘

addList 然后创建另一个变量 current 以与 head:

相同的引用开始

 current
 head                new_node
  ↓                   ↓
┌────────────┐      ┌────────────┐
│ value: 1   │      │ value: 2   │ 
│ next: NULL │      │ next: NULL │
└────────────┘      └────────────┘

while循环条件不成立，所以不会迭代。然后执行 current->next = new_node，这是最重要的赋值：它在列表的 last 节点与新节点之间建立 link：

 current
 head                new_node
  ↓                   ↓
┌────────────┐      ┌────────────┐
│ value: 1   │      │ value: 2   │ 
│ next: ──────────> │ next: NULL │
└────────────┘      └────────────┘

最后，head 返回给调用者，调用者将其分配给他们的 head 变量——这实际上是一个虚拟分配，因为 head 没有改变。 did 改变的是 head 指向的 linked 列表的长度。

这应该可以解释了，但是让我们再添加一个节点：create_node(3) 传递给 addList，所以在 addList 中我们有这个状态：

 current
 head                                    new_node
  ↓                                       ↓
┌────────────┐      ┌────────────┐      ┌────────────┐
│ value: 1   │      │ value: 2   │      │ value: 3   │ 
│ next: ──────────> │ next: NULL │      │ next: NULL │
└────────────┘      └────────────┘      └────────────┘

这次while条件为真，所以current = current->next会让我们进入这个状态：

 head                current             new_node
  ↓                   ↓                   ↓
┌────────────┐      ┌────────────┐      ┌────────────┐
│ value: 1   │      │ value: 2   │      │ value: 3   │ 
│ next: ──────────> │ next: NULL │      │ next: NULL │
└────────────┘      └────────────┘      └────────────┘

然后 while 循环将退出，并且 current->next = new_node 被执行：

 head                current             new_node
  ↓                   ↓                   ↓
┌────────────┐      ┌────────────┐      ┌────────────┐
│ value: 1   │      │ value: 2   │      │ value: 3   │ 
│ next: ──────────> │ next: ──────────> │ next: NULL │
└────────────┘      └────────────┘      └────────────┘

并且 addList 通过返回（未更改的）head 指针终止。主程序再次执行对其自身 head 的赋值，即使该指针没有变化。

我希望这能澄清即使 head 不再改变，next 指针链确实改变：尾节点的 next 指针从 NULL 变为新节点的地址。

原始头指针在 printList 函数中没有改变，但在插入节点时列表确实改变了

Original head pointer not being changed in the printList function, but the list does change when inserting a node

c

linked-list

singly-linked-list