嵌入式实时性可以考虑静态链表～

2万 · 2024-4-27 10:00

大家好，我是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.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.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.next != -1) {
         i = list.next;
      }
      list.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.data);
      i = list.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工程师自己管理，可以根据需要进行内存管理，如果没管理好，就会出现内存泄漏或者野指针等问题。

讲了这么多，到底静态链表有啥只用？有什么优势？

主要是用在内存受限的嵌入式系统，比如说单片机，在内存受限的这样的嵌入式系统中，动态内存分配可能会导致碎片化问题，而静态链表通过预分配数组空间，避免了频繁的内存分配和释放。

需要实时性有要求的系统：对于需要保证实时性能的系统，静态链表的实现更加可靠，因为它避免了动态内存分配和释放的不确定性，从而减少了系统出现延迟的可能性，这一点很重要。

固定大小的数据结构，相对动态链表的话内存问题更加容易受管控。

小型数据集：当数据集较小，不需要频繁进行节点插入和删除操作时，静态链表可以提供较好的性能和简洁的实现。