删除单链表中的节点

Question

Suppose you have a pointer p to a node in a singly linked list that is not on the last node in the list. You have no other pointer to the list except the following links in each node.

Describe an O(1) algorithm that logically removes the value stored in the node pointed to by p (suggestion: use the next node).

这样做的想法是将信息从下一个节点传递到p指向的当前节点，并将下一个节点从列表中删除。 我的问题是为什么我们不删除指针指向的节点，而是删除下一个节点。我有点困惑。

Answer 1

您有一个指向该节点的指针，但无法更改前一个节点对它的引用；因此您必须复制并删除下一个节点。

您的指针p仅引用当前节点。由于您无法修改 prevous->next 以指向值为 3 的节点，因此您必须将下一个节点复制到当前节点，包括值和下一个指针。

Answer 2

总结

您将用列表中的下一个节点替换地址为 p 的节点。当你开始时你有：

        +----+   +----+
        |    |   |    |
     -->|  p |-->|next|-->
        |    |   |    |
        +----+   +----+
        0x1234

替换当前地址的节点后，您将拥有：

        +----+
        |    |
     -->|next|-->
        |    |
        +----+
        0x1234

列表中 p 之前的地址都没有变化。完成后，您只需：

        delete p;

详情

你的问题设置告诉你有一个指针 p 指向一个不是列表中最后一个节点的节点，你需要删除该节点的值。太好了，大部分工作已经完成，无需迭代查找要删除的节点。那么如何利用当前指针去取值（其实就是把那个地址的节点替换成下一个节点）？

这里可以利用指针p（&p）的地址和指向下一个节点的指针（p->next）来复制next 节点到当前地址，用它覆盖当前节点内容。由于您没有更改原始指针 p 指向的位置，它仍然指向在当前地址链接的原始节点的内存，允许您使用指针 p 释放内存以完成操作。

所以你要做的是首先，替换列表中当前地址的节点，例如

node **ppn = &p;               /* a pointer to pointer holding current address */

*ppn = p->next;                /* replace node at address of p with p->next */

(其中 p 指向当前节点，&p 是链表中链接的指针的地址，p->next 是指向下一个节点的单独指针在列表中）

由于之前的next指针仍然指向这个地址，而你已经将当前地址的节点替换为链表中的下一个节点（其next指针仍然指向正确的以下节点），这就是删除最初链接在列表中 p 的节点所需的全部内容。

要完成该过程并避免内存泄漏，您需要释放 (delete) 您删除的节点的内存。由于您没有更改 p 本身指向的位置，它仍然指向您从列表中删除的节点。所以你可以简单地：

delete p;

大功告成。

您需要花一点时间来了解您是如何使用 p &p 的地址作为列表中的占位符的，并且您只是简单地替换了最初位于该地址的节点 在您的列表中，以及您列表中的下一个节点。这将从列表中删除 p 指向的节点。 prev->next 仍然指向 p 的地址并且您分配给该地址的新节点仍然有一个有效的 ->next 指针指向列表中它后面的节点，所以您的列表是完整的没有一个节点。指针 p 仍然指向保存已删除节点的内存，因此您只需 delete p; 进行整理即可。

这就是 Linus on Understanding Pointers 中的解释，尽管我从来没有真正喜欢这个解释，因为我发现它有点单薄而且写得很笨拙。

现在您可以了解这些知识并查看我向您指出的 del_node() 和 delnode() 函数并开始理解它们的工作原理。灯泡闪烁可能需要一个小时或一天的时间，然后全部安装到位。没关系。考虑如何使用指针的地址以及指针指向的位置（例如，它保存的地址作为其值）需要一些努力才能与和平相处。

完整示例

完整示例使用：

*ppn = p->next;     /* replace node at address with next */
free (p);           /* delete current */

仅使用 p 及其地址删除 1 - 10 列表中的第 4 个节点：

#include <stdio.h>
#include <stdlib.h>

typedef struct node_t {
    int data;
    struct node_t *next;
} node_t;

/** add node at end of list, update tail to end */
node_t *add (node_t **head, int v)
{
    node_t **ppn = head,                    /* pointer to pointer to head */
            *pn = *head,                    /* pointer to head */
            *node = malloc (sizeof *node);  /* allocate new node */
 
    if (!node) {                            /* validate allocation */
        perror ("malloc-node");
        return NULL;
    }
    node->data = v;                         /* initialize members values */
    node->next = NULL;
 
    while (pn) {
        ppn = &pn->next;
        pn = pn->next;
    }
 
    return *ppn = node;    /* add & return new node */
}

/** print all nodes in list */
void prn (node_t *l)
{
    if (!l) {
        puts ("list-empty");
        return;
    }
    for (node_t *n = l; n; n = n->next)
        printf (" %d", n->data);
    putchar ('\n');
}

/** delete all nodes in list */
void del_list (node_t *l)
{
    node_t *n = l;
    while (n) {
        node_t *victim = n;
        n = n->next;
        free (victim);
    }
}

int main (void) {
    
    node_t *list = NULL, *p = NULL, **ppn = NULL;
    int node_to_rm = 4;
    
    for (int i = 0; i < 10; i++)
        if (!add (&list, i + 1))
            return 1;
    
    prn (list);
    
    /* iterate to find 4th node (with data = 5) */
    for (ppn=&list, p=list; p && node_to_rm; ppn=&p->next, p=p->next)
        node_to_rm--;
    
    *ppn = p->next;     /* replace node at address with next */
    free (p);           /* delete current */
    
    prn (list);
    del_list (list);
}

示例Use/Output

$ ./bin/ll_rm_single_node_given_p
 1 2 3 4 5 6 7 8 9 10
 1 2 3 4 6 7 8 9 10

内存Use/Error检查

$ valgrind ./bin/ll_rm_single_node_given_p
==22684== Memcheck, a memory error detector
==22684== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==22684== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==22684== Command: ./bin/ll_rm_single_node_given_p
==22684==
 1 2 3 4 5 6 7 8 9 10
 1 2 3 4 6 7 8 9 10
==22684==
==22684== HEAP SUMMARY:
==22684==     in use at exit: 0 bytes in 0 blocks
==22684==   total heap usage: 11 allocs, 11 frees, 1,184 bytes allocated
==22684==
==22684== All heap blocks were freed -- no leaks are possible
==22684==
==22684== For counts of detected and suppressed errors, rerun with: -v
==22684== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Answer 3

My question is why don't we remove the node pointed by our pointer instead of removing the next node.

您无法删除当前节点。

问题说明：

You have no other pointer to the list except the following links in each node.

这意味着在您之前有节点，特别是，有一个紧接在前的节点指向您的节点。您无法删除您的节点，因为您无法更改前一个节点。

您无法删除下一个节点。

问题表明您需要删除：

the value stored in the node pointed to by p.

那绝对不是下一个节点的值。

删除单链表中的节点

Remove node in a singly linked list

algorithm

list

singly-linked-list