c - C链表指针理解

我试图了解C链表指针的工作方式。
我知道指向变量的指针是指向地址存储器的“链接”，并且指向指针的指针有时是指向指针本身的引用。

我关心的是，例如，节点引用如何修改原始列表值，而不是列表本身。

我会更好地解释自己：

void insertNode(struct node** head, int value) {

    struct node* new = malloc(sizeof(struct node*));
    struct node* ref = (*head); //this is a reference. -> same address.

    //base case
    if((*head) == NULL) {
        //do things
    } else { // not null
        while(ref->next != null) {
            ref = ref->next; //THIS: how can this not modify the head itself?
        }

        //null spot found, set up node
        new->value = 10; //some int here
        new->next = NULL;

        ref->next = new; //Instead, how can this modify the head? and why?
    }
}

这是一些代码片段，我的问题是：
是的，我要保留一个引用。
但为什么

ref = ref->next;

仅修改ref本身，而

ref->next = new

还改头吗？

通过GDB，我发现两者在开始时共享相同的地址内存，但是ref仅修改新插入内容上的引用列表。

有人可以解释吗？

最佳答案

也许有些图片会有所帮助。

在调用insertNode之前，您需要像这样链接一系列节点：

+-------+------+      +-------+------+      +-------+------+
| value | next | ---> | value | next | ---> | value | next | ---|||
+-------+------+      +-------+------+      +-------+------+

您有一个指针（称为h）指向列表的第一个元素：

+---+
| h |
+---+
  |
  V
+-------+------+      +-------+------+      +-------+------+
| value | next | ---> | value | next | ---> | value | next | ---|||
+-------+------+      +-------+------+      +-------+------+

调用insertNode时，您将指向h的指针作为参数传递给我们，我们将其称为head：

+------+
| head |
+------+
  |
  V
+---+
| h |
+---+
  |
  V
+-------+------+      +-------+------+      +-------+------+
| value | next | ---> | value | next | ---> | value | next | ---|||
+-------+------+      +-------+------+      +-------+------+

您创建一个名为ref的指针变量，该变量采用*head（h）的值； IOW，ref结束时指向列表的第一个元素：

+------+ +-----+
| head | | ref |
+------+ +-----+
  |        |
  V        |
+---+      |
| h |      |
+---+      |
  |   +----+
  V   V
+-------+------+      +-------+------+      +-------+------+
| value | next | ---> | value | next | ---> | value | next | ---|||
+-------+------+      +-------+------+      +-------+------+

然后，在堆上创建另一个节点，并将该指针分配给名为new的局部变量：

+------+ +-----+ +-----+      +-------+------+
| head | | ref | | new | ---> | value | next |
+------+ +-----+ +-----+      +-------+------+
  |        |
  V        |
+---+      |
| h |      |
+---+      |
  |   +----+
  V   V
+-------+------+      +-------+------+      +-------+------+
| value | next | ---> | value | next | ---> | value | next | ---|||
+-------+------+      +-------+------+      +-------+------+

因此，需要注意的是，尽管ref和*head（h）具有相同的值（列表中第一个节点的地址），但它们是不同的对象。因此，任何更改ref的值均不会影响head或h。

因此，如果执行此循环

while(ref->next != null) {
    ref = ref->next;

第一次迭代的结果是

+------+ +-----+ +-----+      +-------+------+
| head | | ref | | new | ---> | value | next |
+------+ +-----+ +-----+      +-------+------+
  |        |
  V        |
+---+      |
| h |      |
+---+      |
  |        +------------+
  V                     V
+-------+------+      +-------+------+      +-------+------+
| value | next | ---> | value | next | ---> | value | next | ---|||
+-------+------+      +-------+------+      +-------+------+

经过另一次迭代，我们得到

+------+ +-----+ +-----+      +-------+------+
| head | | ref | | new | ---> | value | next |
+------+ +-----+ +-----+      +-------+------+
  |        |
  V        |
+---+      |
| h |      |
+---+      |
  |        +----------------------------------+
  V                                           V
+-------+------+      +-------+------+      +-------+------+
| value | next | ---> | value | next | ---> | value | next | ---|||
+-------+------+      +-------+------+      +-------+------+

此时，ref->next是NULL，因此循环退出。

然后，我们为new->value和new->next分配值，以使new->next为NULL：

+------+ +-----+ +-----+      +-------+------+
| head | | ref | | new | ---> | value | next | ---|||
+------+ +-----+ +-----+      +-------+------+
  |        |
  V        |
+---+      |
| h |      |
+---+      |
  |        +----------------------------------+
  V                                           V
+-------+------+      +-------+------+      +-------+------+
| value | next | ---> | value | next | ---> | value | next | ---|||
+-------+------+      +-------+------+      +-------+------+

最后，我们将ref->next设置为new的值，从而将节点new指向该列表的末尾：

+------+ +-----+ +-----+      +-------+------+
| head | | ref | | new | ---> | value | next | ---|||
+------+ +-----+ +-----+      +-------+------+
  |        |                    ^
  V        |                    |
+---+      |                    +-------------------------------+
| h |      |                                                    |
+---+      |                                                    |
  |        +----------------------------------+                 |
  V                                           V                 |
+-------+------+      +-------+------+      +-------+------+    |
| value | next | ---> | value | next | ---> | value | next | ---+
+-------+------+      +-------+------+      +-------+------+

请注意，ref->next不是指向变量new，而是指向new指向的对象。

因此，这就是为什么更新ref不会影响head（或*head（h））的原因。列表为空的基本情况将最终写入*head（h），并将其设置为指向从堆分配的新节点。