从单向链表中删除条目

Question

所以今天我在看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;评估时会发生什么？我不明白为什么它会导致删除某个条目。请哪位大神解释一下，谢谢！

Answer 1

*indirect = entry->next;评估时会发生什么？我不明白为什么它会导致删除某个条目。

我希望你对双指针¹⁾有清楚的了解。

假设如下：
节点结构是

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

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

                          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第一个节点的指针。内存视图：

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

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

*indirect = entry->next;

*indirect解除对next第一个节点的引用，它现在被分配了指针指向next的节点entry。内存视图：

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

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

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

编辑：

大卫曾建议，在评论，添加周围的一些细节-为什么在(..)所需括号&(*indirect)->next？

indirectis的类型linked_list **，这意味着它可以保存类型指针的地址linked_list *。该*indirect将给类型的指针linked_list *，并->next会给予其next指针。
但是我们不能写，*indirect->next因为->运算*符的优先级高于一元运算符。因此，*indirect->next将被解释为*(indirect->next)which 在语法上是错误的，因为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

内存视图将是这样的：

//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 |
      +---+     +---+     +---+
                ^^^^^     ^^^^^