正文
大家好，我是bug菌～
首先跟大家聊聊什么是静态链表，静态链表是一种使用数组来实现的链表结构。在静态链表中，数组的每个元素称为一个节点，节点中包含两部分信息：数据和指向下一个节点的“指针”，这里的指针并不是C语言里语法上的指针，它主要是标记节点在数组中的位置，也就是数组的下标索引，其实广义上也是一种指针吧。
再来看下静态链表怎么玩的吧～
所以与动态链表的差异点，主要是静态链表的节点在内存中是连续存储的，而且节点的数量是固定的。
有代码有真相：
#include <stdio.h>
#define MAX_SIZE 100
// 静态链表的节点结构
typedef struct Node {
int data; // 数据域
int next; // 指针域，指向下一个节点的索引
} Node;
// 初始化静态链表
void init(Node list[]) {
// 将所有节点的 next 域初始化为 -1，表示空闲状态
for (int i = 0; i < MAX_SIZE; i++) {
list[i].next = -1;
}
}
// 释放节点
void release(Node list[], int index) {
// 将节点标记为可用状态
list[index].next = -1;
}
// 获取可用的空闲节点索引
int getFreeNode(Node list[]) {
for (int i = 0; i < MAX_SIZE; i++) {
if (list[i].next == -1) {
return i;
}
}
return -1; // 没有可用节点
}
// 在链表末尾插入新节点
void insert(Node list[], int *head, int data) {
int freeIndex = getFreeNode(list);
if (freeIndex != -1) {
// 在空闲节点处插入新节点
list[freeIndex].data = data;
list[freeIndex].next = -1;
int i = *head;
while (list[i].next != -1) {
i = list[i].next;
}
list[i].next = freeIndex;
} else {
printf("No free node available.\n");
}
}
// 删除节点
void deleteNode(Node list[], int *head, int data) {
int prevIndex = -1;
int currIndex = *head;
while (currIndex != -1) {
if (list[currIndex].data == data) {
if (prevIndex != -1) {
list[prevIndex].next = list[currIndex].next;
} else {
*head = list[currIndex].next;
}
release(list, currIndex);
printf("Node with data %d deleted.\n", data);
return;
}
prevIndex = currIndex;
currIndex = list[currIndex].next;
}
printf("Node with data %d not found.\n", data);
}
// 打印链表中的所有节点
void printList(Node list[], int head) {
int i = head;
while (i != -1) {
printf("%d ", list[i].data);
i = list[i].next;
}
printf("\n");
}
int main() {
Node list[MAX_SIZE]; // 定义静态链表
int head = 0; // 头指针
// 初始化链表
init(list);
// 插入节点
insert(list, &head, 10);
insert(list, &head, 20);
insert(list, &head, 30);
// 打印链表
printf("Static Linked List: ");
printList(list, head);
// 删除节点
deleteNode(list, &head, 20);
// 打印删除节点后的链表
printf("Static Linked List after deletion: ");
printList(list, head);
return 0;
}
这样看静态链表代码上的两个特点，采用固定内存区域上数组，指向下一个元素存储的是数组索引。
顺便整理下动态数组静态数组的差异，两者也如前面说的，主要是在内存管理和节点分配两个方面有比较大的差异点：
1、内存管理方式:
动态链表: 在动态链表中，节点通常是通过动态内存分配函数（如 malloc 或 new）在堆内存中分配的。这意味着节点在代码运行时动态地分配和释放内存。节点的数量可以根据需要进行动态调整，只要你的动态内存空间足够，因此在插入和删除节点时相对更加灵活。
静态链表: 静态链表使用数组实现，节点的数量在编译时就被确定，并且存储空间是静态分配的，话说回来，你可以在使用前动态分配一片内存供静态链表使用，但在静态链表在使用过程中没法动态地增加或减少总的节点的数量，当然你说完全没法改变吧，也不是不行，就是相对来说性价比不高。
2、节点的分配和释放:
动态链表: 节点在堆内存中动态分配，因此可以根据需要创建新节点，并且可以在不需要时释放节点的内存,给其他任务去使用。节点的生命周期由bug工程师自己管理，可以根据需要进行内存管理，如果没管理好，就会出现内存泄漏或者野指针等问题。
讲了这么多，到底静态链表有啥只用？有什么优势？
主要是用在内存受限的嵌入式系统，比如说单片机，在内存受限的这样的嵌入式系统中，动态内存分配可能会导致碎片化问题，而静态链表通过预分配数组空间，避免了频繁的内存分配和释放。
需要实时性有要求的系统：对于需要保证实时性能的系统，静态链表的实现更加可靠，因为它避免了动态内存分配和释放的不确定性，从而减少了系统出现延迟的可能性，这一点很重要。
固定大小的数据结构，相对动态链表的话内存问题更加容易受管控。
小型数据集：当数据集较小，不需要频繁进行节点插入和删除操作时，静态链表可以提供较好的性能和简洁的实现。
推荐专辑 点击蓝色字体即可跳转
☞ MCU进阶专辑
