删除双向链表的头部

Question

很抱歉提出如此低质量的问题，但我不知道为什么以下代码不起作用。

list指向节点的头部。

void DeleteHeadNode(Node** list, Node * node)
    {
        if ((*list) == node) {
            Node * next = node->nextnode;
            next->prevnode = NULL;
        free(*list);
    }
}

Answer 1

我猜 "doesn't work" 意味着 list 在您的函数之后不再有效 - 这将是正确的。

你应该

void DeleteHeadNode(Node** list, Node* node)
{
    if ((node != NULL) && (*list == node))    // check node being deleted
    {
        Node* next = node->nextnode;
        if (next != NULL)                     // ensure next exists
        {
           next->prevnode = NULL;
           free(*list);
           list = &next;                      // update pointer to head of list
        }
        else                                  // no next, list is now becoming empty
        {
           free(*list);
           list = NULL;                       // update pointer to head of list
        }
    }
}

Answer 2

Node**的用法作为别名使用。如果传递列表变量的地址，可以通过更改 Node* 值来更改它。

通过这种方式将传递的列表变量设置为空或第二个节点。

以下是使用模式。

void DeleteNode(Node** list, int data)
{
    while (*list != NULL && (*list)->data != data) {
        list = &(node->nextnode);
    }
    if (*list != NULL) {
        Node* found = *list;
        *list = found->nextnode;

        if (found->nextnode != NULL) {
            found->nextnode->prevnode = *list;
        }
        free(found);
    }
}

用法：

Node* list;
...
DeleteNode(&list, ...);

前一个节点（prevnode，双链表）并不是真正需要的。

while 循环很有趣：别名 list 从列表头设置到下一个节点字段的地址。因此 *list 的后续更改要么更改传递的列表变量，要么更改某个下一个节点字段。

void SortedInsertNode(Node** list, int data)
{
    Node* node = (Node*) malloc(sizeof(Node));
    node->data = data;
    node->prevnode = NULL;
    node->nextnode = NULL;
    while (*list != NULL && data >= (*list)->data) {
        node->prevnode = *list;
        list = &(node->nextnode);
    }
    node->nextnode = *list;
    *list = node;

    if (node->nextnode != NULL) {
        node->nextnode->prevnode = *list;
    }
}

删除头部：

void DeleteHead(Node** list)
{
    if (*list != null) {
        Node* dead = *list;
        *list = (*list)->nextnode;
        (*list)->prevnede = NULL;
        free(dead);
    }
}

删除双向链表的头部

Deleting the head of doubly linked list

doubly-linked-list