C++带头双向循环链表超详细解析

1. 什么是带头双向循环链表？

带头双向循环链表（DCLL）是一种数据结构，它由一系列节点组成，并将它们通过指针连接起来。每个节点包含两个指针，分别指向其前驱节点和后继节点，同时还保存了一个值域。

带头双向循环链表有两个特点：

1. 它头指针head是一个“虚拟节点”，它并不存储数据，仅仅用来标记链表的开始。因此，DCLL链表中不会出现“头指针为空”的情况。

2. 它是个环，即最后一个节点的后继节点指向head，而head的前驱节点指向最后一个节点。因此，我们可以在列表中沿着前驱和后继指针向前或向后移动，直到回到head，实现一个循环访问的效果。

2. 如何实现带头双向循环链表？

我们可以通过C++中的类和指针来实现带头双向循环链表。

以下是带头双向循环链表的结构体定义：

struct ListNode {
    int val;
    ListNode *prev, *next;
    ListNode(int x) : val(x), prev(nullptr), next(nullptr) {}
};

（1） 插入节点

• 实现向链表末尾插入节点的函数：

void insert_back(ListNode *&head, int val) {
    if (head == nullptr) {
        head = new ListNode(0);  // head是一个虚拟节点
        head->prev = head->next = head;  // 初始时，head节点的前驱指针与后继指针都指向自己
    }
    ListNode *cur = new ListNode(val);
    cur->prev = head->prev;
    cur->next = head;
    head->prev->next = cur;
    head->prev = cur;
}

• 实现向链表头部插入节点的函数：

void insert_front(ListNode *&head, int val) {
    if (head == nullptr) {
        head = new ListNode(0);  // head是一个虚拟节点
        head->prev = head->next = head;  // 初始时，head节点的前驱指针与后继指针都指向自己
    }
    ListNode *cur = new ListNode(val);
    cur->prev = head;
    cur->next = head->next;
    head->next->prev = cur;
    head->next = cur;
}

（2） 删除节点

• 删除链表中某个值为val的节点：

void remove(ListNode *&head, int val) {
    if (head == nullptr) return;
    ListNode *cur = head->next;
    while (cur != head) {
        if (cur->val == val) {
            cur->prev->next = cur->next;
            cur->next->prev = cur->prev;
            delete cur;
            return;
        }
        cur = cur->next;
    }
}

（3） 遍历链表

• 遍历正向链表：

void traverse(ListNode *&head) {
    if (head == nullptr) return;
    ListNode *cur = head->next;
    while (cur != head) {
        cout << cur->val << " ";
        cur = cur->next;
    }
}

• 遍历反向链表：

void traverse_reverse(ListNode *&head) {
    if (head == nullptr) return;
    ListNode *cur = head->prev;
    while (cur != head) {
        cout << cur->val << " ";
        cur = cur->prev;
    }
}

3. 两条示例说明

下面分别演示向链表末尾插入元素和向链表头部插入元素的用法：

int main() {
    ListNode *head = nullptr;
    // 向链表末尾插入元素
    insert_back(head, 1);
    insert_back(head, 2);
    insert_back(head, 3);
    traverse(head);  // 正向遍历：1 2 3
    traverse_reverse(head);  // 反向遍历：3 2 1

    // 向链表头部插入元素
    insert_front(head, 4);
    insert_front(head, 5);
    insert_front(head, 6);
    traverse(head);  // 正向遍历：6 5 4 1 2 3
    traverse_reverse(head);  // 反向遍历：3 2 1 4 5 6

    return 0;
}

以上两个示例可以很好地演示带头双向循环链表的插入节点和遍历函数的用法。