List-带头结点的双向循环链表

STL库中常用的封装好的string（专门用来处理字符串）以及vector（储存任意类型）还有list。前两种在存储空间上地址都是连续的，但是list存储地址不一定是连续的，list的底层实际是用一个带头双向循环链表实现下面为了更加深入了解学习list先手动写一个带头双向循环链表。

下面是我用C++写的

#include 
 
// 节点结构体
struct Node {
    int data;
    Node* prev;
    Node* next;
    
    Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};
 
// 双向循环链表
class DoublyCircularLinkedList {
private:
    Node* head; // 头节点
 
public:
    // 构造函数，初始化头节点
    DoublyCircularLinkedList() {
        head = new Node(0); // 头节点不存储实际数据
        head->next = head;
        head->prev = head;
    }
 
    // 判断链表是否为空
    bool isEmpty() {
        return head->next == head;
    }
 
    // 在链表尾部插入新节点
    void append(int data) {
        Node* newNode = new Node(data);
        Node* tail = head->prev; // 取尾节点
        
        tail->next = newNode;
        newNode->prev = tail;
        newNode->next = head;
        head->prev = newNode;
    }
 
    // 删除指定值的节点
    void remove(int data) {
        Node* current = head->next;
        while (current != head) {
            if (current->data == data) {
                Node* prevNode = current->prev;
                Node* nextNode = current->next;
 
                prevNode->next = nextNode;
                nextNode->prev = prevNode;
 
                delete current;
                return;
            }
            current = current->next;
        }
        std::cout << "未找到要删除的节点: " << data << std::endl;
    }
 
    // 显示链表内容
    void display() {
        if (isEmpty()) {
            std::cout << "链表为空" << std::endl;
            return;
        }
 
        Node* current = head->next;
        while (current != head) {
            std::cout << current->data << " ";
            current = current->next;
        }
        std::cout << std::endl;
    }
 
    // 析构函数，释放内存
    ~DoublyCircularLinkedList() {
        Node* current = head->next;
        while (current != head) {
            Node* temp = current;
            current = current->next;
            delete temp;
        }
        delete head; // 最后释放头节点
    }
};
 
int main() {
    DoublyCircularLinkedList list;
    list.append(10);
    list.append(20);
    list.append(30);
 
    std::cout << "链表内容: ";
    list.display();
 
    list.remove(20);
    std::cout << "删除20后的链表内容: ";
    list.display();
 
    return 0;
}

代码说明：

1. Node结构体表示链表中的节点，包含数据域data、指向前一个节点的指针prev和指向下一个节点的指针next。
2. DoublyCircularLinkedList类表示双向循环链表，包含头节点head，并提供了插入、删除和显示功能。
3. 头节点本身不存储实际数据，仅用于简化链表操作。
4. 链表是循环的，最后一个节点的next指向头节点，头节点的prev指向最后一个节点。

这样设计的双向循环链表可以方便地进行插入、删除、遍历等操作。

小tips：

1、为什么节点要用结构体实现而不在类函数中实现？

在C++中，将节点设计为独立的结构体而不是嵌入类的一个函数中，主要是出于职责分离和可复用性的考虑。节点的本质是链表中的数据单元，它与链表的操作逻辑分开。因此，使用结构体（或类）独立定义节点有以下几个好处：

• 职责清晰：节点只负责存储数据和指向下一个/前一个节点的指针，链表类则负责管理节点及其之间的连接、插入、删除等操作。
• 可复用性：将节点抽象为独立的结构体可以使它适用于不同的链表结构，比如单向链表、双向链表、循环链表等。而嵌入在类函数中的节点则会使代码的灵活性降低。
• 代码清晰：独立的节点结构可以提高代码的可读性和维护性，避免类中代码变得过于复杂

2、Node(int val) : data(val), prev(nullptr), next(nullptr)的作用是什么？

这句话是构造函数的初始化列表，它的作用是在创建Node对象时，将类的成员变量初始化为指定的值。具体的作用如下：

• Node(int val)：这是节点的构造函数，它接受一个整数val作为参数，并将其赋值给节点的data成员。
• : data(val)：这是初始化列表的一部分，表示在对象构造时直接将参数val赋值给节点的成员变量data。这样比在构造函数体内赋值更高效，因为它避免了先默认构造data再赋值的过程。
• prev(nullptr)和next(nullptr)：表示将prev和next这两个指针都初始化为nullptr。这是因为新节点刚创建时还没有前驱和后继节点，因此指向空。

3、为什么带头节点的链表头插头删可以不用传递二级指针？

• 头节点不会变化：无论链表如何插入或删除数据节点，头节点始终存在且不会被修改。所以操作时不需要传递二级指针，因为你始终知道链表从头节点开始。
• 简化边界条件处理：由于头节点不存储数据，不需要处理特殊情况，比如插入到空链表或删除最后一个节点等问题。头节点的存在将所有操作统一为对常规节点的操作，简化了代码逻辑。