使用指针从单链表中删除项目
在最近的Slashdot访谈中， Linus Torvalds给出了一个例子，说明一些人如何以某种方式使用指针，表明他们不知道如何正确使用它们。
不幸的是，由于我是他所谈论的人之一，我也不了解他的例子：
我见过很多人通过跟踪“prev”条目来删除单链表条目，然后删除条目，做类似
if (prev) prev->next = entry->next; else list_head = entry->next;每当我看到这样的代码，我只是去“这个人不明白指针”。 可悲的是，这很常见。 理解指针的人只是使用“指向入口指针的指针”，并用list_head的地址初始化它。 然后当他们遍历列表，他们可以删除条目，而不使用任何条件，只是做
*pp = entry->next
有人可以提供更多的解释，说明为什么这种方法更好，以及如何在没有条件陈述的情况下工作？
在开始的时候，你呢
pp = &list_head;
而且，当你遍历列表时，你用这个“光标”前进
pp = &(*pp)->next;
这样，你总是跟踪“你来自哪里”的位置，并可以修改生活在那里的指针。
所以，当你发现条目被删除，你可以做
*pp = entry->next
这样，你照顾了所有的3例， 阿法在另一个答案中提到，有效地消除了对prev的NULL检查。
一旦节点被删除，重新连接列表更有趣。 我们至less考虑三种情况：
1.从头开始删除一个节点。
2.从中间移除一个节点。
3.从最后删除一个节点。
从开始删除
当删除列表开始处的节点时，由于第一个节点没有先前节点，所以不会执行节点的重新链接。 例如，使用以下命令删除节点：
link | v --------- --------- --------- | a | --+---> | b | --+---> | c | 0 | --------- --------- ---------
但是，我们必须修复指向列表开头的指针：
link | +-------------+ | v --------- --------- --------- | a | --+---> | b | --+---> | c | 0 | --------- --------- ---------
从中间去除
从中间删除节点要求前面的节点跳过被删除的节点。 例如，使用b：
link | v --------- --------- --------- | a | --+--+ | b | --+---> | c | 0 | --------- | --------- --------- | ^ +----------------+
这意味着我们需要一些方法在我们想要删除的节点之前引用节点。
从最后删除
从最后删除一个节点要求前面的节点成为列表的新的结尾（即在它之后没有指向任何东西）。 例如，使用c：
link | v --------- --------- --------- | a | --+---> | b | 0 | | c | 0 | --------- --------- ---------
请注意，最后两种情况（中间和结束）可以合并为： “要移除的节点之前的节点必须指向要移除的节点所在的位置”。
在第一种方法中，通过从列表中取消链接来删除节点。
在第二种方法中，将下一个节点replace为待删除节点。
显然，第二种方法以简洁的方式简化了代码。 当然，第二种方法需要更好地理解链表和底层计算模型。
注意 ：这是一个非常相关的，但稍有不同的编码问题。 很好的testing自己的理解： https ： //leetcode.com/problems/delete-node-in-a-linked-list/
我更喜欢虚拟节点方法，一个示例布局：
|Dummy|->|node1|->|node2|->|node3|->|node4|->|node5|->NULL ^ ^ | | curr curr->next // << toDel
然后，遍历到要删除的节点（toDel = curr> next）
tmp = curr->next; curr->next = curr->next-next; free(tmp);
这样，你不需要检查它是否是第一个元素，因为第一个元素总是Dummy，永远不会被删除。
这是一个完整的代码示例，使用函数调用来删除匹配的元素：
-
rem()使用prev去除匹配的元素 -
rem2()使用指针指针去除匹配的元素
// code.c #include <stdio.h> #include <stdlib.h> typedef struct list_entry { int val; struct list_entry *next; } list_entry; list_entry *new_node(list_entry *curr, int val) { list_entry *new_n = (list_entry *) malloc(sizeof(list_entry)); if (new_n == NULL) { fputs("Error in malloc\n", stderr); exit(1); } new_n->val = val; new_n->next = NULL; if (curr) { curr->next = new_n; } return new_n; } #define ARR_LEN(arr) (sizeof(arr)/sizeof((arr)[0])) #define CREATE_LIST(arr) create_list((arr), ARR_LEN(arr)) list_entry *create_list(const int arr[], size_t len) { if (len == 0) { return NULL; } list_entry *node = NULL; list_entry *head = node = new_node(node, arr[0]); for (size_t i = 1; i < len; ++i) { node = new_node(node, arr[i]); } return head; } void rem(list_entry **head_p, int match_val) // remove and free all entries with match_val { list_entry *prev = NULL; for (list_entry *entry = *head_p; entry; ) { if (entry->val == match_val) { list_entry *del_entry = entry; entry = entry->next; if (prev) { prev->next = entry; } else { *head_p = entry; } free(del_entry); } else { prev = entry; entry = entry->next; } } } void rem2(list_entry **pp, int match_val) // remove and free all entries with match_val { list_entry *entry; while ((entry = *pp)) { // assignment, not equality if (entry->val == match_val) { *pp = entry->next; free(entry); } else { pp = &entry->next; } } } void print_and_free_list(list_entry *entry) { list_entry *node; // iterate through, printing entries, and then freeing them for (; entry != NULL; node = entry, /* lag behind to free */ entry = entry->next, free(node)) { printf("%d ", entry->val); } putchar('\n'); } #define CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val) createList_removeMatchElems_print((arr), ARR_LEN(arr), (match_val)) void createList_removeMatchElems_print(const int arr[], size_t len, int match_val) { list_entry *head = create_list(arr, len); rem2(&head, match_val); print_and_free_list(head); } int main() { const int match_val = 2; // the value to remove { const int arr[] = {0, 1, 2, 3}; CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val); } { const int arr[] = {0, 2, 2, 3}; CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val); } { const int arr[] = {2, 7, 8, 2}; CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val); } { const int arr[] = {2, 2, 3, 3}; CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val); } { const int arr[] = {0, 0, 2, 2}; CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val); } { const int arr[] = {2, 2, 2, 2}; CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val); } { const int arr[] = {}; CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val); } return 0; }
请参阅此处的代码：
如果编译和使用这样的valgrind（一个内存泄漏检查器）：
gcc -std=c11 -Wall -Wextra -Werror -o go code.c && valgrind ./go
我们看到一切都很好。
@glglgl：
我写了以下简单的例子。 希望你能看看它为什么有效。
在函数void delete_node(LinkedList *list, void *data) ，我使用*pp = (*pp)->next; 它的工作。 说实话，我不明白它为什么起作用。 我甚至画出了指针图，但仍然不明白。 希望你能澄清一下。
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct _employee { char name[32]; unsigned char age; } Employee; int compare_employee(Employee *e1, Employee *e2) { return strcmp(e1->name, e2->name); } typedef int (*COMPARE)(void *, void *); void display_employee(Employee *e) { printf("%s\t%d\n", e->name, e->age); } typedef void (*DISPLAY)(void *); typedef struct _node { void *data; struct _node *next; } NODE; typedef struct _linkedlist { NODE *head; NODE *tail; NODE *current; } LinkedList; void init_list(LinkedList *list) { list->head = NULL; list->tail = NULL; list->current = NULL; } void add_head(LinkedList *list, void *data) { NODE *node = (NODE *) malloc(sizeof(NODE)); node->data = data; if (list->head == NULL) { list->tail = node; node->next = NULL; } else { node->next = list->head; } list->head = node; } void add_tail(LinkedList *list, void *data) { NODE *node = (NODE *) malloc(sizeof(NODE)); node->data = data; node->next = NULL; if (list->head == NULL) { list->head = node; } else { list->tail->next = node; } list->tail = node; } NODE *get_node(LinkedList *list, COMPARE compare, void *data) { NODE *n = list->head; while (n != NULL) { if (compare(n->data, data) == 0) { return n; } n = n->next; } return NULL; } void display_list(LinkedList *list, DISPLAY display) { printf("Linked List\n"); NODE *current = list->head; while (current != NULL) { display(current->data); current = current->next; } } void delete_node(LinkedList *list, void *data) { /* Linus says who use this block of code doesn't understand pointer. NODE *prev = NULL; NODE *walk = list->head; while (((Employee *)walk->data)->age != ((Employee *)data)->age) { prev = walk; walk = walk->next; } if (!prev) list->head = walk->next; else prev->next = walk->next; */ NODE **pp = &list->head; while (((Employee *)(*pp)->data)->age != ((Employee *)data)->age) { pp = &(*pp)->next; } *pp = (*pp)->next; } int main () { LinkedList list; init_list(&list); Employee *samuel = (Employee *) malloc(sizeof(Employee)); strcpy(samuel->name, "Samuel"); samuel->age = 23; Employee *sally = (Employee *) malloc(sizeof(Employee)); strcpy(sally->name, "Sally"); sally->age = 19; Employee *susan = (Employee *) malloc(sizeof(Employee)); strcpy(susan->name, "Susan"); susan->age = 14; Employee *jessie = (Employee *) malloc(sizeof(Employee)); strcpy(jessie->name, "Jessie"); jessie->age = 18; add_head(&list, samuel); add_head(&list, sally); add_head(&list, susan); add_tail(&list, jessie); display_list(&list, (DISPLAY) display_employee); NODE *n = get_node(&list, (COMPARE) compare_employee, sally); printf("name is %s, age is %d.\n", ((Employee *)n->data)->name, ((Employee *)n->data)->age); printf("\n"); delete_node(&list, samuel); display_list(&list, (DISPLAY) display_employee); return 0; }
输出：
Linked List Susan 14 Sally 19 Samuel 23 Jessie 18 name is Sally, age is 19. Linked List Susan 14 Sally 19 Jessie 18
