在最近的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
这样，您就可以处理Afaq在另一个答案中提到的所有3种情况，有效消除对prev进行NULL检查的需要。
pp是一个节点指针的指针，所以需要进行解引用操作，然后按通常方式访问next，最后再次获取其地址。 - glglgltail，你会如何使用代码中提到的 pp 来实现呢？ - hasnobrains*pp = (*pp)->next。我说的对吗？ - Lion Laipp 指向不同的地方，而不是改变 pp 所指向的数据。 - glglgl如果你喜欢从例子中学习，我准备了一个。假设我们有以下单链表：
它被表示为以下形式（点击放大）：
我们想要删除值为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
让我们创建指向*head指针的p双重指针：
现在让我们分析void remove_from_list(int val, node_t **head)如何工作。只要*p && (**p).value != val，它就会遍历由head指向的链表。
在这个例子中，给定列表包含我们想要删除的值（即8）。在第二次循环while (*p && (**p).value != val)时，(**p).value变为8，因此我们停止迭代。
请注意，*p指向node_t中的变量node_t *next，该变量位于我们要删除的node_t之前（即**p）。这是至关重要的，因为它允许我们更改在我们要删除的node_t之前的node_t的*next指针，从而有效地将其从列表中删除。
现在让我们将要删除的元素（del->value == 8）的地址分配给*del指针。
我们需要修复*p指针，以使**p指向我们将要删除的*del元素之后的一个元素：
在上面的代码中，我们调用了free(del)，因此不需要将del->next设置为NULL，但是如果我们想返回指向从列表中“分离”而不是完全删除的元素的指针，则将del->next = NULL：
一旦要删除节点，重新连接列表会更有趣。让我们考虑至少3种情况：
1.从开头删除节点。
2.从中间删除节点。
3.从末尾删除节点。
从开头删除节点
当删除链表开头的节点时，无需执行任何节点重新链接操作，因为第一个节点没有前驱节点。例如，删除节点a：
link
|
v
--------- --------- ---------
| a | --+---> | b | --+---> | c | 0 |
--------- --------- ---------
然而，我们必须将指针修正到列表的开头：
link
|
+-------------+
|
v
--------- --------- ---------
| a | --+---> | b | --+---> | c | 0 |
--------- --------- ---------
从中间删除节点
从中间删除一个节点需要让前一个节点跳过被删除的节点。例如，删除包含 b 的节点：
link
|
v
--------- --------- ---------
| a | --+--+ | b | --+---> | c | 0 |
--------- | --------- ---------
| ^
+----------------+
link
|
v
--------- --------- ---------
| a | --+---> | b | 0 | | c | 0 |
--------- --------- ---------
|Dummy|->|node1|->|node2|->|node3|->|node4|->|node5|->NULL
^ ^
| |
curr curr->next // << toDel
tmp = curr->next;
curr->next = curr->next->next;
free(tmp);
这样，您就不需要检查是否为第一个元素，因为第一个元素始终是“Dummy”，永远不会被删除。
curr->next-next是一个笔误吗？ - Max Heiber@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 = 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
这里是一个完整的代码示例，使用函数调用来删除匹配的元素：
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
我们可以看到一切正常。
void rem2(list_entry **pp, int match_val)，它解决了Linus Torvalds的担忧，即许多开发人员不太理解指针，特别是指向指针的微妙之处。他将其用作示例，说明许多人不知道如何使用仅具有两个分支条件的指针删除链接的多个元素，因为这需要使用指向指针的指针。 - abetancort以下是我的理解，我发现这种方式更容易理解。
使用指向指针的指针，在链表中删除节点的示例。
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
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将指向第二个元素。
请注意：
”。list = &entry->next;
list = &(entry->next);