循环链表

为什么需要循环链表

普通链表（单链表或双链表）的最后一个结点的指针域为 NULL，遍历到表尾就必须停止。如果需要从表中任意一个结点出发，访问到表中所有其他结点，普通链表无法做到。

循环链表将尾结点的指针指回头部，使整条链表形成一个环。这样从任意结点出发沿链遍历，都能回到起点、访问到所有结点。典型应用场景包括：

操作系统中的轮转调度（Round-Robin）
经典的约瑟夫问题（Josephus Problem）
需要反复循环处理的数据缓冲区

核心思想

循环链表的核心特点：

循环单链表：尾结点的 next 指针不为 NULL，而是指向头结点（带头结点时）或第一个数据结点（不带头结点时）
循环双链表：在循环单链表的基础上，头结点的 prior 指向尾结点，尾结点的 next 指向头结点，形成双向闭合环
判空条件不同：普通链表判 p->next == NULL；循环链表判 p->next == L（是否回到头结点）

循环单链表结构示意：

┌───┬───┐   ┌───┬───┐   ┌───┬───┐
│ L │ ──┼──→│ a₁│ ──┼──→│ a₂│ ──┼──┐
└───┴───┘   └───┴───┘   └───┴───┘  │
  ↑                                 │
  └─────────────────────────────────┘

循环双链表结构示意：

       ┌──────────────────────────────────┐
       ↓                                  │
  ┌───┬───┐   ┌───┬───┐   ┌───┬───┐     │
  │ L │   │←──│ a₁│   │←──│ a₂│   │     │
  │   │ ──┼──→│   │ ──┼──→│   │ ──┼─────┘
  └───┴───┘   └───┴───┘   └───┴───┘

循环链表 vs 普通链表：终止条件对比

对比项	普通链表	循环链表
尾结点指针	`next = NULL`	`next = L`（指向头结点）
判空条件	`L->next == NULL`	`L->next == L`
遍历终止	`p != NULL`	`p != L`

交互可视化

通过下方的交互动画，你可以逐步观察循环链表的执行过程：

加载可视化中...

操作详解

循环单链表

结点定义

typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

初始化（带头结点）

初始化时，头结点的 next 指向自身，形成空的循环链表。

bool InitList(LinkList *L) {
    *L = (LNode *)malloc(sizeof(LNode));
    if (*L == NULL) return false;
    (*L)->next = *L;  // 指向自身，而非 NULL
    return true;
}

判空

bool Empty(LinkList L) {
    return L->next == L;  // 注意：不是 L->next == NULL
}

遍历

与普通单链表的关键区别在于终止条件：不再判 p != NULL，而是判 p != L（是否回到头结点）。

void Traverse(LinkList L) {
    LNode *p = L->next;   // 第一个数据结点
    while (p != L) {       // 回到头结点时停止
        printf("%d ", p->data);
        p = p->next;
    }
}

在第 i 个位置插入

关键步骤与普通单链表相同，找到第 i-1 个结点后执行插入。唯一区别是查找过程中终止条件从 p != NULL 变为 p != L。

bool ListInsert(LinkList L, int i, int e) {
    if (i < 1) return false;
    LNode *p = L;
    int j = 0;
    while (p->next != L && j < i - 1) {  // 终止条件不同
        p = p->next;
        j++;
    }
    if (j < i - 1) return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) return false;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

删除第 i 个结点

bool ListDelete(LinkList L, int i, int *e) {
    if (i < 1) return false;
    LNode *p = L;
    int j = 0;
    while (p->next != L && j < i - 1) {
        p = p->next;
        j++;
    }
    if (p->next == L || j > i - 1) return false;
    LNode *q = p->next;
    *e = q->data;
    p->next = q->next;
    free(q);
    return true;
}

尾指针的妙用

如果设置一个尾指针 rear 指向尾结点（而非头指针），则：

访问尾结点：rear，时间 O(1)
访问头结点：rear->next，时间 O(1)
访问第一个数据结点：rear->next->next，时间 O(1)

这在两个循环单链表的合并中特别有用，可以在 O(1) 时间内完成：

// 将 Lb 合并到 La 的尾部（均用尾指针表示）
LinkList Connect(LinkList La, LinkList Lb) {
    LNode *headA = La->next;  // 保存 La 的头结点
    La->next = Lb->next->next; // La 尾接 Lb 第一个数据结点
    free(Lb->next);            // 释放 Lb 的头结点
    Lb->next = headA;          // Lb 尾接 La 头结点
    return Lb;                 // 返回新的尾指针
}

循环双链表

结点定义

typedef struct DNode {
    int data;
    struct DNode *prior, *next;
} DNode, *DLinklist;

初始化（带头结点）

头结点的 prior 和 next 都指向自身。

bool InitDLinkList(DLinklist *L) {
    *L = (DNode *)malloc(sizeof(DNode));
    if (*L == NULL) return false;
    (*L)->prior = *L;  // 前驱指向自身
    (*L)->next = *L;   // 后继指向自身
    return true;
}

判空

bool Empty(DLinklist L) {
    return L->next == L;
}

遍历

void Traverse(DLinklist L) {
    DNode *p = L->next;
    while (p != L) {       // 回到头结点时停止
        printf("%d ", p->data);
        p = p->next;
    }
}

在结点 p 之后插入结点 s

与普通双链表的操作基本一致，但因为是循环结构，不需要特判 p 是否为尾结点——p->next 永远不会是 NULL。

bool InsertNextDNode(DNode *p, DNode *s) {
    if (p == NULL || s == NULL) return false;
    s->next = p->next;
    p->next->prior = s;  // 无需判空，循环链表中 p->next 必有效
    s->prior = p;
    p->next = s;
    return true;
}

删除结点 p 的后继结点

同样无需特判尾结点。但要注意不能删除头结点（即 p->next == L 时不可删除）。

bool DeleteNextDNode(DLinklist L, DNode *p) {
    if (p == NULL || p->next == L) return false;  // 后继是头结点则无法删除
    DNode *q = p->next;
    p->next = q->next;
    q->next->prior = p;
    free(q);
    return true;
}

循环双链表的优势

相比循环单链表，循环双链表可以在 O(1) 时间内找到任意结点的前驱，因此：

在某结点之前插入：O(1)
删除当前结点自身：O(1)（不需要找前驱）

这使得循环双链表成为实际工程中最常用的链表形式之一。

复杂度分析

循环单链表

操作	时间复杂度	说明
头插 / 头删	O(1)	在头结点之后操作
尾插（头指针）	O(n)	需遍历找到尾结点
尾插（尾指针）	O(1)	尾指针直接定位
按位查找	O(n)	需从头遍历
按值查找	O(n)	最坏遍历整个表
两表合并（尾指针）	O(1)	仅修改指针

循环双链表

操作	时间复杂度	说明
在已知结点后插入	O(1)	修改四个指针
在已知结点前插入	O(1)	利用 `prior` 直接定位
删除已知结点	O(1)	利用 `prior` 无需遍历
按位查找	O(n)	需从头遍历
按值查找	O(n)	最坏遍历整个表

空间复杂度：所有操作均为 O(1)，只需常数级辅助空间。

考研高频考点

⭐ 循环链表的判空条件：L->next == L（对比普通链表的 L->next == NULL）
⭐ 循环链表遍历终止条件：p != L（对比普通链表的 p != NULL）
⭐ 尾指针表示循环单链表的优势：O(1) 时间访问头尾结点、O(1) 时间合并两个循环链表
⭐ 约瑟夫问题（Josephus Problem）：n 个人围成一圈，从第 k 个人开始报数，报到第 m 个人出列，循环进行直到所有人出列。这是循环链表的经典应用，考研中常以算法设计题出现
⭐ 循环双链表插入、删除操作的指针修改顺序（选择题/代码填空题高频）
循环链表 vs 普通链表的适用场景对比
循环双链表中无需特判尾结点的原因分析

交互体验

前往完整可视化页面 →

巩固练习

刷题平台即将推出，敬请期待...

循环链表 ​

为什么需要循环链表 ​

核心思想 ​

循环链表 vs 普通链表：终止条件对比 ​

交互可视化 ​

操作详解 ​

循环单链表 ​

结点定义 ​

初始化（带头结点） ​

判空 ​

遍历 ​

在第 i 个位置插入 ​

删除第 i 个结点 ​

尾指针的妙用 ​

循环双链表 ​

结点定义 ​

初始化（带头结点） ​

判空 ​

遍历 ​

在结点 p 之后插入结点 s ​

删除结点 p 的后继结点 ​

循环双链表的优势 ​

复杂度分析 ​

循环单链表 ​

循环双链表 ​

考研高频考点 ​

相关文章

交互体验

巩固练习

循环链表

为什么需要循环链表

核心思想

循环链表 vs 普通链表：终止条件对比

交互可视化

操作详解

循环单链表

结点定义

初始化（带头结点）

判空

遍历

在第 i 个位置插入

删除第 i 个结点

尾指针的妙用

循环双链表

结点定义

初始化（带头结点）

判空

遍历

在结点 p 之后插入结点 s

删除结点 p 的后继结点

循环双链表的优势

复杂度分析

循环单链表

循环双链表

考研高频考点