使用指针从单链表中删除项目

Question

在最近的Slashdot访谈中, Linus Torvalds给出了一个例子,说明一些人如何使用指针,表明他们并不真正理解如何正确使用它们.

不幸的是,由于我是他所谈论的人之一,我也不理解他的例子:

我见过太多人通过跟踪"prev"条目删除单链表项,然后删除条目,做类似的事情

if (prev)
    prev->next = entry->next;
else
    list_head = entry->next;

每当我看到这样的代码时,我就会去"这个人不理解指针".而且很遗憾很常见.理解指针的人只使用"指向条目指针的指针",并使用list_head的地址初始化它.然后当他们遍历列表时,他们可以在不使用任何条件的情况下删除条目,只需执行即可

*pp = entry->next

有人可以提供更多解释为什么这种方法更好,以及它如何在没有条件声明的情况下工作？

Answer 1

一开始,你做到了

pp = &list_head;

并且,当你遍历列表时,你用这个"光标"前进

pp = &(*pp)->next;

这样,您始终可以跟踪"您来自"的位置,并可以修改生活在那里的指针.

因此,当您找到要删除的条目时,您可以这样做

*pp = entry->next

通过这种方式,您可以处理Afaq在另一个答案中提到的所有3个案例,从而有效地取消了NULL检查prev.

Answer 2

一旦要删除节点,重新连接列表会更有趣.让我们考虑至少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 |
---------     ---------     ---------

请注意,最后两种情况(中间和结尾)可以通过说"要删除的节点之前的节点必须指向要删除的节点所在的位置"来组合.

Answer 3

视频解释

Philip Buuck在此YouTube视频中讨论过此问题.如果您需要更详细的说明,我建议您观看此内容.

以举例说明

如果你喜欢从例子中学习,我准备了一个.假设我们有以下单链表:

表示如下(点击放大):

我们想删除节点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 = (node_t*)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指针的'double' 指针:

现在让我们分析一下如何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).这是至关重要的,因为它使我们能够改变*next的指针node_t是在前面node_t,我们要删除,有效地从列表中删除.

现在让我们将要删除的元素的地址(del->value == 8)分配给*del指针.

我们需要修复*p指针,以便**p指向我们要删除的元素之后 的一个元素*del:

在上面的代码中我们称之为free(del),因此没有必要设置del->next到NULL,但如果我们想指针返回从列表中,而不是完全删除"分离"的元素,我们会设置del->next = NULL:

Answer 4

在第一种方法中,通过从列表中取消链接来删除节点.

在第二种方法中,将下一个节点替换为要删除的节点.

显然,第二种方法以优雅的方式简化了代码.当然,第二种方法需要更好地理解链表和基础计算模型.

注意:这是一个非常相关但略有不同的编码问题.适合测试一个人的理解:https: //leetcode.com/problems/delete-node-in-a-linked-list/