C++中链表：单链表、双向链表、循环链表

在 C++ 中，链表是一种常用的数据结构，用于存储一组有序的元素。链表中的元素不必在内存中连续存储，而是通过指针连接起来。链表分为三种类型：单链表、双向链表和循环链表。

单链表（Singly Linked List）

单链表是一种简单的链表结构，每个节点包含一个数据元素和一个指向下一个节点的指针。最后一个节点的指针指向空值。

单链表可以用以下结构体来表示：

template<typename T>
struct Node {
    T data;
    Node<T>* next;
};

其中，data 表示节点存储的数据，next 表示指向下一个节点的指针。

单链表的优点是插入和删除操作非常高效，时间复杂度为 $O(1)$。缺点是难以直接访问任意位置的节点，需要从头节点开始遍历。以下是一个简单的单链表示例，实现了插入、删除和遍历操作：

template<typename T>
class SinglyLinkedList {
public:
    SinglyLinkedList(); // 构造函数
    bool isEmpty() const; // 判断链表是否为空
    int length() const; // 返回链表的长度
    bool insert(int index, const T& value); // 在指定位置插入元素
    bool remove(int index); // 删除指定位置的元素
    void clear(); // 清空链表
    void traverse(void (*visit)(const T&)); // 遍历链表并对每个元素执行visit函数
    ~SinglyLinkedList(); // 析构函数
private:
    Node<T>* head; // 链表头节点
    int size; // 链表长度
};

双向链表（Doubly Linked List）

双向链表是在单链表的基础上，每个节点除了包含一个指向下一个节点的指针之外，还包含一个指向上一个节点的指针。这样就可以实现双向遍历。

双向链表可以用以下结构体来表示：

template<typename T>
struct Node {
    T data;
    Node<T>* prev;
    Node<T>* next;
};

其中，prev 表示指向上一个节点的指针，next 表示指向下一个节点的指针。

双向链表的优点是可以双向遍历，缺点是需要额外的指针存储上一个节点的信息，占用更多的内存空间。以下是一个简单的双向链表示例，实现了插入、删除和遍历操作：

template<typename T>
class DoublyLinkedList {
public:
    DoublyLinkedList(); // 构造函数
    bool isEmpty() const; // 判断链表是否为空
    int length() const; // 返回链表的长度
    bool insert(int index, const T& value); // 在指定位置插入元素
    bool remove(int index); // 删除指定位置的元素
    void clear(); // 清空链表
        void traverse(void (visit)(const T&)); // 遍历链表并对每个元素执行visit函数
        void traverseReverse(void (visit)(const T&)); // 反向遍历链表并对每个元素执行visit函数
        ~DoublyLinkedList(); // 析构函数
private:
        Node<T> head; // 链表头节点
        Node<T> tail; // 链表尾节点
        int size; // 链表长度
};

### 循环链表（Circular Linked List）

循环链表是一种特殊的链表结构，最后一个节点的指针不是空值，而是指向头节点，形成一个循环。

循环链表可以用以下结构体来表示：

```c++
template<typename T>
struct Node {
    T data;
    Node<T>* next;
};

其中，data 表示节点存储的数据，next 表示指向下一个节点的指针。

循环链表的优点是可以像双向链表一样双向遍历，而且可以循环遍历，缺点是难以直接访问任意位置的节点，需要从头节点开始遍历。以下是一个简单的循环链表表示例，实现了插入、删除和遍历操作：

template<typename T>
class CircularLinkedList {
public:
    CircularLinkedList(); // 构造函数
    bool isEmpty() const; // 判断链表是否为空
    int length() const; // 返回链表的长度
    bool insert(int index, const T& value); // 在指定位置插入元素
    bool remove(int index); // 删除指定位置的元素
    void clear(); // 清空链表
    void traverse(void (*visit)(const T&)); // 遍历链表并对每个元素执行visit函数
    ~CircularLinkedList(); // 析构函数
private:
    Node<T>* head; // 链表头节点
    int size; // 链表长度
};

需要注意的是，在循环链表中，空链表和非空链表的判断需要根据头节点指针是否为空来判断，而不是最后一个节点的指针是否为空。