圆形链表的基本概念

什么是圆形链表？

圆形链表（Circular Linked List）是一种链表结构，区别于普通线性链表在最后一个节点没有指向null或空指针，而是指向链表中的某个有效节点。这种结构使得链表形成一个闭环。

圆形链表的实现方式

数据结构定义

为了实现圆形链表，首先需要定义链表节点的数据结构。每个节点不仅包含数据字段（data），还包含一个指向下一个节点的指针（next）。

struct Node {
    int data;
    Node* next;
};

基本操作

初始化

初始化时通常会创建头节点，并将其 next 指向自身，形成环形链表。

Node* createCircularList() {
    Node *head = new Node();
    head->data = 0; // 或其他初始值
    head->next = head;
    return head;
}

插入节点

在指定位置插入新节点。对于圆形链表，通常是在尾部插入。

void insertNode(Node *head, int data) {
    Node *newNode = new Node();
    newNode->data = data;

    if (head == nullptr) { // 如果链表为空
        head = newNode;
        newNode->next = head;  // 新节点指向自身形成环
    } else {
        Node *current = head;
        while (current->next != head) {
            current = current->next;
        }
        current->next = newNode;
        newNode->next = head;
    }
}

删除节点

删除指定位置的节点。由于是闭环链表，需要特别处理头节点。

void deleteNode(Node *head, int data) {
    if (head == nullptr) return; // 空链表直接返回

    Node *current = head;
    Node *prev = nullptr;

    while ((current->data != data && current->next != head)) {
        prev = current;
        current = current->next;
    }

    if (current->data == data) { // 找到了数据
        if (current == head) { // 如果要删除的是头节点
            Node *tail = head;
            while (tail->next != head) {
                tail = tail->next;
            }
            tail->next = current->next;  // 前一个尾部节点指向下一个节点
            head = current->next;
        } else {  // 正常删除节点
            prev->next = current->next;
        }
    }
}

遍历链表

遍历时，从头节点开始，按顺序访问每个节点。

void traverse(Node *head) {
    Node* temp = head;
    if (head != nullptr) {
        do {
            cout << temp->data << " -> ";
            temp = temp->next;
        } while (temp != head);  // 继续循环直到回到头节点
        cout << "head";
    }
}

圆形链表的应用

• 环检测：可以用来检测图中是否存在环。
• 内存管理：在某些场景下用于对象的管理，比如缓存机制等。
• 时间序列：模拟时间循环，如一天24小时循环。

通过上述实现和应用说明，我们可以看出圆形链表不仅是一种特殊的链式存储结构，还具有独特的应用场景。