C++循环链表实现（从零开始掌握C++数据结构中的循环链表）

一、什么是循环链表？

普通单向链表的最后一个节点的指针为 nullptr，而循环链表的最后一个节点的指针指向第一个节点（即头节点），从而形成一个闭环。这样，你可以从任意节点出发，遍历整个链表。

二、循环链表的基本结构

我们首先定义一个节点结构体：

struct Node {    int data;          // 存储数据    Node* next;        // 指向下一个节点的指针    // 构造函数    Node(int value) : data(value), next(nullptr) {}};  

三、循环链表类的设计

我们将封装一个 CircularLinkedList 类，包含以下基本操作：

• 插入节点（尾插法）
• 删除节点
• 遍历打印
• 判断是否为空

class CircularLinkedList {private:    Node* head;public:    // 构造函数    CircularLinkedList() : head(nullptr) {}    // 析构函数（释放内存）    ~CircularLinkedList();    // 插入新节点（尾部插入）    void insert(int value);    // 删除指定值的节点    bool remove(int value);    // 打印所有节点    void display();    // 判断链表是否为空    bool isEmpty() const;};  

四、关键函数实现详解

1. 插入节点（尾插法）

在循环链表中插入新节点时，需要特别注意维护“环”的结构。

void CircularLinkedList::insert(int value) {    Node* newNode = new Node(value);    if (isEmpty()) {        head = newNode;        head->next = head;  // 自己指向自己，形成环    } else {        Node* temp = head;        // 找到尾节点（即指向 head 的节点）        while (temp->next != head) {            temp = temp->next;        }        temp->next = newNode;        newNode->next = head;  // 新节点指向头，保持循环    }}  

2. 遍历打印

由于是循环结构，不能用 while (current != nullptr)，否则会无限循环！

void CircularLinkedList::display() {    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;}  

3. 删除节点

删除时要小心处理头节点和尾节点的情况。

bool CircularLinkedList::remove(int value) {    if (isEmpty()) return false;    // 特殊情况：只有一个节点    if (head->data == value && head->next == head) {        delete head;        head = nullptr;        return true;    }    Node* current = head;    Node* prev = nullptr;    // 找到要删除的节点    do {        if (current->data == value) {            if (current == head) {                // 删除头节点：需要更新 head 并找到尾节点                Node* tail = head;                while (tail->next != head) tail = tail->next;                tail->next = head->next;                head = head->next;            }            prev->next = current->next;            delete current;            return true;        }        prev = current;        current = current->next;    } while (current != head);    return false; // 未找到}  

4. 析构函数（防止内存泄漏）

CircularLinkedList::~CircularLinkedList() {    if (isEmpty()) return;    Node* current = head;    Node* next;    do {        next = current->next;        delete current;        current = next;    } while (current != head);}  

五、完整使用示例

#include <iostream>int main() {    CircularLinkedList list;    list.insert(10);    list.insert(20);    list.insert(30);    std::cout << "当前链表: ";    list.display(); // 输出: 10 -> 20 -> 30 -> (回到头节点)    list.remove(20);    std::cout << "删除20后: ";    list.display(); // 输出: 10 -> 30 -> (回到头节点)    return 0;}  

六、总结

通过本教程，你已经掌握了C++循环链表实现的核心方法。循环链表虽然比普通链表稍复杂，但只要理解“尾指头”这一关键点，就能轻松驾驭。

无论是准备面试、完成课程作业，还是深入学习C++数据结构教程，循环链表都是必须掌握的基础技能。建议你动手敲一遍代码，加深理解！

如果你对链表编程入门感兴趣，还可以继续学习双向循环链表、跳表等高级结构。祝你编程愉快！

关键词提示：本教程涵盖 C++循环链表实现、C++数据结构教程、循环链表代码示例、链表编程入门 等核心知识点。