在最近的一次Slashdot 采访中，Linus Torvalds 举了一个例子，说明有些人如何使用指针，表明他们并不真正了解如何正确使用它们。
不幸的是，由于我是他所说的人之一，所以我也无法理解他的例子：
我见过太多人通过跟踪“上一个”条目来删除单链表条目，然后删除该条目，执行类似的操作
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
这样，您可以处理Afaq在另一个答案中提到的所有 3 个案例，从而有效地消除了NULL对prev.
如果你喜欢从例子中学习，我准备了一个。假设我们有以下单链表：
表示如下（点击放大）：
我们要删除带有value = 8.
这是执行此操作的简单代码：
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
struct node_t {
int value;
node_t *next;
};
node_t* create_list() {
int test_values[] = { 28, 1, 8, 70, 56 };
node_t *new_node, *head = NULL;
int i;
for (i = 0; i < 5; i++) {
new_node = malloc(sizeof(struct node_t));
assert(new_node);
new_node->value = test_values[i];
new_node->next = head;
head = new_node;
}
return head;
}
void print_list(const node_t *head) {
for (; head; head = head->next)
printf("%d ", head->value);
printf("\n");
}
void destroy_list(node_t **head) {
node_t *next;
while (*head) {
next = (*head)->next;
free(*head);
*head = next;
}
}
void remove_from_list(int val, node_t **head) {
node_t *del, **p = head;
while (*p && (**p).value != val)
p = &(*p)->next; // alternatively: p = &(**p).next
if (p) { // non-empty list and value was found
del = *p;
*p = del->next;
del->next = NULL; // not necessary in this case
free(del);
}
}
int main(int argc, char **argv) {
node_t *head;
head = create_list();
print_list(head);
remove_from_list(8, &head);
print_list(head);
destroy_list(&head);
assert (head == NULL);
return EXIT_SUCCESS;
}
如果您编译并运行此代码，您将获得：
56 70 8 1 28
56 70 1 28
让我们创建指向指针的**p“双”*head指针：
现在让我们分析它是如何void remove_from_list(int val, node_t **head)工作的。它遍历head只要指向的列表*p && (**p).value != val。
在此示例中，给定列表包含value我们要删除的内容（即8）。在循环的第二次迭代后while (*p && (**p).value != val)变为(**p).value，8所以我们停止迭代。
请注意，*p指向其中的变量node_t *next位于我们要删除的 （即node_t）之前。这是至关重要的，因为它允许我们更改要删除的 前面的指针，从而有效地将其从列表中删除。node_t**p*nextnode_tnode_t
现在让我们将要删除的元素的地址 ( del->value == 8) 分配给*del指针。
我们需要修复*p指针，使其**p指向我们要删除的元素之后的一个元素： *del
在上面的代码中我们调用free(del)，因此没有必要设置del->next为NULL，但是如果我们想返回指向从列表中“分离”的元素的指针，而不是完全删除它，我们将设置del->next = NULL：
一旦要删除节点，重新连接列表会更有趣。让我们考虑至少 3 种情况：
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 |
--------- --------- ---------
请注意，最后两种情况（中间和结束）可以通过说“要删除的节点之前的节点必须指向要删除的节点所在的位置”来组合。
在第一种方法中，您通过从列表中取消链接来删除节点。
在第二种方法中，您将要删除的节点替换为下一个节点。
显然，第二种方法以一种优雅的方式简化了代码。当然，第二种方法需要更好地理解链表和底层计算模型。
注意：这是一个非常相关但略有不同的编码问题。有利于测试一个人的理解： 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 = 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：
我写了以下简单的例子。希望你能看看它为什么有效。
在 functionvoid 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 = 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 = 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 = malloc(sizeof(Employee));
strcpy(samuel->name, "Samuel");
samuel->age = 23;
Employee *sally = malloc(sizeof(Employee));
strcpy(sally->name, "Sally");
sally->age = 19;
Employee *susan = malloc(sizeof(Employee));
strcpy(susan->name, "Susan");
susan->age = 14;
Employee *jessie = 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
这是我的看法，我发现这种方式更容易理解。
使用指向指针的指针删除链表中的节点的示例。
struct node {
int value;
struct node *next;
};
void delete_from_list(struct node **list, int n)
{
struct node *entry = *list;
while (entry && entry->value != n) {
// store the address of current->next value (1)
list = &entry->next;
// list now stores the address of previous->next value
entry = entry->next;
}
if (entry) {
// here we change the previous->next value
*list = entry->next;
free(entry);
}
}
假设我们创建一个包含这些值的列表：
*node value next
----------------------------------------
a 1 null
b 2 a
c 3 b
d 4 c
e 5 d
如果我们要删除值为 3 的节点：
entry = e
while (entry && entry->value != 3) iterations:
e->value != 3
list = &e->next
entry = d
d->value != 3
list = &d->next
entry = c
c->value == 3
STOP
if (entry)
d->next = b (what was 'list' is dereferenced)
free(entry)
之后if (entry)我们有：
d->next = b
所以列表变成：
*node value next
----------------------------------------
a 1 null
b 2 a
c 3 b
d 4 b
e 5 d
最后：
free(entry)
列表变为：
*node value next
----------------------------------------
a 1 null
b 2 a
d 4 b
e 5 d
如果我们想删除第一个节点，它仍然可以工作，因为最初
*list == entry
因此：
*list = entry->next;
*list将指向第二个元素。
(1) 注意说：
list = &entry->next;
和说的一样：
list = &(entry->next);