如何将某个条目从单链表中彻底删除？
- 内容介绍
- 文章标签
- 相关推荐
本文共计1157个文字，预计阅读时间需要5分钟。
今天我正在观看《The Mind behind Linux | Linus Torvalds》，Linus 在视频中发布了两段代码，都用于删除单链表中的某个元素。第一个（这是常规的）：
cvoid remove_list_entry(linked_list *entry){ linked_list *temp=entry->next; entry->next=temp->next; free(temp);}
所以今天我正在观看 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时会发生什么？评估？我不明白为什么它导致删除某些条目.有人解释了,谢谢！
what happens when
*indirect = entry->next;evaluates? I cannot see why it leads to the remove of the certain entry.
我希望你对双指针有清楚的认识1).
假设如下：
节点结构是
typedef struct Node { int data; struct Node *next; } linked_list;
链表有5个节点,条目指针指向列表中的第二个节点.内存中的视图将是这样的：
entry -+ head | +---+ +-------+ +-------+ +-------+ +-------+ +--------+ | |---->| 1 | |---->| 2 | |---->| 3 | |---->| 4 | |---->| 5 |NULL| +---+ +-------+ +-------+ +-------+ +-------+ +--------+
这个说法：
linked_list** indirect = &head;
将使间接指针指向头部.
entry -+ head | +---+ +-------+ +-------+ +-------+ +-------+ +--------+ | |---->| 1 | |---->| 2 | |---->| 3 | |---->| 4 | |---->| 5 |NULL| +---+ +-------+ +-------+ +-------+ +-------+ +--------+ ^ | +---+ | | +---+ indirect
while循环
while ((*indirect) != entry)
* indirect将给出第一个节点的地址,因为head指向第一个节点,因为entry指向第二个节点,循环条件的计算结果为true,后面的代码将执行：
indirect = &(*indirect)->next;
这将使间接指针指向第一个节点的下一个指针.内存中的视图：
entry -+ head | +---+ +-------+ +-------+ +-------+ +-------+ +--------+ | |---->| 1 | |---->| 2 | |---->| 3 | |---->| 4 | |---->| 5 |NULL| +---+ +-------+ +-------+ +-------+ +-------+ +--------+ ^ | +---+ | | +---+ indirect
现在将评估while循环条件.因为间接指针现在指向第一个节点的下一个,所以* indirect将给出第二个节点的地址,并且由于条目指向第二个节点,因此循环条件的计算结果为false并且循环退出.
以下代码现在将执行：
*indirect = entry->next;
*间接取消引用第一个节点的下一个节点,现在它被分配了一个节点指向的节点的下一个节点.内存中的视图：
entry -+ head | +---+ +-------+ +-------+ +-------+ +-------+ +--------+ | |---->| 1 | |-- | 2 | |---->| 3 | |---->| 4 | |---->| 5 |NULL| +---+ +-------+ \ +-------+ +-------+ +-------+ +--------+ *indirect \ / +------------+
现在,第一个节点的下一个节点指向列表中的第三个节点,这样就可以从列表中删除第二个节点.
希望这清楚你所有的疑虑.
编辑：
大卫在评论中建议添加一些细节 – 为什么(&);(*间接) – >下一个需要(..)括号？
间接的类型是linked_list **,这意味着它可以保存linked_list *类型的指针的地址.
* indirect将给出linked_list *类型的指针和 – > next将给出它的下一个指针.
但我们不能写* indirect-> next因为运算符的优先级 – >高于一元*运算符.因此,* indirect-> next将被解释为*(indirect-> next),这在语法上是错误的,因为indirect是指向指针的指针.
因此我们需要()围绕*间接.
此外,&(* indirect) – > next将被解释为&((* indirect) – > 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 | +---+ +---+ +---+ ^^^^^ ^^^^^
本文共计1157个文字，预计阅读时间需要5分钟。
今天我正在观看《The Mind behind Linux | Linus Torvalds》，Linus 在视频中发布了两段代码，都用于删除单链表中的某个元素。第一个（这是常规的）：
cvoid remove_list_entry(linked_list *entry){ linked_list *temp=entry->next; entry->next=temp->next; free(temp);}
所以今天我正在观看 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时会发生什么？评估？我不明白为什么它导致删除某些条目.有人解释了,谢谢！
what happens when
*indirect = entry->next;evaluates? I cannot see why it leads to the remove of the certain entry.
我希望你对双指针有清楚的认识1).
假设如下：
节点结构是
typedef struct Node { int data; struct Node *next; } linked_list;
链表有5个节点,条目指针指向列表中的第二个节点.内存中的视图将是这样的：
entry -+ head | +---+ +-------+ +-------+ +-------+ +-------+ +--------+ | |---->| 1 | |---->| 2 | |---->| 3 | |---->| 4 | |---->| 5 |NULL| +---+ +-------+ +-------+ +-------+ +-------+ +--------+
这个说法：
linked_list** indirect = &head;
将使间接指针指向头部.
entry -+ head | +---+ +-------+ +-------+ +-------+ +-------+ +--------+ | |---->| 1 | |---->| 2 | |---->| 3 | |---->| 4 | |---->| 5 |NULL| +---+ +-------+ +-------+ +-------+ +-------+ +--------+ ^ | +---+ | | +---+ indirect
while循环
while ((*indirect) != entry)
* indirect将给出第一个节点的地址,因为head指向第一个节点,因为entry指向第二个节点,循环条件的计算结果为true,后面的代码将执行：
indirect = &(*indirect)->next;
这将使间接指针指向第一个节点的下一个指针.内存中的视图：
entry -+ head | +---+ +-------+ +-------+ +-------+ +-------+ +--------+ | |---->| 1 | |---->| 2 | |---->| 3 | |---->| 4 | |---->| 5 |NULL| +---+ +-------+ +-------+ +-------+ +-------+ +--------+ ^ | +---+ | | +---+ indirect
现在将评估while循环条件.因为间接指针现在指向第一个节点的下一个,所以* indirect将给出第二个节点的地址,并且由于条目指向第二个节点,因此循环条件的计算结果为false并且循环退出.
以下代码现在将执行：
*indirect = entry->next;
*间接取消引用第一个节点的下一个节点,现在它被分配了一个节点指向的节点的下一个节点.内存中的视图：
entry -+ head | +---+ +-------+ +-------+ +-------+ +-------+ +--------+ | |---->| 1 | |-- | 2 | |---->| 3 | |---->| 4 | |---->| 5 |NULL| +---+ +-------+ \ +-------+ +-------+ +-------+ +--------+ *indirect \ / +------------+
现在,第一个节点的下一个节点指向列表中的第三个节点,这样就可以从列表中删除第二个节点.
希望这清楚你所有的疑虑.
编辑：
大卫在评论中建议添加一些细节 – 为什么(&);(*间接) – >下一个需要(..)括号？
间接的类型是linked_list **,这意味着它可以保存linked_list *类型的指针的地址.
* indirect将给出linked_list *类型的指针和 – > next将给出它的下一个指针.
但我们不能写* indirect-> next因为运算符的优先级 – >高于一元*运算符.因此,* indirect-> next将被解释为*(indirect-> next),这在语法上是错误的,因为indirect是指向指针的指针.
因此我们需要()围绕*间接.
此外,&(* indirect) – > next将被解释为&((* indirect) – > 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 | +---+ +---+ +---+ ^^^^^ ^^^^^