一、什么是静态链表

静态链表，就是用数组来实现的链表。它结合了数组的顺序存储和链表的动态链接特点。

核心思想：

• 申请一个固定大小的数组

• 数组的每个元素是一个结构体，包含数据域和游标（cur）

• 游标存放的是下一个元素在数组中的下标，相当于指针

• 通过游标来链接各个元素，形成逻辑上的链表

画个图理解：

text

数组：         数据    游标
下标0：        [头]    2   ← 指向第一个空闲位置
下标1：        [A]     3   ← 指向B
下标2：        [B]     4   ← 指向C
下标3：        [C]     0   ← 0表示NULL
下标4：        [空闲]  5
下标5：        [空闲]  6
...

特点：

• 不需要动态申请和释放内存（内存固定）

• 插入删除时不需要移动数据，只需修改游标

• 没有指针，适合没有指针的语言（如早期的BASIC、Fortran）

---

二、静态链表的结构定义

2.1 节点定义

c

#define MAX_SIZE 100  // 静态链表的最大长度

typedef struct {
    int data;      // 数据域
    int cur;       // 游标，存放下一个节点的下标
} StaticNode;

typedef struct {
    StaticNode nodes[MAX_SIZE];  // 节点数组
    int head;                     // 头结点下标
    int size;                     // 当前元素个数
} StaticList;

2.2 备用链表

静态链表中，有两种链表：

• 数据链表：存储实际数据的节点链接而成的链表

• 备用链表：未被使用的空闲节点链接而成的链表

通常约定：

• 下标0作为头结点，不存数据，只做管理

• 下标0的cur指向备用链表的第一个空闲节点

• 备用链表的最后一个节点的cur为0（表示NULL）

2.3 初始化

c

void initStaticList(StaticList *list) {
    // 初始化所有节点，将每个节点的cur指向下一个
    for (int i = 0; i < MAX_SIZE - 1; i++) {
        list->nodes[i].cur = i + 1;
    }
    list->nodes[MAX_SIZE - 1].cur = 0;  // 最后一个节点cur为0
    
    list->head = 0;        // 头结点下标
    list->size = 0;
    
    // 初始化后，整个数组都是空闲的，备用链表为：0 → 1 → 2 → ... → MAX_SIZE-1 → 0
}

2.4 分配和释放节点

分配节点：从备用链表中取一个空闲节点
释放节点：将节点放回备用链表

c

// 从备用链表中分配一个节点，返回下标
int allocNode(StaticList *list) {
    int i = list->nodes[0].cur;  // 第一个空闲节点
    if (i != 0) {
        // 将头结点的cur指向下一个空闲节点
        list->nodes[0].cur = list->nodes[i].cur;
    }
    return i;  // 返回分配到的下标，0表示没有空闲节点
}

// 将下标为i的节点释放回备用链表
void freeNode(StaticList *list, int i) {
    // 将节点i插入到备用链表的头部
    list->nodes[i].cur = list->nodes[0].cur;
    list->nodes[0].cur = i;
}

---

三、基本操作实现

3.1 插入

在指定位置插入元素（pos从0开始，0表示第一个有效节点）。

c

int insertAt(StaticList *list, int pos, int value) {
    if (pos < 0 || pos > list->size) {
        printf("插入位置不合法\n");
        return -1;
    }
    
    // 分配新节点
    int newNodeIndex = allocNode(list);
    if (newNodeIndex == 0) {
        printf("静态链表已满\n");
        return -1;
    }
    list->nodes[newNodeIndex].data = value;
    
    // 找到插入位置的前一个节点
    int prev = list->head;
    for (int i = 0; i < pos; i++) {
        prev = list->nodes[prev].cur;
    }
    
    // 插入节点
    list->nodes[newNodeIndex].cur = list->nodes[prev].cur;
    list->nodes[prev].cur = newNodeIndex;
    list->size++;
    
    return 0;
}

3.2 删除

删除指定位置的元素。

c

int deleteAt(StaticList *list, int pos) {
    if (pos < 0 || pos >= list->size) {
        printf("删除位置不合法\n");
        return -1;
    }
    
    // 找到要删除节点的前一个节点
    int prev = list->head;
    for (int i = 0; i < pos; i++) {
        prev = list->nodes[prev].cur;
    }
    
    int toDelete = list->nodes[prev].cur;
    int value = list->nodes[toDelete].data;
    
    // 断开连接
    list->nodes[prev].cur = list->nodes[toDelete].cur;
    
    // 释放节点
    freeNode(list, toDelete);
    list->size--;
    
    return value;
}

3.3 查找

c

int find(StaticList *list, int value) {
    int cur = list->nodes[list->head].cur;
    int pos = 0;
    while (cur != 0) {
        if (list->nodes[cur].data == value) {
            return pos;
        }
        cur = list->nodes[cur].cur;
        pos++;
    }
    return -1;
}

3.4 遍历打印

c

void printList(StaticList *list) {
    printf("size=%d, [", list->size);
    int cur = list->nodes[list->head].cur;
    while (cur != 0) {
        printf("%d", list->nodes[cur].data);
        if (list->nodes[cur].cur != 0) printf(" -> ");
        cur = list->nodes[cur].cur;
    }
    printf("]\n");
}

3.5 销毁

c

void destroyList(StaticList *list) {
    // 静态链表不需要释放内存，只需要重置状态
    initStaticList(list);
}

---

四、完整代码演示

c

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

typedef struct {
    int data;
    int cur;
} StaticNode;

typedef struct {
    StaticNode nodes[MAX_SIZE];
    int head;
    int size;
} StaticList;

void initStaticList(StaticList *list) {
    for (int i = 0; i < MAX_SIZE - 1; i++) {
        list->nodes[i].cur = i + 1;
    }
    list->nodes[MAX_SIZE - 1].cur = 0;
    list->head = 0;
    list->size = 0;
}

int allocNode(StaticList *list) {
    int i = list->nodes[0].cur;
    if (i != 0) {
        list->nodes[0].cur = list->nodes[i].cur;
    }
    return i;
}

void freeNode(StaticList *list, int i) {
    list->nodes[i].cur = list->nodes[0].cur;
    list->nodes[0].cur = i;
}

int insertAt(StaticList *list, int pos, int value) {
    if (pos < 0 || pos > list->size) {
        printf("插入位置不合法\n");
        return -1;
    }
    
    int newNodeIndex = allocNode(list);
    if (newNodeIndex == 0) {
        printf("静态链表已满\n");
        return -1;
    }
    list->nodes[newNodeIndex].data = value;
    
    int prev = list->head;
    for (int i = 0; i < pos; i++) {
        prev = list->nodes[prev].cur;
    }
    
    list->nodes[newNodeIndex].cur = list->nodes[prev].cur;
    list->nodes[prev].cur = newNodeIndex;
    list->size++;
    
    return 0;
}

int deleteAt(StaticList *list, int pos) {
    if (pos < 0 || pos >= list->size) {
        printf("删除位置不合法\n");
        return -1;
    }
    
    int prev = list->head;
    for (int i = 0; i < pos; i++) {
        prev = list->nodes[prev].cur;
    }
    
    int toDelete = list->nodes[prev].cur;
    int value = list->nodes[toDelete].data;
    
    list->nodes[prev].cur = list->nodes[toDelete].cur;
    freeNode(list, toDelete);
    list->size--;
    
    return value;
}

int find(StaticList *list, int value) {
    int cur = list->nodes[list->head].cur;
    int pos = 0;
    while (cur != 0) {
        if (list->nodes[cur].data == value) {
            return pos;
        }
        cur = list->nodes[cur].cur;
        pos++;
    }
    return -1;
}

void printList(StaticList *list) {
    printf("size=%d, [", list->size);
    int cur = list->nodes[list->head].cur;
    while (cur != 0) {
        printf("%d", list->nodes[cur].data);
        if (list->nodes[cur].cur != 0) printf(" -> ");
        cur = list->nodes[cur].cur;
    }
    printf("]\n");
}

int main() {
    StaticList list;
    initStaticList(&list);
    
    // 插入
    insertAt(&list, 0, 10);
    insertAt(&list, 1, 20);
    insertAt(&list, 2, 30);
    printList(&list);  // [10 -> 20 -> 30]
    
    // 中间插入
    insertAt(&list, 1, 15);
    printList(&list);  // [10 -> 15 -> 20 -> 30]
    
    // 删除
    int val = deleteAt(&list, 2);
    printf("删除的值: %d\n", val);
    printList(&list);  // [10 -> 15 -> 30]
    
    // 查找
    int pos = find(&list, 15);
    printf("15的位置: %d\n", pos);
    
    return 0;
}

运行结果：

text

size=3, [10 -> 20 -> 30]
size=4, [10 -> 15 -> 20 -> 30]
删除的值: 20
size=3, [10 -> 15 -> 30]
15的位置: 1

---

五、静态链表 vs 动态链表

对比项	静态链表	动态链表
内存分配	静态数组，大小固定	动态分配，按需申请
内存位置	连续内存	不连续，分散在堆中
插入删除	改游标，不移动数据	改指针，不移动数据
最大长度	受数组大小限制	受内存限制
内存利用率	可能浪费（空闲节点）	按需分配，利用率高
适用语言	无指针的语言	C/C++等有指针的语言

---

六、静态链表的实际应用

虽然现代编程很少直接用静态链表，但它的思想在很多地方有体现：

1. 文件系统
某些文件系统的空闲块管理，用的就是类似静态链表的机制。

2. 内存池
预先申请一大块内存，用静态链表管理空闲块，可以避免频繁的malloc/free。

3. 数据库
某些数据库的页内记录管理，用类似游标的方式链接记录。

4. 嵌入式开发
在内存受限、不允许动态分配的环境中，静态链表是很好的选择。

---

七、小结

这一篇我们讲了静态链表：

要点	说明
核心思想	用数组下标代替指针，用游标链接元素
两种链表	数据链表（存实际数据）+ 备用链表（管理空闲节点）
插入删除	修改游标，不需要移动数据
优缺点	固定大小，无内存碎片；但长度受限，空间可能浪费

静态链表虽然现在用得不多，但它展示了链式结构的本质：不依赖连续内存，通过“链接”来组织数据。理解这个思想，对后面学树、图这些更复杂的结构也有帮助。

---

八、思考题

1. 静态链表初始化时，为什么要把所有节点的cur指向下一个节点？这样做的好处是什么？

2. 如果静态链表满了，再调用allocNode会返回什么？如何处理这种情况？

3. 静态链表的头结点（下标0）如果不存数据，那它的data字段可以用来做什么？

4. 尝试用静态链表实现一个简单的内存池（比如固定大小的对象池）。

欢迎在评论区讨论你的答案。