静态线性链表

1 基本概念

静态线性链表是一种使用数组（或连续内存空间）来模拟链表逻辑结构的数据结构。它通过数组下标（索引）来替代传统链表中的指针，实现元素的线性连接。

1.1 核心组成

静态线性链表通常包含两个核心部分：

• 数据域（data）：存储元素的实际值。
• 游标（cur 或 next）：存储下一个元素在数组中的下标（索引）。在链表的末尾或空闲位置，游标通常用一个特殊值（如 -1 或 0）表示“空”。

静态线性链表的第一个位置下标0不存储数据，用来作为空间的头结点，游标（cur / next）指向下一个结点，当最后遍历到链表的游标指向0，即为指向空，到达链表的结尾。静态链表同时维护数据链表和备用链表，节点在物理上固定，逻辑上通过cur灵活组织，插入删除本质是在两个链表间转移节点。

1.2 基本操作

静态线性链表支持与传统链表类似的基本操作，但实现方式基于数组索引：

• 初始化：将数组的每个位置（节点）的游标指向下一个空闲位置，形成一个“空闲链表”。
• 插入：从空闲链表中分配一个节点，修改相关节点的游标以建立新的链接关系。
• 删除：将节点从数据链表中移除，并将其重新链入空闲链表。
• 遍历：从“头节点”下标开始，顺着游标依次访问每个节点。

2 与动态链表的相似点

静态线性链表在逻辑行为上与动态链表（指针实现的链表）高度相似：

2.1 逻辑结构相同

两者都是线性表，元素之间通过“链接”关系（指针或游标）形成前后顺序，物理存储位置可以不连续。

2.2 操作接口一致

插入、删除、查找、遍历等操作的逻辑步骤和算法复杂度（如 O(1) 的头插、O(n) 的按值查找）在概念上是相同的。

2.3 无需预先确定长度

与顺序表（数组）不同，两者在逻辑上都可以动态地增加或删除元素，而不必在创建时就固定最大容量（尽管静态链表底层数组大小固定，但逻辑上可用的节点数可以动态变化）。

3 与动态链表的区别

尽管逻辑相似，但静态线性链表在实现机制和特性上与动态链表有显著区别：

3.1 内存管理方式

3.2 性能特点

• 访问速度：静态链表基于数组，CPU 缓存友好，连续访问可能更快；动态链表节点分散，缓存局部性较差。
• 插入/删除开销：两者逻辑开销相同，但静态链表的节点分配/释放只是修改游标，速度快且无系统调用；动态链表涉及内存管理函数，可能更慢。
• 空间开销：静态链表需要预先分配固定空间，可能浪费或不足；动态链表按需分配，更灵活，但每个节点可能有额外的内存开销（如堆内存管理信息）。

3.3 适用场景

• 静态线性链表适用场景：
  • 嵌入式系统或内存受限环境，避免动态内存分配的不确定性。
  • 需要频繁增删但总节点数有明确上限的场景。
  • 实现某些特定数据结构的基础，如操作系统的文件分配表（FAT）、静态内存池管理。
• 动态链表适用场景：
  • 元素数量变化范围大，无法预估上限。
  • 对内存使用效率要求高，希望精确按需分配。
  • 支持复杂的内存管理策略（如垃圾回收、内存池）。

4 代码实现

以下是一个简单的静态线性链表实现，演示初始化、插入和遍历：

基本结构：

#define MAXSIZE 8 typedef struct slinklist { int value; int cur; }component,SLinkList[MAXSIZE];

基本操作：

#include <iostream> #include <string> #include <stdio.h> #include <ctime> void InitSpace_SL(SLinkList space) { //初始化静态备用链表 for (int i = 0; i < MAXSIZE - 1; i++) { space[i].cur = i + 1; } // 设置0，作为空指针，结束标志； space[MAXSIZE - 1].cur = 0; } int Malloc_SL(SLinkList space) { //若静态备用链表非空，返回分配的节点下标，否则返回0 int i = space[0].cur; if(space[0].cur) space[0].cur = space[i].cur; return i; } void Free_SL(SLinkList space, int k) { //将下标为k的空闲节点回收到备用链表中 space[k].cur = space[0].cur; space[0].cur = k; } void Insert_SL(SLinkList s, SLinkList space, int value,int loc) { //静态链表中插入数据； int index = Malloc_SL(space); int i = 0; int count = 0; if (!index) { printf("空间已满，位置%d无法插入%d！\n",loc,value); return; } s[index].value = value; while (s[i].cur && count<loc-1) { i = s[i].cur; count++; } if (count < loc - 1) { printf("非法位置插入,超出长度\n"); Free_SL(space, index); return; } s[index].cur = s[i].cur; s[i].cur = index; } int Delete_SL(SLinkList s, SLinkList space, int loc) { // 按位置删除数据 int del,i=0,count = 0; while (s[i].cur && count < loc - 1) { i = s[i].cur; count++; } if (count < loc - 1) { printf("非法删除数据，该位置超出链表长度！\n"); return -1; } del = s[i].cur; s[i].cur = s[del].cur; int re = s[del].value; Free_SL(space,del); return re; } void Print_SL(SLinkList s) { // 打印内容 int i = s[0].cur; while (i) { printf("%5d", s[i].value); i = s[i].cur; } printf("\n"); }

代码测试：

int main() { SLinkList space; InitSpace_SL(space); SLinkList s; // 初始化数据链表 s[0].cur = 0; s[0].value = 0; int d; srand((unsigned int)time(0)); // 1 初始化插入前五位； for (int i = 0; i < 5; i++) { d = rand() % 100 + 1; Insert_SL(s, space, d, i + 1); } printf("原始链表内容：\n"); Print_SL(s); printf("\n"); // 2 继续插入（测试空间满） printf("继续插入更多数据：\n"); Insert_SL(s, space, 50, 5); Insert_SL(s, space, 60, 5); Insert_SL(s, space, 70, 6); Insert_SL(s, space, 80, 7); printf("插入后链表内容：\n"); Print_SL(s); printf("\n"); //第2个位置删除 int del = Delete_SL(s, space, 2); if (del != -1) { printf("第二个位置，值%d删除，现链表内容：\n", del); Print_SL(s); } printf("\n"); //第三个位置插入 Insert_SL(s, space, 60, 3); printf("第三个位置插入60，现链表内容：\n"); Print_SL(s); printf("\n"); return 0; }

运行结果：

原始链表内容： 55 59 26 14 25 继续插入更多数据： 空间已满，位置6无法插入70！ 空间已满，位置7无法插入80！ 插入后链表内容： 55 59 26 14 60 50 25 第二个位置，值59删除，现链表内容： 55 26 14 60 50 25 第三个位置插入60，现链表内容： 55 26 60 14 60 50 25

5 总结

刚开始，我还搞不懂这个指向问题，一直以为数组下标代表其在链表的位置，于是我在数组和动态链表的思想中转变不过来，后来才慢慢理解，静态链表其实和动态链表相似，区别是它的存储空间是连续的，而它们在静态链表中的先后顺序和动态链表类似，可以不连续。