Appearance
静态链表
为什么需要静态链表
并非所有编程语言都支持指针（如 Basic、Java 等），但有时我们仍然需要链表的插入/删除不移动元素的特性。静态链表就是在这种背景下提出的——用数组模拟链表。
此外，在某些系统级场景中（如多进程共享内存），无法使用操作系统动态分配的指针地址，静态链表提供了一种无需 malloc/free 就能实现链式存储的方案。408 考研中，静态链表是链表章节的补充考点，重在理解"游标代替指针"的思想。
核心思想
静态链表的核心特点：
- 用数组存储节点：每个数组元素包含
data（数据域）和cursor（游标/指针域） - 游标代替指针：游标存放的是下一个节点在数组中的下标，而非内存地址
- 需要维护空闲链表：被删除的节点通过游标串成"备用链表"，供后续插入使用
节点结构定义：
c
#define MAXSIZE 100
typedef struct {
int data; // 数据域
int cursor; // 游标（下一个节点的数组下标）
} SLinkList[MAXSIZE];存储示意：
下标: 0 1 2 3 4 5 ...
data: - 'A' 'C' 'E' 'B' 'D' ...
cursor: 6 4 3 0 2 -1 ...上例中，下标 0 作为备用链表的头节点（不存数据），其游标指向第一个空闲位置；数据链表通常约定某个固定位置（如最后一个元素）存放数据链的头指针。游标值 -1（或 0）表示链表结尾。
节点申请与回收流程图
交互可视化
通过下方的交互动画，你可以逐步观察静态链表的执行过程：
操作详解
初始化
初始化时，将数组中所有节点串成一条备用空闲链表，表示所有空间均可用。
关键步骤：
- 将数组下标 0 作为备用链表头节点
- 每个节点的游标指向下一个下标，形成空闲链
- 最后一个节点的游标置为 0（表示无更多空闲空间）
c
void InitList(SLinkList space) {
for (int i = 0; i < MAXSIZE - 1; i++) {
space[i].cursor = i + 1; // 每个节点指向下一个
}
space[MAXSIZE - 1].cursor = 0; // 最后一个节点指向 0，表示结束
}初始化后的状态：
下标: 0 1 2 3 ... MAXSIZE-1
cursor: 1 2 3 4 ... 0插入操作
插入时，先从备用链表中申请一个空闲节点，再修改游标完成插入，无需移动其他元素。
关键步骤：
- 从备用链表取出一个空闲节点（模拟
malloc） - 将数据写入该节点的
data域 - 修改游标，将新节点插入到目标位置
c
// 从备用链表申请一个空闲节点，返回其下标
int Malloc_SL(SLinkList space) {
int i = space[0].cursor; // 取备用链表第一个空闲节点
if (i) {
space[0].cursor = space[i].cursor; // 备用链表头指向下一个空闲节点
}
return i; // 返回分配到的下标，0 表示分配失败（无空间）
}
// 在第 k 个节点之后插入新元素 e
void InsertAfter(SLinkList space, int k, int e) {
int j = Malloc_SL(space); // 申请空闲节点
if (j == 0) return; // 空间已满
space[j].data = e;
space[j].cursor = space[k].cursor; // 新节点指向 k 的后继
space[k].cursor = j; // k 指向新节点
}删除操作
删除时，修改游标跳过被删节点，再将该节点归还给备用链表（模拟 free），同样无需移动元素。
关键步骤：
- 找到待删除节点的前驱
- 修改前驱的游标，跳过被删节点
- 将被删节点回收到备用链表
c
// 将下标为 k 的节点回收到备用链表
void Free_SL(SLinkList space, int k) {
space[k].cursor = space[0].cursor; // 被回收节点指向原备用链表首节点
space[0].cursor = k; // 备用链表头指向被回收节点
}
// 删除第 k 个节点之后的节点
void DeleteAfter(SLinkList space, int k) {
int j = space[k].cursor; // j 为被删节点下标
if (j == 0) return; // k 之后无节点
space[k].cursor = space[j].cursor; // k 指向被删节点的后继
Free_SL(space, j); // 回收节点 j
}查找操作
静态链表不支持随机访问，查找时只能从头节点出发，沿游标逐个遍历。
c
// 按值查找，返回节点下标，未找到返回 0
int LocateElem(SLinkList space, int head, int e) {
int i = space[head].cursor; // 从头节点的后继开始
while (i != 0) {
if (space[i].data == e) {
return i;
}
i = space[i].cursor; // 沿游标移动到下一个节点
}
return 0; // 未找到
}复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 按位查找 | O(n) | 不支持随机访问，需沿游标遍历 |
| 按值查找 | O(n) | 最坏需遍历整条链 |
| 插入（已知前驱） | O(1) | 只需修改游标，无需移动元素 |
| 删除（已知前驱） | O(1) | 只需修改游标，无需移动元素 |
| 申请/回收节点 | O(1) | 备用链表头部操作 |
空间复杂度：需要预先分配固定大小的数组，空间利用率取决于 MAXSIZE 的设置。每个节点额外存储一个游标字段，存储密度低于顺序表。
与动态链表对比：
| 对比项 | 静态链表 | 动态链表 |
|---|---|---|
| 存储方式 | 预分配数组 | 动态 malloc/free |
| 指针域 | 游标（数组下标） | 内存地址指针 |
| 插入/删除 | 不移动元素，O(1) | 不移动元素，O(1) |
| 容量 | 固定，需预先确定 | 理论上不受限 |
| 适用场景 | 无指针的语言、共享内存 | 通用场景 |
| 内存碎片 | 无 | 频繁分配可能产生碎片 |
考研高频考点
- ⭐ 静态链表的定义与存储结构（游标的含义，选择题高频）
- ⭐ 静态链表与动态链表的区别（简答题/选择题常考）
- ⭐ 静态链表的适用场景：不支持指针的语言、共享内存环境（概念题）
- 备用链表（空闲链表）的管理机制：
Malloc_SL与Free_SL - 插入和删除操作不需要移动元素，只修改游标（判断题易错点）
- 静态链表仍然不能随机访问，查找时间复杂度为 O(n)