7. 静态链表与循环链表：静态链表的概念与实现、循环链表、双向链表
好，咱们今天聊聊链表里几个“变种”。说实话，很多初学者学完单链表就觉得链表就那样了。其实不然。我在实际项目中遇到过不少场景，单链表根本搞不定，或者用起来特别别扭。这时候，静态链表、循环链表、双向链表就派上用场了。
你想想看，单链表有个硬伤——每个节点只知道下一个是谁，不知道上一个。而且它的内存是动态分配的，在某些嵌入式环境里，malloc 根本不能用。怎么办？嗯，这就是静态链表要解决的问题。
7.1 静态链表的概念与实现
静态链表，说白了就是用数组来模拟链表。每个数组元素既存数据，又存一个“游标”（cursor），指向下一个元素的下标。它既有数组的连续存储特性，又有链表的灵活插入删除能力。
我刚开始做嵌入式开发时，遇到过一块没有操作系统的芯片，堆空间小得可怜，动态分配根本不敢用。那时候就是用静态链表管理任务队列，稳得很。
7.1.1 结构定义
#define MAXSIZE 100
typedef struct {
int data; // 数据域
int cur; // 游标，指向下一个元素的下标
} StaticLinkList[MAXSIZE];这里有个关键点：cur 为 0 表示无后继，相当于单链表的 NULL。数组的第 0 个元素和第 1 个元素通常被特殊对待——第 0 个作为备用链表的头结点，第 1 个作为数据链表的头结点。
7.1.2 初始化与分配
void InitList(StaticLinkList space) {
for (int i = 0; i < MAXSIZE - 1; i++) {
space[i].cur = i + 1;
}
space[MAXSIZE - 1].cur = 0; // 最后一个元素的cur为0
}
int Malloc_SLL(StaticLinkList space) {
int i = space[0].cur; // 取备用链表的第一个空闲节点
if (i) {
space[0].cur = space[i].cur; // 备用链表头指针后移
}
return i;
}分配节点时，从备用链表头部取一个。释放节点时，把节点插回备用链表头部。这个思路我在管理内存池时也用过，本质是一样的。
核心思想：静态链表用数组下标代替指针，用游标代替 next 指针。插入删除不需要移动元素，只需要修改游标。
7.1.3 插入操作示例
Status ListInsert(StaticLinkList L, int i, int e) {
int j, k, l;
k = MAXSIZE - 1; // 数据链表头结点
if (i < 1 || i > ListLength(L) + 1) return ERROR;
j = Malloc_SLL(L);
if (j) {
L[j].data = e;
for (l = 1; l <= i - 1; l++) {
k = L[k].cur;
}
L[j].cur = L[k].cur;
L[k].cur = j;
return OK;
}
return ERROR;
}这段代码看着有点绕，其实逻辑和单链表一模一样——找到第 i-1 个节点，把新节点插进去。只不过这里的“指针”变成了数组下标。
避坑指南：我曾经在写静态链表删除操作时，忘了把被删节点归还到备用链表，结果跑了几次就“内存耗尽”了。记住：Free_SLL 一定要把节点插回备用链表头部，否则静态链表就是个一次性玩具。
7.2 循环链表
循环链表是什么？就是把单链表的尾节点的 next 指针指向头结点，形成一个环。为什么要这么做？
我记得有一次做音乐播放器的循环播放功能，用单链表实现时，每次播完最后一首都要手动把指针挪回头部，代码写得很别扭。换成循环链表后，一个指针从头走到尾，到尾自动回到头，完美契合循环播放的逻辑。
7.2.1 循环链表的优势
- 从任意节点出发都能遍历整个链表——单链表做不到这一点
- 尾节点访问头节点的时间复杂度为 O(1)——单链表需要 O(n)
- 适合需要循环访问的场景——比如轮询任务、约瑟夫环问题
7.2.2 循环链表的合并
两个循环链表的合并，我当年面试时被考过。代码其实很简洁：
LinkList Merge(LinkList LA, LinkList LB) {
LinkList p = LA->next; // 保存LA的头节点
LA->next = LB->next->next; // LA尾节点指向LB的第一个数据节点
free(LB->next); // 释放LB的头节点
LB->next = p; // LB尾节点指向LA的头节点
return LB; // 返回合并后的尾指针
}这里用尾指针表示循环链表，合并操作只需要修改两个指针，时间复杂度 O(1)。你想想看，如果是单链表，你得先遍历找到尾节点，那就 O(n) 了。
注意：循环链表的遍历结束条件不是 p == NULL，而是 p == head。很多初学者在这里翻车，写了个死循环还不知道。我曾经调试一个循环链表程序，卡了半小时才发现是判断条件写错了。
7.3 双向链表
双向链表，每个节点有两个指针——一个指向前驱，一个指向后继。说白了就是“前后都能走”。
为什么需要双向链表？我给你举个例子。你在文本编辑器里按“退格键”删除字符，如果用单链表存储文本，删除当前字符时你得先找到前一个节点，那就得从头遍历。双向链表直接通过 prior 指针就找到了，时间复杂度从 O(n) 降到 O(1)。
7.3.1 结构定义
typedef struct DuLNode {
int data;
struct DuLNode *prior; // 前驱指针
struct DuLNode *next; // 后继指针
} DuLNode, *DuLinkList;7.3.2 插入操作
Status ListInsert_DuL(DuLinkList L, int i, int e) {
DuLinkList p = GetElemP_DuL(L, i); // 找到第i个节点
if (!p) return ERROR;
DuLinkList s = (DuLinkList)malloc(sizeof(DuLNode));
s->data = e;
s->prior = p->prior;
s->next = p;
p->prior->next = s;
p->prior = s;
return OK;
}这里要注意指针修改的顺序。我习惯先处理新节点的两个指针，再处理前驱和后继的指针。顺序搞反了，链表就断了。
个人经验：双向链表删除操作时，记得检查 p == L 的情况（删除头结点）。我曾经在写一个双向链表实现 LRU 缓存时，忘了处理头结点删除，结果每次淘汰最久未使用的节点时都会崩溃。调试了一下午才发现。
7.4 三种链表的对比
| 特性 | 静态链表 | 循环链表 | 双向链表 |
|---|---|---|---|
| 存储方式 | 数组（连续） | 动态（不连续） | 动态（不连续） |
| 内存分配 | 静态（编译时确定） | 动态（运行时分配） | 动态（运行时分配） |
| 遍历方向 | 单向 | 单向（可循环） | 双向 |
| 查找前驱 | O(n) | O(n) | O(1) |
| 适用场景 | 嵌入式、无动态分配环境 | 循环播放、轮询、约瑟夫环 | 文本编辑、LRU缓存、需要频繁前后操作 |
这三种链表各有各的脾气。静态链表适合资源受限的环境，循环链表适合“绕圈”的场景，双向链表适合需要频繁前后移动的场景。选哪个，得看你的具体需求。
一句话总结：静态链表是“披着数组外衣的链表”，循环链表是“首尾相连的链表”，双向链表是“能进能退的链表”。理解它们的本质区别，比死记硬背代码重要得多。
好了，这一章的内容就到这儿。静态链表、循环链表、双向链表，每个都有自己独特的应用场景。我个人建议你动手实现一遍，尤其是静态链表的分配和回收逻辑，写一遍比看十遍都管用。遇到问题别怕，调试的过程才是真正学到东西的时候。