C++ 循环链表学习笔记教程

1. 循环链表的概念

循环链表是一种特殊的链表结构，其特点是最后一个节点的指针不是指向空值（NULL），而是指向链表的头节点，形成一个环形结构。这种结构使得链表的遍历可以从任意节点开始，并能方便地回到起始节点。

循环链表可以是单向的，也可以是双向的：

• 单向循环链表：每个节点只有一个指针，指向后继节点，尾节点指向头节点
• 双向循环链表：每个节点有两个指针，分别指向前驱和后继节点，头节点的前驱指向尾节点，尾节点的后继指向头节点

2. 单向循环链表的节点结构

template <typename T>
struct Node {
    T data;          // 节点存储的数据
    Node* next;      // 指向后继节点的指针
    
    // 构造函数
    Node(T val) : data(val), next(nullptr) {}
};

3. 单向循环链表的基本操作

3.1 循环链表类的定义

template <typename T>
class CircularLinkedList {
private:
    Node<T>* head;   // 头指针
    int size;        // 链表长度
    
public:
    // 构造函数
    CircularLinkedList() : head(nullptr), size(0) {}
    
    // 析构函数
    ~CircularLinkedList() {
        clear();
    }
    
    // 基本操作函数声明
    void push_back(T val);    // 在链表尾部插入元素
    void push_front(T val);   // 在链表头部插入元素
    void insert(int pos, T val);  // 在指定位置插入元素
    void remove(T val);       // 删除指定值的节点
    int find(T val);          // 查找指定值的位置
    void print();             // 打印链表
    bool isEmpty();           // 判断链表是否为空
    int getSize();            // 获取链表长度
    void clear();             // 清空链表
};

3.2 基本操作的实现

#include <iostream>
using namespace std;

// 节点结构定义
template <typename T>
struct Node {
    T data;          // 节点存储的数据
    Node* next;      // 指向后继节点的指针
    
    // 构造函数
    Node(T val) : data(val), next(nullptr) {}
};

// 循环链表类定义
template <typename T>
class CircularLinkedList {
private:
    Node<T>* head;   // 头指针
    int size;        // 链表长度
    
public:
    // 构造函数
    CircularLinkedList() : head(nullptr), size(0) {}
    
    // 析构函数
    ~CircularLinkedList() {
        clear();
    }
    
    // 判断链表是否为空
    bool isEmpty() {
        return size == 0;
    }
    
    // 获取链表长度
    int getSize() {
        return size;
    }
    
    // 在链表尾部插入元素
    void push_back(T val) {
        Node<T>* newNode = new Node<T>(val);
        
        if (isEmpty()) {
            head = newNode;
            head->next = head;  // 自己指向自己
        } else {
            Node<T>* current = head;
            // 找到最后一个节点
            while (current->next != head) {
                current = current->next;
            }
            current->next = newNode;
            newNode->next = head;  // 新节点指向头节点，形成循环
        }
        size++;
    }
    
    // 在链表头部插入元素
    void push_front(T val) {
        Node<T>* newNode = new Node<T>(val);
        
        if (isEmpty()) {
            head = newNode;
            head->next = head;  // 自己指向自己
        } else {
            Node<T>* current = head;
            // 找到最后一个节点
            while (current->next != head) {
                current = current->next;
            }
            newNode->next = head;  // 新节点指向原头节点
            current->next = newNode;  // 最后一个节点指向新节点
            head = newNode;  // 更新头节点
        }
        size++;
    }
    
    // 在指定位置插入元素（位置从0开始）
    void insert(int pos, T val) {
        if (pos < 0 || pos > size) {
            cout << "位置无效！" << endl;
            return;
        }
        
        if (pos == 0) {
            push_front(val);
            return;
        }
        
        if (pos == size) {
            push_back(val);
            return;
        }
        
        Node<T>* newNode = new Node<T>(val);
        Node<T>* current = head;
        
        // 移动到pos-1位置
        for (int i = 0; i < pos - 1; i++) {
            current = current->next;
        }
        
        newNode->next = current->next;
        current->next = newNode;
        size++;
    }
    
    // 删除指定值的节点
    void remove(T val) {
        if (isEmpty()) {
            cout << "链表为空，无法删除！" << endl;
            return;
        }
        
        Node<T>* current = head;
        Node<T>* prev = nullptr;
        
        // 查找要删除的节点
        do {
            if (current->data == val) {
                // 找到要删除的节点
                if (prev == nullptr) {  // 要删除的是头节点
                    // 找到最后一个节点
                    Node<T>* last = head;
                    while (last->next != head) {
                        last = last->next;
                    }
                    
                    if (head == head->next) {  // 只有一个节点
                        delete head;
                        head = nullptr;
                    } else {
                        last->next = head->next;
                        delete head;
                        head = last->next;
                    }
                } else {  // 要删除的是中间节点
                    prev->next = current->next;
                    delete current;
                }
                size--;
                cout << "已删除值为 " << val << " 的节点" << endl;
                return;
            }
            prev = current;
            current = current->next;
        } while (current != head);
        
        cout << "未找到值为 " << val << " 的节点" << endl;
    }
    
    // 查找指定值的位置（位置从0开始）
    int find(T val) {
        if (isEmpty()) {
            return -1;
        }
        
        Node<T>* current = head;
        int pos = 0;
        
        do {
            if (current->data == val) {
                return pos;
            }
            current = current->next;
            pos++;
        } while (current != head);
        
        return -1;  // 未找到
    }
    
    // 打印链表
    void print() {
        if (isEmpty()) {
            cout << "链表为空！" << endl;
            return;
        }
        
        Node<T>* current = head;
        cout << "循环链表内容：";
        do {
            cout << current->data << " -> ";
            current = current->next;
        } while (current != head);
        cout << "（回到头部 " << head->data << "）" << endl;
    }
    
    // 清空链表
    void clear() {
        if (isEmpty()) {
            return;
        }
        
        Node<T>* current = head->next;
        Node<T>* nextNode;
        
        // 逐个删除节点
        while (current != head) {
            nextNode = current->next;
            delete current;
            current = nextNode;
        }
        
        // 删除头节点
        delete head;
        head = nullptr;
        size = 0;
    }
};

// 测试函数
int main() {
    // 创建一个整数类型的循环链表
    CircularLinkedList<int> clist;
    
    // 测试插入操作
    clist.push_back(10);
    clist.push_back(20);
    clist.push_front(5);
    clist.insert(2, 15);
    
    clist.print();  // 应该输出: 5 -> 10 -> 15 -> 20 -> （回到头部 5）
    
    // 测试查找操作
    int pos = clist.find(15);
    if (pos != -1) {
        cout << "元素 15 的位置是: " << pos << endl;  // 应该输出 2
    }
    
    // 测试删除操作
    clist.remove(10);
    clist.print();  // 应该输出: 5 -> 15 -> 20 -> （回到头部 5）
    
    // 测试链表信息
    cout << "链表长度: " << clist.getSize() << endl;  // 应该输出 3
    cout << "链表是否为空: " << (clist.isEmpty() ? "是" : "否") << endl;  // 应该输出 否
    
    // 清空链表
    clist.clear();
    clist.print();  // 应该输出: 链表为空！
    
    return 0;
}

4. 循环链表的工作原理

循环链表的核心特性是尾节点的next指针指向头节点，形成一个闭环。这种结构带来了一些特殊的性质：

1. 从任意节点出发都能遍历整个链表
2. 不需要额外的指针来标识链表的尾部，头节点的前驱就是尾节点
3. 适合实现环形队列等数据结构

5. 循环链表与普通链表的区别

6. 循环链表的应用场景

1. 环形缓冲区（Circular Buffer）：用于数据缓存，当缓冲区满时覆盖旧数据
2. 约瑟夫问题（Josephus Problem）：经典的循环链表应用，解决环形排列中的淘汰问题
3. 资源调度：如操作系统中的进程调度，循环轮转法
4. 音乐播放列表：播放到最后一首后自动回到第一首

7. 循环链表的优缺点

优点：

• 从任意节点都能访问到所有节点
• 可以高效地实现首尾相连的操作
• 适合需要循环遍历的数据结构

缺点：

• 实现稍复杂，需要注意循环终止条件
• 容易出现死循环（如果操作不当）
• 相比普通链表，需要更多的注意事项来避免错误

8. 注意事项

1. 遍历循环链表时，必须使用do-while循环或检查是否回到头节点来避免死循环
2. 插入和删除节点时，要特别注意维护循环特性
3. 销毁链表时，需要正确处理循环关系，避免内存泄漏
4. 在处理空链表时要进行特殊判断

通过以上学习，你应该对C++循环链表有了全面的了解。循环链表虽然实现上比普通链表稍复杂，但在特定场景下能提供更高效的操作。建议多进行代码练习，加深对循环链表的理解和应用能力。