循环链表是一种数据结构，其中最后一个节点的next连接回到第一个节点，形成一个循环。此结构允许连续遍历而不会中断。
循环链表对于日程安排和音乐播放列表等任务特别有用，这允许播放完毕后回到第一首继续播放。
在这小节中，我们将介绍循环链表的基础知识、如何使用它们、它们的优点和缺点以及它们的应用。

什么是循环链表？

循环链表是一种特殊类型的链表，其中所有节点都连接起来形成一个环。
与我们前面讲到的链表不同的是，循环链表中的最后一个节点的next指向第一个节点。这意味着当遍历到尾部时可以继续向头部遍历。

循环链表是从单链表和双链表扩展出来的，因此，循环链表基本只有这两种类型。

循环单链表

在循环单链表中，每个节点只有一个指针，称为next指针。最后一个节点的next指针指向第一个节点，这样就形成了一个环。在循环单链表中，我们只能沿一个方向遍历链表。

循环单链表结构

数据结构

#include <stdio.h>
#include <stdlib.h>
#define ElemType int
typedef struct LNode {
  int data;
  struct LNode* next;
} LNode, *LinkList;
LNode* pTemp = (LNode*)malloc(sizeof(LNode));
pTemp->data = e;
pTemp->next = p->next; // 将新节点的next指向p的下一个节点
p->next = pTemp; // 更新p的next指向新节点，完成插入操
// 完整代码：https://totuma.cn

data：数据域，也是节点的值
next：指针域，指向下一个结点的指针

在上面的定义中，每个节点都有data数据域和next指针域，和普通的单链表结构一模一样，唯一区别就是当我们为循环链表创建多个节点时，我们只需要将最后一个节点连接回第一个节点即可。

循环单链表的基本操作实现

创建循环单链表

插入是链表中的基本操作。和普通单链表的唯一区别是将最后一个节点的next连接到第头结点。
插入大概可以分为以下三种情况

1.在空链表中插入新结点

在空链表中插入新结点

这里使用的是带头结点的单链表来实现循环链表，所以链表空的条件是头结点的next指向头结点，即头结点自己指向自己。
在空的循环链表中插入一个节点，需要创建一个新结点，将其next指针指向头结点，以达到循环的目的。

2.在链表中部插入新结点

在链表中部插入新结点

和普通单链表操作一样，在中部插入结点并没有改变尾结点next的指向。

3.在链表尾部插入新结点

在链表尾部插入新结点

#include <stdio.h>
#include <stdlib.h>
#define ElemType int
typedef struct LNode {
  int data;
  struct LNode* next;
} LNode, *LinkList;
LNode* pTemp = (LNode*)malloc(sizeof(LNode));
pTemp->data = e;
pTemp->next = p->next; // 将新节点的next指向p的下一个节点
p->next = pTemp; // 更新p的next指向新节点，完成插入操
// 完整代码：https://totuma.cn

上面三种情况，都可以统一为同一操作：
1.找到待插入位置的前驱结点，即p；
2.创建新结点pTemp；
3.使pTemp的next指向p的next；
（如果是空链表，那么p的next指向头结点本身。如果是在末尾插入，p的next同样也是指向头结点）
4.使p的next指向pTemp；

按位序插入结点 | 可视化完整可视化

2.4 循环单链表详解 - 线性表教程使用动画可视化你的代码

数据结构与算法可视化学习：线性表之链表详解

在计算机科学中，数据结构是组织、管理和存储数据的基础。对于学习数据结构和算法的初学者来说，链表（Linked List）是一个核心且必须掌握的概念。与数组不同，链表是一种线性表，但它不要求物理上连续的内存空间，而是通过“指针”将一系列节点串联起来。本文将从零开始，详细解析链表的原理、特点、分类、应用场景，并介绍如何利用数据结构可视化学习平台直观地理解链表的动态操作过程。

什么是线性表？链表与数组的区别

线性表是最基本的数据结构之一，它表示一组数据元素的线性序列。常见的线性表实现方式有两种：顺序存储结构（如数组）和链式存储结构（如链表）。

数组在内存中占用一块连续的空间，通过下标可以直接访问任意元素，时间复杂度为O(1)。但数组的插入和删除操作需要移动大量元素，效率较低（O(n)），并且数组的大小在建时固定，扩展不便。

链表则不同。链表中的每个元素称为一个“节点”（Node），每个节点包含两部分：数据域（存储实际数据）和指针域（存储下一个节点的地址）。链表通过指针将节点链接起来，因此不需要连续内存。链表的插入和删除操作只需修改指针指向，时间复杂度为O(1)（前提是已知插入或删除位置），但访问某个元素必须从头节点开始遍历，时间复杂度为O(n)。

链表的核心原理：节点与指针

理解链表的关键在于理解“节点”和“指针”的概念。假设我们有一个节点类，通常包含两个属性：val（数据）和next（指向下一个节点的引用）。例如，一个存储整数1、2、3的链表，其结构如下：

节点1 (val=1, next→节点2) → 节点2 (val=2, next→节点3) → 节点3 (val=3, next→null)

最后一个节点的next指向null，表示链表结束。链表的第一个节点称为头节点（Head），它是访问整个链表的入口。如果没有头节点，整个链表就会丢失。

链表的分类

根据指针的结构，链表可以分为以下几种常见类型：

单向链表

这是最简单的链表形式。每个节点只包含一个指向下一个节点的指针。遍历只能从头节点开始，单向进行。单向链表的优点是结构简单，内存占用少；缺点是无法反向查找。

双向链表

双向链表的每个节点包含两个指针：一个指向前一个节点（prev），一个指向后一个节点（next）。这使得链表可以双向遍历。双向链表在插入和删除操作中更加灵活，但每个节点需要额外的内存存储前驱指针。

循环链表

循环链表是一种特殊的链表，其最后一个节点的指针指向头节点，形成一个环。循环链表可以从任意节点出发遍历整个链表，适合需要循环处理数据的场景，如操作系统中的进程调度。

静态链表

静态链表使用数组来模拟链表的链式结构。数组中的每个元素除了存储数据外，还存储一个“游标”来表示下一个元素的数组下标。这种结构在早期编程语言中用于实现链表功能，现在较少使用。

链表的基本操作

链表的核心操作包括插入、删除、查找和遍历。下面我们详细分析这些操作的原理和复杂度。

插入操作

在链表中插入一个新节点，通常需要以下步骤：

1. 创建新节点，并设置其数据。

2. 将新节点的next指针指向插入位置的后继节点。

3. 将插入位置的前驱节点的next指针指向新节点。

如果是在头节点之前插入（即插入为新的头节点），只需将新节点的next指向原头节点，然后更新头节点引用即可。插入操作的时间复杂度为O(1)，前提是已经知道插入位置的前驱节点。

删除操作

删除一个节点同样需要修改指针：

1. 找到待删除节点的前驱节点。

2. 将前驱节点的next指针指向待删除节点的后继节点。

3. （可选）释放待删除节点的内存。

删除操作的时间复杂度也是O(1)，前提是已知前驱节点。如果不知道前驱节点，则需要先遍历查找，此时时间复杂度为O(n)。

查找操作

由于链表不支持随机访问，查找一个特定值必须从头节点开始逐个遍历，直到找到目标节点或到达链表末尾。查找操作的平均时间复杂度为O(n)。

遍历操作

遍历链表就是从头节点开始，通过next指针依次访问每个节点，直到遇到null。遍历的时间复杂度为O(n)。

链表的优缺点分析

任何数据结构都有其适用场景，链表也不例外。下面总结链表的主要优缺点。

优点

1. 动态大小：链表可以在运行时动态增加或删除节点，不需要预先分配固定大小的内存。

2. 高效的插入和删除：在已知位置的情况下，链表的插入和删除操作仅需修改指针，时间复杂度为O(1)，而数组需要移动大量元素。

3. 内存利用率高：链表不需要连续内存，可以充分利用碎片化的内存空间。

缺点

1. 访问效率低：链表不支持随机访问，要访问第i个元素必须从头遍历，时间复杂度为O(n)。

2. 额外内存开销：每个节点需要额外的指针域存储地址，对于大型数据集，这部分开销不可忽视。

3. 缓存不友好：由于节点在内存中不连续，CPU缓存命中率较低，可能影响性能。

4. 操作复杂性：链表的插入和删除操作需要小心处理指针，容易出现指针悬空或内存泄漏等错误。

链表的典型应用场景

链表在许多计算机系统和算法中都有广泛应用。以下是一些典型的应用场景：

实现栈和队列

链表可以用来实现动态的栈和队列。例如，使用单向链表实现栈时，头节点作为栈顶，插入和删除都在头节点进行，时间复杂度为O(1)。使用双向链表实现队列时，头节点作为队首，尾节点作为队尾，入队和出队操作都非常高效。

操作系统的内存管理

在操作系统中，空闲内存块通常使用链表来管理。每个空闲块是一个节点，通过指针链接在一起。当进程申请内存时，系统从链表中分配一个合适的块；当进程释放内存时，系统将块重新加入链表。

哈希表的链地址法

在哈希表中，当多个键映射到同一个哈希桶时，可以使用链表来存储这些冲突的键值对。这就是链地址法（Separate Chaining）。每个桶对应一个链表，插入和删除操作都在链表上进行。

大数运算

在实现大整数运算（如加法、乘法）时，可以使用链表来存储每一位数字。例如，一个100位的整数可以用一个100个节点的链表表示，每个节点存储一位数字。这样，运算过程可以逐位进行，方便处理进位。

图的邻接表表示

在图的存储中，邻接表是一种常用的表示方法。对于每个顶点，使用一个链表来存储其所有邻接顶点。这种表示方式对于稀疏图非常高效，节省内存。

LRU缓存淘汰算法

LRU（Least Recently Used）缓存算法通常使用双向链表和哈希表实现。双向链表用于维护数据的访问顺序，最近访问的数据放在头部，最久未访问的数据放在尾部。当缓存满时，删除尾部的数据。

链表与数组的性能对比

为了帮助学习者更好地选择数据结构，下面从多个维度对比链表和数组：

访问速度：数组O(1) vs 链表O(n)

插入/删除（已知位置）：数组O(n) vs 链表O(1)

插入/删除（未知位置）：数组O(n) vs 链表O(n)（因为需要先查找）

内存占用：数组连续，无额外开销；链表每个节点有指针开销

内存分配：数组静态分配；链表动态分配

缓存友好性：数组友好；链表不友好

在实际开发中，如果主要操作是随机访问，应选择数组；如果主要操作是频繁的插入和删除，且数据大小不确定，应选择链表。

如何利用可视化平台学习链表

对于初学者来说，链表中的指针操作和节点链接可能比较抽象。传统的文字和图片讲解往往难以直观展示动态过程。数据结构可视化学习平台正是为了解决这一痛点而设计的。这些平台通过图形化界面，将链表的结构和操作过程实时呈现出来，帮助学习者“看到”数据在内存中是如何组织和变化的。

可视化平台的核心功能

1. 节点可视化：每个节点以矩形或圆形表示，内部显示数据值，节点之间用箭头表示指针链接。头节点和尾节点有特殊标记。

2. 操作动画：当用户执行插入、删除或查找操作时，平台会以动画形式展示指针的修改过程。例如，插入一个新节点时，会先显示新节点出现，然后看到指针从原节点断开并指向新节点。

3. 代码同步：许多可视化平台支持代码和图形同步显示。用户编写或查看代码时，每一步操作都会在图形界面上高亮对应的节点和指针变化。这有助于将抽象代码与具体数据结构联系起来。

4. 交互式操作：用户可以通过点击按钮或拖拽节点来手动执行操作。例如，点击“插入节点”按钮，输入数据值，然后观察链表的变化。这种交互式学习方式大大增强了理解深度。

5. 多种链表类型支持：平台通常支持单向链表、双向链表、循环链表等多种类型，用户可以切换学习不同链表的差异。

6. 错误检测与提示：当用户执行非法操作（如访问空指针）时，平台会给出错误提示，帮助用户理解为什么不能这样做。

使用可视化平台的学习方法

为了更好地利用可视化平台学习链表，建议按照以下步骤进行：

第一步：理解基本概念

在开始操作之前，先阅读平台提供的链表概念介绍，了解节点、指针、头节点等基本术语。

第二步：观察初始化

创建一个空链表，观察头指针的指向。然后依次插入几个节点，观察链表是如何增长的。注意每次插入后指针的变化。

第三步：手动执行操作

不要使用平台的自动演示功能，而是手动点击按钮执行每一步操作。例如，在插入节点时，先选择插入位置，然后观察平台显示的前驱节点和后继节点。这样能加深对操作步骤的理解。

四步：结合代码学习

如果平台支持代码同步，打开代码窗口。观察代码中的每一行对图形界面中的哪个动作。例如，当代码执行newNode.next = current.next时，看图形界面中箭头是如何变化的。

第五步：尝试错误操作

故意执行一些错误操作，比如在空链表中删除节点，或者访问超出范围的索引。观察平台的错误提示，理解这些操作为什么非法。

第六步：挑战练习题

许多可视化平台内置了练习题，例如“反转链表”、“检测环”等。利用可视化工具一步步推导解题思路，而不是直接看答案。这能有效训练算法思维。

可视化平台的学习优势

相比传统学习方式，使用可视化平台学习链表具有以下显著优势：

降低认知负担：初学者不需要在脑中想象指针的指向和变化，可视化平台将抽象概念具象化，降低了理解难度。

即时反馈：每次操作都能立即看到结果，如果操作错误也能马上发现。这种即时反馈有助于快速纠正错误认知。

加深记忆：视觉记忆往往比文字记忆更持久。通过观察动画和图形，学习者对链表操作的理解更加深刻。

培养调试能力：当自己编写链表代码出现bug时，可以借助可视化平台模拟代码执行过程，快速定位问题所在。

适合多种学习风格：无论是视觉型学习者还是动手型学习者，都能从可视化平台中找到适合自己的学习方式。

常见链表算法与可视化

除了基本操作，链表相关的常见算法也可以通过可视化平台进行学习：

反转链表

反转链表是面试中的高频题。通过可视化，可以清晰看到三个指针（prev、current、next）如何逐步移动，将每个节点的next指向反转。学习者可以观察从原始链表到反转后链表的完整过程。

检测环

使用快慢指针法检测链表是否有环。可视化平台会同时显示快指针（每次移动两步）和慢指针（每次移动一步）的移动轨迹。当两者相遇时，平台会高亮显示相遇点，直观展示算法的正确性。

合并两个有序链表

合并两个升序链表时，可视化平台会显示两个链表头节点，以及一个虚拟头节点。每一步比较两个头节点的值，将较小的节点接入结果链表，并移动指针。整个过程如同“拉链”一样清晰可见。

删除倒数第N个节点

使用双指针法删除倒数第N个节点。可视化平台会显示两个指针之间的间隔，当快指针到达末尾时，慢指针正好指向待删除节点的前驱。这种可视化方式让“快慢指针”技巧变得非常直观。

链表学习的常见误区与可视化纠正

许多学习者在初学链表时容易陷入一些误区，可视化平台可以帮助纠正这些错误：

误区一：认为链表节点是连续存放的

通过可视化，学习者可以看到节点在图形界面中虽然排列整齐，但实际内存地址是分散的。平台可以在节点上显示内存地址（或编号），让学习者明白链表“逻辑连续，物理离散”的特点。

误区二：混淆节点本身和节点指针

可视化平台用不同的形状或颜色区分节点和指针。例如，节点用矩形表示，指针用箭头表示。学习者可以清楚看到，修改指针并不会改变节点本身的数据。

误区三：忘记处理边界情况

在插入或删除头节点或尾节点时，可视化平台会特别高亮显示边界情况。例如，删除头节点时，平台会显示头指针如何更新。这有助于学习者养成考虑边界情况的习惯。

误区四：认为空链表没有头指针

可视化平台会显示空链表的头指针指向null，而不是什么都不显示。这让学习者明白即使链表为空，头指针变量仍然存在。

总结

链表是数据结构学习中的基石，它体现了“链式存储”的核心思想。通过本文的详细介绍，相信读者已经对链表的原理、特点、操作和应用有了全面的认识。链表虽然简单，但其中蕴含的指针操作和动态内存管理思想，是后续学习更复杂数据结构（如树、图）的基础。

对于初学者来说，仅仅阅读文字描述是远远不够的。强烈建议利用数据结构可视化学习平台进行交互式学习。这些平台将抽象的数据结构转化为直观的图形，将静态的文字转化为动态的动画，让学习者能够“看见”数据在内存中的流动。通过动手操作、观察动画、结合代码，学习者可以快速掌握链表的精髓，为后续的算法学习打下坚实基础。

最后，记住一句话：数据结构是程序的骨架，算法是程序的灵魂。而链表，正是你构建这个骨架的第一步。利用好可视化工具，让学习过程变得有趣而高效。

为什么要使用头插法创建，而不是尾插法创建？
如果我们要在链表末尾进行插入，那么需要先遍历整个链表找到尾结点，或者使用一个变量记录尾结点的。
而且每次都需要改变尾结点的next指向头结点，以达到循环。
而我们使用头插法，无论链表是否为空，代码都是统一不变，不需要做其他判断。

按位序删除结点

删除操作和普通单链表相同。主要区别在于我们需要确保删除后链表保持循环。

要从循环链表中删除特定的结点，首先需要检查删除的位序是否满足条件。
找到待删除结点的前驱结点即p结点
找到前驱结点p后，使用q记录为待删除结点
修改前驱结点p的next指向待删除结点q的next，即跳过q结点并将其删除

仅有一个结点时，循环指向头结点

删除尾部结点，更新链表循环

删除中间结点

💡 提示
对于带头结点的链表，上面三种情况都可以统一为同一种操作代码

按位序删除结点 | 可视化完整可视化