c - 我是否正确地在 C 中实现了双向链表的删除节点函数？

Question

我正在学习双向链表。我已经实现了一个可以正常工作的删除节点函数，并且旨在无论要删除的节点是第一个节点、最后一个节点还是其间的任何节点，都可以正常工作。然而，我想知道我的逻辑是否正确(我应该说是高效的)。我在确定正确执行此功能的明确示例时遇到了一些麻烦。仅供引用，此链表不跟踪尾部。如有任何反馈，我们将不胜感激。

Node *removeNode(Node *head, int d)
{
    Node *curr = head;
    while (curr != NULL){
        if (curr->data == d){
            if (curr->prev == NULL && curr->next == NULL){
                free(curr);
                head = NULL;
                return head;
            } else if (curr->prev == NULL){
                curr->next->prev = NULL;
                head = curr->next;
                free(curr);
                return head;
            } else if (curr->next == NULL){
                curr->prev->next = NULL;
                free(curr);
                return head;
            } else if (curr->prev != NULL && curr->next != NULL){
                curr->next->prev = curr->prev;
                curr->prev->next = curr->next;
                free(curr);
                return head;
            }
        } else if (curr->data != d){
            curr = curr->next;
        }           
    }
    return head;
}

Answer 1

您当前的代码工作正常；那挺好的。和Valgrind给它一个干净的健康状况，至少在使用我创建的支持代码运行时是这样。不过，它可以简化。

这是我想到的:

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

typedef struct Node Node;

struct Node
{
    int data;
    Node *prev;
    Node *next;
};

static Node *removeNode(Node *head, int d)
{
    Node *curr = head;
    while (curr != NULL)
    {
        if (curr->data != d)
            curr = curr->next;
        else
        {
            if (curr->prev != NULL)
                curr->prev->next = curr->next;
            else
                head = curr->next;
            if (curr->next != NULL)
                curr->next->prev = curr->prev;
            free(curr);
            return head;
        }
    }
    return head;
}

static Node *addNodeAtHead(Node *head, int d)
{
    Node *item = malloc(sizeof(*item));
    if (item != 0)
    {
        item->next = head;
        item->prev = NULL;
        if (head != 0)
            head->prev = item;
        item->data = d;
    }
    return item;
}

static void dumpList(const char *tag, Node *head)
{
    printf("%s:", tag);
    while (head != 0)
    {
        printf(" %d", head->data);
        head = head->next;
    }
    putchar('\n');
}

int main(void)
{
    Node *head = 0;
    head = addNodeAtHead(head, 23);
    head = addNodeAtHead(head, 43);
    head = addNodeAtHead(head, 73);
    head = addNodeAtHead(head, 13);
    head = addNodeAtHead(head, 33);
    dumpList("Full", head);

    head = removeNode(head, 33);
    dumpList("Lost 33", head);
    head = removeNode(head, 23);
    dumpList("Lost 23", head);
    head = removeNode(head, 13);
    dumpList("Lost 13", head);
    head = removeNode(head, 34);
    dumpList("Lost 34", head);
    head = removeNode(head, 43);
    dumpList("Lost 43", head);
    head = removeNode(head, 73);
    dumpList("Lost 73", head);
    head = removeNode(head, 37);
    dumpList("Lost 37", head);

    return 0;
}

根本的区别在于上面的代码在可行的最大程度上避免了专门处理特殊情况。

• 如果前一个节点不为null，则调整前一个节点的next指针指向下一个节点(并且下一个节点是否为null并不重要)；
• 否则，头必须更改为指向下一个节点(并且下一个节点是否为 null 仍然无关紧要)。
• 如果下一个节点不为空，则调整下一个节点的前一个指针指向前一个节点(并且前一个节点是否为空并不重要)。
• 然后释放当前节点并返回头节点。

在运行 macOS Sierra 10.12.5 的 Mac 上运行时的示例输出:

$ make dl61 && valgrind --suppressions=etc/suppressions-macos-10.12.5 -- ./dl61
gcc -O3 -g -std=c11 -Wall -Wextra -Werror -Wmissing-prototypes -Wstrict-prototypes dl61.c -o dl61 
==3505== Memcheck, a memory error detector
==3505== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==3505== Using Valgrind-3.13.0.SVN and LibVEX; rerun with -h for copyright info
==3505== Command: ./dl61
==3505== 
Full: 33 13 73 43 23
Lost 33: 13 73 43 23
Lost 23: 13 73 43
Lost 13: 73 43
Lost 34: 73 43
Lost 43: 73
Lost 73:
Lost 37:
==3505== 
==3505== HEAP SUMMARY:
==3505==     in use at exit: 22,308 bytes in 163 blocks
==3505==   total heap usage: 184 allocs, 21 frees, 28,572 bytes allocated
==3505== 
==3505== LEAK SUMMARY:
==3505==    definitely lost: 0 bytes in 0 blocks
==3505==    indirectly lost: 0 bytes in 0 blocks
==3505==      possibly lost: 0 bytes in 0 blocks
==3505==    still reachable: 0 bytes in 0 blocks
==3505==         suppressed: 22,308 bytes in 163 blocks
==3505== 
==3505== For counts of detected and suppressed errors, rerun with: -v
==3505== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 5 from 5)
$

代码很少会好到无法改进的程度。我认为 removeNode() 的这个变体稍微整洁一点。它的循环只关心迭代列表以找到要删除的(第一个)节点。然后，如果找到节点，则会在循环体之外将其删除。此代码需要 <assert.h> header 也如所写(但尚未触发)。

static Node *removeNode(Node *head, int d)
{
    Node *curr = head;
    while (curr != NULL && curr->data != d)
        curr = curr->next;
    if (curr != NULL)
    {
        assert(curr->data == d);
        if (curr->prev != NULL)
            curr->prev->next = curr->next;
        else
            head = curr->next;
        if (curr->next != NULL)
            curr->next->prev = curr->prev;
        free(curr);
    }
    return head;
}

结果与之前相同。