循环双向链表的概念

循环双向链表是一种链表数据结构，其中每个节点包含指向前驱节点和后继节点的指针。与普通双向链表不同的是，循环双向链表的头节点的前驱指针指向尾节点，而尾节点的后继指针指向头节点，形成一个闭环。这种结构使得从任意节点出发都可以遍历整个链表，无论是向前还是向后。

节点结构体定义

首先，让我们定义循环双向链表的节点结构：

// 循环双向链表的节点结构体
struct Node {
    int data;        // 节点存储的数据
    Node* prev;      // 指向前驱节点的指针
    Node* next;      // 指向后继节点的指针
    
    // 构造函数，方便创建节点时初始化数据
    Node(int value) : data(value), prev(nullptr), next(nullptr) {}
};

循环双向链表的基本操作

下面是实现循环双向链表的完整代码，包含了创建、插入、删除和遍历等基本操作：

#include <iostream>

// 循环双向链表的节点结构体
struct Node {
    int data;        // 节点存储的数据
    Node* prev;      // 指向前驱节点的指针
    Node* next;      // 指向后继节点的指针
    
    // 构造函数，方便创建节点时初始化数据
    Node(int value) : data(value), prev(nullptr), next(nullptr) {}
};

// 循环双向链表类
class CircularDoublyLinkedList {
private:
    Node* head;      // 头节点指针

public:
    // 构造函数，初始化空链表
    CircularDoublyLinkedList() : head(nullptr) {}
    
    // 析构函数，释放链表内存
    ~CircularDoublyLinkedList() {
        clear();
    }
    
    // 判断链表是否为空
    bool isEmpty() const {
        return head == nullptr;
    }
    
    // 在链表头部插入新节点
    void insertAtHead(int value) {
        Node* newNode = new Node(value);
        
        if (isEmpty()) {
            // 空链表的情况，新节点既是头节点也是尾节点
            head = newNode;
            newNode->next = newNode;  // 自己指向自己形成环
            newNode->prev = newNode;
        } else {
            // 非空链表，插入到头部
            Node* tail = head->prev;  // 找到尾节点
            
            newNode->next = head;     // 新节点的后继指向原头节点
            newNode->prev = tail;     // 新节点的前驱指向尾节点
            
            tail->next = newNode;     // 尾节点的后继指向新节点
            head->prev = newNode;     // 原头节点的前驱指向新节点
            
            head = newNode;           // 更新头节点为新节点
        }
    }
    
    // 在链表尾部插入新节点
    void insertAtTail(int value) {
        if (isEmpty()) {
            insertAtHead(value);  // 空链表时，尾部插入等同于头部插入
            return;
        }
        
        // 找到尾节点（头节点的前驱）
        Node* tail = head->prev;
        Node* newNode = new Node(value);
        
        newNode->next = head;     // 新节点的后继指向头节点
        newNode->prev = tail;     // 新节点的前驱指向尾节点
        
        tail->next = newNode;     // 尾节点的后继指向新节点
        head->prev = newNode;     // 头节点的前驱指向新节点
    }
    
    // 删除链表头部节点
    void deleteAtHead() {
        if (isEmpty()) return;  // 空链表不做处理
        
        if (head->next == head) {
            // 只有一个节点的情况
            delete head;
            head = nullptr;
        } else {
            // 多个节点的情况
            Node* tail = head->prev;  // 找到尾节点
            Node* newHead = head->next;  // 新头节点
            
            tail->next = newHead;     // 尾节点的后继指向新头节点
            newHead->prev = tail;     // 新头节点的前驱指向尾节点
            
            delete head;              // 释放原头节点内存
            head = newHead;           // 更新头节点
        }
    }
    
    // 删除链表尾部节点
    void deleteAtTail() {
        if (isEmpty()) return;  // 空链表不做处理
        
        if (head->next == head) {
            // 只有一个节点的情况
            delete head;
            head = nullptr;
        } else {
            // 多个节点的情况
            Node* tail = head->prev;  // 找到尾节点
            Node* newTail = tail->prev;  // 新尾节点
            
            newTail->next = head;     // 新尾节点的后继指向头节点
            head->prev = newTail;     // 头节点的前驱指向新尾节点
            
            delete tail;              // 释放原尾节点内存
        }
    }
    
    // 遍历链表（正向）
    void traverseForward() const {
        if (isEmpty()) {
            std::cout << "链表为空" << std::endl;
            return;
        }
        
        Node* current = head;
        do {
            std::cout << current->data << " ";
            current = current->next;
        } while (current != head);  // 回到头节点时结束遍历
        
        std::cout << std::endl;
    }
    
    // 遍历链表（反向）
    void traverseBackward() const {
        if (isEmpty()) {
            std::cout << "链表为空" << std::endl;
            return;
        }
        
        Node* current = head->prev;  // 从尾节点开始
        do {
            std::cout << current->data << " ";
            current = current->prev;
        } while (current != head->prev);  // 回到尾节点时结束遍历
        
        std::cout << std::endl;
    }
    
    // 清空链表
    void clear() {
        if (isEmpty()) return;
        
        Node* current = head;
        Node* nextNode;
        
        // 遍历链表，逐个删除节点
        do {
            nextNode = current->next;
            delete current;
            current = nextNode;
        } while (current != head);
        
        head = nullptr;  // 链表清空后，头节点置空
    }
};

// 主函数示例
int main() {
    CircularDoublyLinkedList list;
    
    // 插入节点
    list.insertAtHead(10);
    list.insertAtTail(20);
    list.insertAtHead(5);
    list.insertAtTail(30);
    
    // 遍历链表
    std::cout << "正向遍历: ";
    list.traverseForward();  // 输出: 5 10 20 30
    
    std::cout << "反向遍历: ";
    list.traverseBackward();  // 输出: 30 20 10 5
    
    // 删除节点
    list.deleteAtHead();
    list.deleteAtTail();
    
    std::cout << "删除后的正向遍历: ";
    list.traverseForward();  // 输出: 10 20
    
    return 0;
}

代码解析

1. 节点结构体：Node 结构体包含三个成员：数据 data、指向前驱节点的指针 prev 和指向后继节点的指针 next。

2. 链表类：CircularDoublyLinkedList 类封装了链表的操作，包括初始化、插入、删除和遍历等。

3. 插入操作：

   • insertAtHead：在链表头部插入新节点。
   • insertAtTail：在链表尾部插入新节点。

4. 删除操作：

   • deleteAtHead：删除链表头部节点。
   • deleteAtTail：删除链表尾部节点。

5. 遍历操作：

   • traverseForward：从头部开始正向遍历链表。
   • traverseBackward：从尾部开始反向遍历链表。

6. 清空操作：clear 方法释放链表中所有节点的内存，并将头节点置空。

通过这种方式，你可以实现一个完整的循环双向链表，并进行各种操作。循环双向链表的优势在于可以双向遍历，且在表头和表尾插入删除操作的时间复杂度都是 O(1)。