04_C语言数据结构与算法之线性数据结构：链表 —— 非连续内存的灵活王者

C语言数据结构与算法之线性数据结构：链表 —— 非连续内存的灵活王者

做嵌入式开发的朋友，想必都遇到过这样的场景：用数组做串口数据缓存时，要是数据量突然暴涨，数组固定的长度要么不够用导致数据溢出，要么提前分配超大数组浪费宝贵的内存；想在数据中间插入一个新的传感器读数，却要把后面的元素全都后移，在单片机这种资源受限的环境里，每一次循环移动都可能占用宝贵的CPU时间。

还有更头疼的：在裸机程序里实现一个任务队列，需要频繁地在队列头部删除已完成的任务、尾部添加新任务，用数组来做的话，要么每次删除都要移动一堆元素，要么就得用环形缓冲区的复杂逻辑来规避——可环形缓冲区又受限于初始的数组大小，一旦任务数量超过预设值，还是会陷入困境。

这时候你会不会想：要是有一种数据结构，能像搭积木一样，要一个节点就申请一块内存，不用了就释放，插入删除数据时不用动其他元素，那该多好？

其实，这就是链表的核心价值。它挣脱了连续内存的束缚，以非连续内存的存储方式，成为数据结构里的“灵活王者”。在嵌入式开发、后台服务的高频数据操作场景中，链表的灵活性往往能解决数组和顺序表难以攻克的问题。今天，我们就从嵌入式开发的实际需求出发，聊聊链表的三种常见形态——单链表、双向链表、循环链表，读懂非连续内存的灵活操作艺术。

一、链表的本质：非连续内存的“链式连接”

与数组和顺序表的连续内存布局不同，链表的核心是节点与指针：

节点：链表的基本单元，包含两部分——数据域（存储实际数据，如传感器的数值、任务的ID）和指针域（存储下一个节点的地址，双向链表还会存储上一个节点的地址）。

指针：通过指针将分散在内存中不同位置的节点串联起来，形成一个线性的逻辑结构。

这种设计让链表彻底摆脱了连续内存的限制：

内存按需分配：需要存储数据时，才向系统申请一块内存作为节点；数据删除后，可立即释放节点内存，极大节省内存资源（这对内存只有几KB、几十KB的嵌入式MCU来说，尤为重要）。

物理分散，逻辑连续：节点在内存中的地址可以是任意的，只要通过指针指向彼此，就能在逻辑上保持线性顺序。

对比数组的“整块连续内存”，链表就像一串珍珠：每颗珍珠（节点）是独立的，通过线（指针）连在一起，哪怕珍珠的位置分散，也不影响整体的顺序。

二、单链表：最简单的链式结构，嵌入式场景的“轻量之选”

单链表是链表中最基础的形态，每个节点只有一个指针域，指向下一个节点（
next），最后一个节点的
next指针指向
NULL，表示链表结束。此外，通常会用一个头指针（
head）指向第一个节点，作为链表的入口。

1. 单链表的结构定义（嵌入式场景适配版）

在嵌入式开发中，我们通常会用结构体定义节点，数据域可以根据实际需求设计（比如存储串口数据、任务信息）：

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

// 单链表节点定义（以存储嵌入式传感器数据为例）
typedef struct Node {
    uint16_t sensor_data; // 数据域：存储传感器采集的16位数值
    struct Node *next;    // 指针域：指向下一个节点
} ListNode;

2. 单链表的核心操作（嵌入式场景优化）

单链表的操作核心是指针的移动与指向修改，这也是链表灵活性的关键。我们以嵌入式中常用的“传感器数据队列”为例，实现核心操作。

（1）初始化链表：创建头节点（可选）

在嵌入式场景中，为了简化操作，常使用头节点（哑节点）——一个不存储有效数据的节点，作为链表的固定入口，避免处理空链表的特殊情况：

// 初始化单链表，返回头节点指针
ListNode *SinglyList_Init() {
    ListNode *head = (ListNode *)malloc(sizeof(ListNode));
    if (head == NULL) {
        // 嵌入式场景中，可添加硬件层面的错误处理（如点亮错误LED）
        return NULL;
    }
    head->sensor_data = 0; // 头节点数据域无意义
    head->next = NULL;
    return head;
}

（2）尾插法添加节点：传感器数据入队

在嵌入式中，传感器数据通常按采集顺序入队，尾插法是最常用的方式：

// 尾插法：将传感器数据添加到链表尾部（数据入队）
int SinglyList_TailInsert(ListNode *head, uint16_t data) {
    if (head == NULL) return -1;

    // 1. 创建新节点
    ListNode *new_node = (ListNode *)malloc(sizeof(ListNode));
    if (new_node == NULL) return -1;
    new_node->sensor_data = data;
    new_node->next = NULL;

    // 2. 找到链表尾部节点
    ListNode *p = head;
    while (p->next != NULL) {
        p = p->next;
    }

    // 3. 将新节点链接到尾部
    p->next = new_node;
    return 0;
}

（3）头插法添加节点：实现栈结构

头插法是将新节点插入到链表头部（头节点之后），这种方式可以快速实现嵌入式中的“栈”结构（如中断现场保护）：

// 头插法：将数据插入到链表头部（实现栈的压栈操作）
int SinglyList_HeadInsert(ListNode *head, uint16_t data) {
    if (head == NULL) return -1;

    // 1. 创建新节点
    ListNode *new_node = (ListNode *)malloc(sizeof(ListNode));
    if (new_node == NULL) return -1;
    new_node->sensor_data = data;

    // 2. 新节点指向头节点的下一个节点
    new_node->next = head->next;
    // 3. 头节点指向新节点
    head->next = new_node;
    return 0;
}

（4）删除节点：传感器数据出队/异常数据移除

在嵌入式中，处理完传感器数据后需要将其从链表中删除，或移除异常的数值节点：

// 删除第一个包含指定数据的节点（异常数据移除）
int SinglyList_Delete(ListNode *head, uint16_t data) {
    if (head == NULL || head->next == NULL) return -1;

    // 双指针：pre指向当前节点的前驱，p指向当前节点
    ListNode *pre = head;
    ListNode *p = head->next;

    while (p != NULL) {
        if (p->sensor_data == data) {
            // 前驱节点指向当前节点的下一个节点
            pre->next = p->next;
            // 释放节点内存（嵌入式中务必注意内存泄漏）
            free(p);
            p = NULL; // 野指针防护
            return 0;
        }
        pre = p;
        p = p->next;
    }
    return -1; // 未找到指定数据
}

3. 单链表的优缺点与嵌入式适用场景

三、双向链表：可前可后的“灵活升级款”

单链表的最大局限是只能单向遍历，如果需要访问某个节点的前驱节点，必须从表头重新遍历，这在需要频繁双向操作的场景中效率极低。双向链表正是为解决这个问题而生——每个节点有两个指针域：
prev （指向前驱节点） 和**
next（指向后继节点）**。

1. 双向链表的结构定义

// 双向链表节点定义（以存储嵌入式任务信息为例）
typedef struct DNode {
    uint32_t task_id;      // 数据域：任务ID
    uint8_t task_priority; // 数据域：任务优先级
    struct DNode *prev;    // 指针域：指向前驱节点
    struct DNode *next;    // 指针域：指向后继节点
} DListNode;

2. 双向链表的核心优势：双向遍历与高效删除

在嵌入式的任务调度场景中，双向链表的优势尤为明显：

双向遍历：可以从任意节点向前或向后遍历，方便根据任务优先级正向/反向查找任务。

高效删除：如果已经找到需要删除的节点，无需像单链表那样查找前驱节点，直接通过
prev指针就能完成删除，时间复杂度从O(n)降至O(1)。

示例：删除指定任务节点（双向链表）

// 删除双向链表中指定task_id的节点（已知节点指针时）
int DList_DeleteNode(DListNode *node) {
    if (node == NULL) return -1;

    // 前驱节点的next指向当前节点的后继节点
    node->prev->next = node->next;
    // 后继节点的prev指向当前节点的前驱节点
    node->next->prev = node->prev;

    free(node);
    node = NULL;
    return 0;
}

3. 双向链表的嵌入式适用场景

双向链表的内存开销略大于单链表（多一个指针域），但灵活性大幅提升，适合：

嵌入式系统的任务调度（支持按优先级双向查找、快速删除任务）；

触摸屏的触控点历史记录（需要向前/向后翻阅记录）；

带撤销功能的操作队列（如配置参数的修改记录）。

四、循环链表：首尾相连的“闭环结构”

循环链表是链表的“闭环形态”，将单链表或双向链表的最后一个节点的
next指针（双向链表还包括第一个节点的
prev指针）指向链表的第一个节点（或头节点），形成一个环形结构。

1. 循环链表的核心特点

无边界：遍历链表时，从任意节点出发都能回到该节点，适合需要循环处理数据的场景。

简化遍历：无需判断
next是否为
NULL，只需判断是否回到起始节点即可。

2. 循环链表的嵌入式适用场景

（1）单循环链表：环形任务调度

在裸机程序中，常使用单循环链表实现时间片轮转调度：将多个任务节点组成循环链表，CPU按顺序逐个执行任务，执行完最后一个任务后回到第一个任务，循环往复。

（2）双向循环链表：实时数据缓冲区

在嵌入式的实时数据采集场景中，双向循环链表可以实现一个“无限长度”的缓冲区：新数据添加到链表尾部，当缓冲区满时，自动覆盖最旧的数据（通过指针移动实现，无需删除节点）。

示例：单循环链表的任务遍历

// 遍历单循环链表的任务节点（从头节点开始，回到头节点结束）
void CycleList_Traverse(DListNode *head) {
    if (head == NULL || head->next == head) return; // 空链表

    DListNode *p = head->next; // 第一个有效节点
    while (p != head) { // 未回到头节点则继续
        printf("任务ID：%d，优先级：%d
", p->task_id, p->task_priority);
        p = p->next;
    }
}

五、链表vs数组/顺序表：嵌入式场景的选择之道

在嵌入式开发中，选择数据结构的核心是平衡资源开销与操作效率，我们通过表格对比三者的关键特性，明确适用场景：

若传感器数据量固定、需要快速查询（如按索引读取历史数据），用数组/顺序表；

若串口数据缓存、简单任务队列，数据量动态且仅需单向操作，用单链表；

若任务调度、实时数据缓冲区，需要双向操作或循环处理，用双向链表/循环链表。

六、嵌入式链表开发的避坑指南

链表的灵活性也带来了一些容易踩坑的点，尤其是在资源受限的嵌入式环境中，一个小错误就可能导致程序崩溃。

1. 野指针：嵌入式程序的“致命隐患”

问题：指针指向已释放的节点、未初始化的指针、链表尾部的指针未正确指向
NULL（或循环链表的头节点），都会导致野指针，进而引发内存访问错误。

避坑方法：

节点释放后，立即将指针置为
NULL；

初始化链表时，务必将尾指针指向
NULL（或循环链表的头节点）；

访问指针前，先判断指针是否为
NULL。

2. 内存泄漏：MCU内存的“慢性毒药”

问题：嵌入式MCU的内存资源有限，若频繁创建节点却不释放，会导致内存逐渐耗尽，程序最终崩溃。

避坑方法：

数据处理完成后，及时释放对应的节点；

在裸机程序中，可设计“内存池”管理链表节点（预先分配一批节点，避免频繁调用
malloc/free，提升效率并减少内存碎片）。

3. 链表遍历死循环：循环链表的“专属陷阱”

问题：循环链表中，若节点的指针指向错误（如未指向头节点，而是指向中间节点），会导致遍历陷入死循环，占用CPU全部资源。

避坑方法：

循环链表的节点插入时，务必确保尾节点指向头节点；

遍历循环链表时，设置明确的终止条件（如回到头节点），避免无限循环。

七、总结：非连续内存的灵活哲学

链表的核心价值，在于挣脱了连续内存的束缚，以指针为纽带，实现了数据的灵活存储与操作。在嵌入式开发中，它完美解决了数组/顺序表在动态数据处理中的痛点——内存按需分配、插入删除无需移动元素，成为资源受限环境下的“灵活王者”。

从单链表的轻量高效，到双向链表的双向操作，再到循环链表的闭环处理，三种链表形态分别适配了不同的嵌入式场景。学习链表，不仅是掌握三种数据结构的实现，更重要的是理解**“逻辑连续”比“物理连续”更重要**的设计思路——这也是数据结构的核心精髓。

在实际开发中，我们无需拘泥于链表的“纯理论实现”，可以结合嵌入式的实际需求进行优化：比如用内存池替代
malloc/free，用头节点简化空链表处理，用循环链表实现高效的任务调度。唯有如此，才能真正让链表的灵活性为嵌入式程序赋能，写出更高效、更稳定的代码。