从单链表中删除条目

Question

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

Answer 1

该条目实际上不是 "deleted"，它只是不再在列表中。如果这是您的连锁店：

A --> B --> C --> D --> E --> ■

而你想删除 C，你实际上只是链接它。它仍在内存中，但无法再从您的数据结构中访问。

            C 
A --> B --------> D --> E --> ■

最后一行将 B 的 next 指针设置为 D 而不是 C。

Answer 2

*indirect = entry->next; 那只是将它移动到下一个节点您需要删除条目一所以你必须在入口节点的下一个入口节点之前指向.. 所以你的循环应该在进入之前停止 while ((*indirect)->next != entry) 间接 = &(*间接)->下一个

(*indirect)->下一个=entry->下一个

希望对你有所帮助

Answer 3

第二个示例不是像第一个示例那样遍历列表中的条目，而是遍历[=14=]指向列表中条目的指针。这使得第二个示例可以根据您所询问的语句得出简单的结论，英语为 "set the pointer that used to point to the entry I want to remove from the list so that it now points to whatever that entry was pointing to"。换句话说，它使指向您要删除的条目的指针指向过去您要删除的条目。

第一个示例必须有一种特殊的方式来处理您要删除的条目的独特情况，即列表中的第一个条目。因为第二个例子循环遍历指针（以 &head 开头），所以它没有特殊情况。

Answer 4

what happens when *indirect = entry->next; evaluates? I cannot see why it leads to the remove of the certain entry.

希望大家对双指针有清晰的认识¹⁾.

假设如下：
节点结构为

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;

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

                          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 我们可以使用双指针 [=67= 更改它指向的地址]，它指向指针 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 |
      +---+     +---+     +---+
                ^^^^^     ^^^^^

从单链表中删除条目

delete an entry from a singly-linked list

c

pointers

list

singly-linked-list