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

大家好，我是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);
}

这样看静态链表代码上的两个特点，采用固定内存区域上数组，指向下一个元素存储的是数组索引。

顺便整理下动态数组静态数组的差异，两者也如前面说的，主要是在内存管理和节点分配两个方面有比较大的差异点：

1、内存管理方式:

动态链表: 在动态链表中，节点通常是通过动态内存分配函数（如 malloc 或 new）在堆内存中分配的。这意味着节点在代码运行时动态地分配和释放内存。节点的数量可以根据需要进行动态调整，只要你的动态内存空间足够，因此在插入和删除节点时相对更加灵活。

静态链表: 静态链表使用数组实现，节点的数量在编译时就被确定，并且存储空间是静态分配的，话说回来，你可以在使用前动态分配一片内存供静态链表使用，但在静态链表在使用过程中没法动态地增加或减少总的节点的数量，当然你说完全没法改变吧，也不是不行，就是相对来说性价比不高。

2、节点的分配和释放:

动态链表: 节点在堆内存中动态分配，因此可以根据需要创建新节点，并且可以在不需要时释放节点的内存,给其他任务去使用。节点的生命周期由bug工程师自己管理，可以根据需要进行内存管理，如果没管理好，就会出现内存泄漏或者野指针等问题。

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

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

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

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

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