c - 从单向链表中删除条目

所以今天我在看 The mind behind Linux | Linus Torvalds ，Linus 在视频里贴了两段代码，都是用来删除单向链表中的某个元素。

第一个(这是正常的):

void remove_list_entry(linked_list* entry) {
    linked_list* prev = NULL;
    linked_list* walk = head;
    while (walk != entry) {
        prev = walk;
        walk = walk->next;
    }
    if (!prev) {
        head = entry->next;
    } else {
        prev->next = entry->next;
    }
}

更好的一个:

void remove_list_entry(linked_list* entry) {
    // The "indirect" pointer points to the
    // *address* of the thing we'll update
    linked_list** indirect = &head;

    // Walk the list, looking for the thing that
    // points to the entry we want to remove
    while ((*indirect) != entry)
        indirect = &(*indirect)->next;

    // .. and just remove it
    *indirect = entry->next;
}

所以我无法理解第二段代码，当 *indirect = entry->next; 求值时会发生什么？我不明白为什么它会导致删除某个条目。请哪位大神解释一下，谢谢!

最佳答案

我希望你对双指针有清楚的了解1)。

假设如下:
节点结构是

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

和链表具有 5 节点和指向列表中第二个节点的 entry 指针。内存中的 View 将是这样的:

                          entry -+
   head                          |
      +---+     +-------+     +-------+     +-------+     +-------+     +--------+
      |   |---->| 1 |   |---->| 2 |   |---->| 3 |   |---->| 4 |   |---->| 5 |NULL|
      +---+     +-------+     +-------+     +-------+     +-------+     +--------+

这个说法:

linked_list** indirect = &head;

将使 indirect 指针指向 head 。

                         entry -+
  head                          |
     +---+     +-------+     +-------+     +-------+     +-------+     +--------+
     |   |---->| 1 |   |---->| 2 |   |---->| 3 |   |---->| 4 |   |---->| 5 |NULL|
     +---+     +-------+     +-------+     +-------+     +-------+     +--------+
       ^
       |
     +---+
     |   |
     +---+
   indirect

while 循环

    while ((*indirect) != entry)

*indirect 将给出第一个节点的地址，因为 head 指向第一个节点，并且因为 entry 指向第二个节点，循环条件评估为 true 并且以下代码将执行:

indirect = &(*indirect)->next;

这将使 indirect 指针指向第一个节点的 next 指针。内存 View :

                          entry -+
   head                          |
      +---+     +-------+     +-------+     +-------+     +-------+     +--------+
      |   |---->| 1 |   |---->| 2 |   |---->| 3 |   |---->| 4 |   |---->| 5 |NULL|
      +---+     +-------+     +-------+     +-------+     +-------+     +--------+
                      ^
                      |
                    +---+
                    |   |
                    +---+
                  indirect

现在将评估 while 循环条件。因为 indirect 指针现在指向第一个节点的 next，*indirect 将给出第二个节点的地址，并且由于 entry 指向第二个节点，循环条件评估为 false 并且循环退出。
现在将执行以下代码:

*indirect = entry->next;

*indirect 取消对第一个节点的 next 的引用，现在它被分配了 next 指针指向的节点的 entry。内存 View :

                          entry -+
   head                          |
      +---+     +-------+     +-------+     +-------+     +-------+     +--------+
      |   |---->| 1 |   |--   | 2 |   |---->| 3 |   |---->| 4 |   |---->| 5 |NULL|
      +---+     +-------+  \  +-------+     +-------+     +-------+     +--------+
                  *indirect \              /
                             +------------+

现在第一个节点的 next 指向列表中的第三个节点，这样第二个节点就会从列表中删除。

希望这能解决你所有的疑惑。

编辑 :

David 在评论中建议添加一些细节 - 为什么 (..) 中需要 &(*indirect)->next 括号？
indirect 的类型是 linked_list ** ，这意味着它可以保存 linked_list * 类型的指针的地址。*indirect 将给出 linked_list * 类型的指针，->next 将给出其 next 指针。
但是我们不能写 *indirect->next 因为运算符 -> 的优先级高于一元 * 运算符。因此，*indirect->next 将被解释为 *(indirect->next)，这在语法上是错误的，因为 indirect 是指向指针的指针。
因此我们需要 () 围绕 *indirect 。

此外， &(*indirect)->next 将被解释为 &((*indirect)->next) ，它是 next 指针的地址。

1) 如果您不知道双指针的工作原理，请查看以下内容:

让我们举个例子:

#include <stdio.h>

int main() {
        int a=1, b=2;
        int *p = &a;
        int **pp = &p;

        printf ("1. p : %p\n", (void*)p);
        printf ("1. pp : %p\n", (void*)pp);
        printf ("1. *p : %d\n", *p);
        printf ("1. *pp : %d\n", **pp);

        *pp = &b;  // this will change the address to which pointer p pointing to
        printf ("2. p : %p\n", (void*)p);
        printf ("2. pp : %p\n", (void*)pp);
        printf ("2. *p : %d\n", *p);
        printf ("2. *pp : %d\n", **pp);

        return 0;
}

在上面的代码中，在这个语句 - *pp = &b; 中，你可以看到，在不直接访问指针 p 的情况下，我们可以使用双指针 pp 更改它指向的地址，该指针指向指针 p ，因为取消引用双指针 pp 将给出指针 p 。

它的输出:

1. p : 0x7ffeedf75a38
1. pp : 0x7ffeedf75a28
1. *p : 1
1. *pp : 1
2. p : 0x7ffeedf75a34   <=========== changed
2. pp : 0x7ffeedf75a28
2. *p : 2
2. *pp : 2

内存 View 将是这样的:

//Below in the picture
//100 represents 0x7ffeedf75a38 address
//200 represents 0x7ffeedf75a34 address
//300 represents 0x7ffeedf75a28 address

int *p = &a
      p         a
      +---+     +---+
      |100|---->| 1 |
      +---+     +---+

        int **pp = &p;

      pp        p         a
      +---+     +---+     +---+
      |300|---->|100|---->| 1 |
      +---+     +---+     +---+


*pp = &b;

      pp        p         b
      +---+     +---+     +---+
      |300|---->|200|---->| 2 |
      +---+     +---+     +---+
                ^^^^^     ^^^^^

关于c - 从单向链表中删除条目，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/51794426/