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. 单链表的核心操作（嵌入式场景优化）
单链表的操作核心