双向循环链表删除节点

前言

在数据结构中，双向循环链表是一种常见的线性数据结构，它具有前驱指针和后继指针两个方向的链接关系，并且首尾相连形成一个闭环。这种结构使得访问任意一个节点的前后节点都非常方便。当我们需要从双向循环链表中删除某个节点时，需要注意一些特定的操作步骤以保持链表的有效性和一致性。

双向循环链表的基本概念

定义

双向循环链表是一种每个节点都包含两个指针的数据结构，分别指向其前一个节点和后一个节点。通常情况下，还会有一个头节点或者尾节点来简化操作。

特点

1. 方便访问前后节点：由于每个节点都有向前和向后的指针，因此可以很方便地从当前节点访问到它的任何相邻节点。
2. 首尾相连的闭环结构：双向循环链表中的最后一个节点指向头节点（或第一个节点），形成一个环状结构。

删除节点的操作步骤

在双向循环链表中删除某个特定节点 p 的操作主要包括以下几个步骤：

1. 断开指针连接：首先需要断开目标节点 p 与其前后节点的连接。这可以通过修改 p 的前驱节点和后继节点的指针来完成。
2. 更新前后节点的指针：为了保持双向循环链表的一致性，需要分别更新 p 的前驱节点的下一个指针以及 p 的后继节点的上一个指针，将它们指向彼此。
3. 释放资源（可选）：如果程序中涉及动态内存分配的话，还需要释放目标节点所占用的内存。

具体代码示例

以下是使用C语言实现双向循环链表删除节点的基本步骤：

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

void deleteNode(struct Node **head, struct Node *p) {
    if (*head == NULL || p == NULL)
        return;

    // 如果要删除的节点是头节点
    if (p->prev != NULL && p->next != NULL) {
        p->prev->next = p->next;
        p->next->prev = p->prev;
    } else if (*head == p) {  // 头节点本身被删除了的情况
        *head = p->next;       // 新头结点为原头节点的下一个节点
        (p->next)->prev = NULL;   // 新头结点的前驱指针置空
    } else if (p->prev == NULL && p->next != NULL) {  // 仅有一个节点的情况
        *head = p->next;
        (p->next)->prev = NULL;
    }

    free(p);  // 释放被删除结点的内存空间
}

注意事项

• 链表为空或目标节点不存在：在实际编程过程中，应首先检查链表是否为空以及目标节点是否存在。
• 操作前后的指针设置：确保在断开当前节点与前后节点连接的同时正确设置了它们之间的关系，否则可能导致数据结构的破坏。

通过以上方法和步骤，在双向循环链表中删除指定节点时可以高效地保持链表结构的有效性和一致性。