嵌入式C语言链表技术实现与工程实践

写在前面

链表是嵌入式开发中最基础也最核心的数据结构之一。然而在嵌入式领域，由于运行环境的限制，我们无法像桌面应用那样随意使用 malloc 和 free 进行动态内存管理。静态内存池、侵入式设计、哨兵节点这些在通用 C 语言教材中很少提及的技术，反而是嵌入式工程师的必备技能。

本文档从实际工程出发，通过三个完整的 Demo 分别讲解单向链表、双向循环链表和双向非循环链表的原理与实现。所有代码均不依赖动态内存分配，采用静态数组模拟内存池的方式，读者可以直接拷贝到自己的项目中运行验证。

除了代码实现，文档还重点对比了三种链表的特点差异、使用场景选型建议，以及完整的移植步骤清单。无论你是刚接触链表的新人，还是需要回顾总结的老兵，这份文档都能为你提供实用的参考。

文档结构：第一节～第三节分别讲解三种链表（原理、数据结构、完整 Demo、常用操作补充、要点小结、移植要点）；第四节对比差异，第五节选型，第六节学习建议，第七节移植使用清单。

一、单向链表（Singly Linked List）

1.1 原理

单向链表的每个节点只保留一个指向后继的指针 next，从头节点出发可顺序遍历到尾部，无法逆向。链表尾的 next 为 NULL 表示结束。

head -> [A|next] -> [B|next] -> [C|next] -> NULL

1.2 数据结构定义

/* 节点：业务数据 + 后继指针 */
typedef struct SList_node {
int id; /* 示例业务字段 */
int value;
struct SList_node *next; /* 仅后继指针 */
} SList_node_t;

/* 链表头：指向首节点，NULL 表示空 */
SList_node_t *head = NULL;

1.3 Demo：完整实现

以下实现包含：尾插、按 id 删除、遍历；并抽象出 alloc_node / free_node，便于移植时替换为静态池或 malloc。

#include <stdio.h>
#include <string.h>

#define POOL_SIZE 8

typedef struct SList_node {
int id;
int value;
struct SList_node *next;
} SList_node_t;

static SList_node_t pool[POOL_SIZE]; /* 静态内存池 */
static int pool_used[POOL_SIZE];

static SList_node_t* alloc_node(void) {
for (int i = 0; i < POOL_SIZE; i++) {
if (!pool_used[i]) {
pool_used[i] = 1;
memset(&pool[i], 0, sizeof(pool[i]));
return &pool[i];
}
}
return NULL;
}

static void free_node(SList_node_t *n) {
if (n >= pool && n < pool + POOL_SIZE)
pool_used[n – pool] = 0;
}

/* 尾插 */
void slist_append(SList_node_t **head, SList_node_t *node) {
node->next = NULL;
if (*head == NULL) {
*head = node;
return;
}
SList_node_t *p = *head;
while (p->next != NULL)
p = p->next;
p->next = node;
}

/* 按 id 删除：需特殊处理首节点 */
void slist_remove(SList_node_t **head, int id) {
SList_node_t *cur = *head, *prev = NULL;
while (cur != NULL) {
if (cur->id == id) {
if (prev == NULL)
*head = cur->next; /* 删首节点 */
else
prev->next = cur->next;
free_node(cur);
return;
}
prev = cur;
cur = cur->next;
}
}

/* 遍历 */
void slist_foreach(SList_node_t *head, void (*fn)(SList_node_t*)) {
while (head != NULL) {
fn(head);
head = head->next;
}
}

1.3.1 常用操作补充（便于移植时扩展）

头插（新节点作为链表头）：

void slist_insert_head(SList_node_t **head, SList_node_t *node) {
node->next = *head;
*head = node;
}

按 id 查找（返回第一个匹配的节点指针）：

SList_node_t* slist_find(SList_node_t *head, int id) {
while (head != NULL) {
if (head->id == id) return head;
head = head->next;
}
return NULL;
}

1.4 使用示例

static void print_node(SList_node_t *n) {
printf("id=%d value=%d\\n", n->id, n->value);
}

int main(void) {
SList_node_t *head = NULL;

SList_node_t *a = alloc_node();
a->id = 1; a->value = 10;
slist_append(&head, a);

SList_node_t *b = alloc_node();
b->id = 2; b->value = 20;
slist_append(&head, b);

slist_remove(&head, 1); /* 删除 id=1，需遍历查找 */

slist_foreach(head, print_node);

return 0;
}

1.5 要点小结

1.5.1 移植要点

二、双向循环链表（Doubly Circular Linked List）

2.1 原理

双向循环链表在每个节点上增加 prev 指针，且链表首尾相接形成环。通常引入一个**哨兵节点（Sentinel）**作为链表头，它不存业务数据，next 指向首个有效节点，prev 指向最后一个。空链表时哨兵的 next 和 prev 都指向自身。

Sentinel
/\\
/ \\
[A] <-> [B] <-> [C]
\\_______________/

2.2 数据结构定义

/* 通用链表节点：仅 prev/next，可嵌入任意结构体 */
typedef struct DLink {
struct DLink *prev;
struct DLink *next;
} DLink_t;

/* 业务结构体：嵌入 DLink */
typedef struct Task {
int id;
int state;
DLink_t link; /* 侵入式链表节点 */
} Task_t;

/* 哨兵节点：空链表时 next=prev=self */
DLink_t list_head;

2.3 宏接口与 container_of

/* 初始化空链表 */
#define list_init(head) \\
do { (head)->prev = (head); (head)->next = (head); } while (0)

/* 判空 */
#define list_is_empty(head) ((head)->next == (head))

/* 尾插：插在 head 前面（即尾部） */
#define list_append(head, node) \\
do { \\
(node)->prev = (head)->prev; \\
(node)->next = (head); \\
(head)->prev->next = (node); \\
(head)->prev = (node); \\
} while (0)

/* 头插：插在 head 后面（即头部） */
#define list_push(head, node) \\
do { \\
(node)->next = (head)->next; \\
(node)->prev = (head); \\
(head)->next->prev = (node); \\
(head)->next = (node); \\
} while (0)

/* 移除节点：O(1)，不需要知道链表头 */
#define list_remove(node) \\
do { \\
(node)->prev->next = (node)->next; \\
(node)->next->prev = (node)->prev; \\
(node)->prev = (node); \\
(node)->next = (node); \\
} while (0)

/* 从链表节点反推宿主结构体（container_of） */
#define list_entry(ptr, type, member) \\
((type*)((char*)(ptr) – (unsigned long)(&((type*)0)->member)))

/* 从链表节点反推宿主结构体，推荐使用标准 offsetof */
#include <stddef.h>
#define list_entry(ptr, type, member) \\
((type*)((char*)(ptr) – offsetof(type, member)))

2.3.1 get_obj_by_member 原理与应用

侵入式链表中，链表只维护「节点指针」（如 DLink_t*），遍历时得到的是成员地址；业务逻辑需要的是宿主结构体指针（如 Task_t*）。get_obj_by_member（或等价的 list_entry）用来从「成员指针」反推「宿主结构体指针」。

宏定义（与 list_entry 等价）：

#define get_obj_by_member(obj_type, mem_name, mem_ptr) \\
((obj_type*)((uint8_t*)(mem_ptr) – (uint32_t)&((obj_type*)0)->mem_name))

• obj_type：宿主结构体类型（如 Task_t、DataSyncManager_t）
• mem_name：成员名（如 link、bilink）
• mem_ptr：该成员的地址（遍历得到的 DLink_t* / bilink_t*）

原理：宿主首地址 = 成员地址 − 成员在结构体内的偏移

结构体在内存中连续存放，成员 link 的地址 = 宿主首地址 + offsetof(Task_t, link)。因此：

• 宿主首地址 = 成员地址 − offsetof(Task_t, link)

&((obj_type*)0)->member 在 C 中表示「假设结构体从地址 0 开始，则 member 的地址」即该成员的偏移量（不访问 0 地址，仅做指针运算）。

内存布局示意：

Task_t 在内存中：
┌─────────────┐
│ id │ ← Task_t*（宿主首地址，我们要得到的）
│ state │
│ link.prev │
│ link.next │ ← mem_ptr（已知：链表遍历得到的 DLink_t*）
└─────────────┘
↑
offsetof(Task_t, link) = &((Task_t*)0)->link

所以：Task_t* = (uint8_t*)mem_ptr – offsetof(Task_t, link)

在双向循环链表中的典型用法：

/* 遍历时：从 link 指针反推 Task_t* */
for (DLink_t *p = head.next; p != &head; p = p->next) {
Task_t *t = get_obj_by_member(Task_t, link, p); /* 或 list_entry(p, Task_t, link) */
printf("task id=%d\\n", t->id);
}

可移植写法：若希望避免 (type*)0 写法，可使用标准库 offsetof：

#include <stddef.h>
#define list_entry(ptr, type, member) ((type*)((char*)(ptr) – offsetof(type, member)))

2.4 Demo：完整实现

#include <stdio.h>
#include <string.h>

typedef struct DLink {
struct DLink *prev;
struct DLink *next;
} DLink_t;

typedef struct Task {
int id;
int state;
DLink_t link;
} Task_t;

#define list_init(head) \\
do { (head)->prev = (head); (head)->next = (head); } while (0)
#define list_is_empty(head) ((head)->next == (head))
#define list_append(head, node) \\
do { \\
(node)->prev = (head)->prev; (node)->next = (head); \\
(head)->prev->next = (node); (head)->prev = (node); \\
} while (0)
#define list_remove(node) \\
do { \\
(node)->prev->next = (node)->next; (node)->next->prev = (node)->prev; \\
(node)->prev = (node); (node)->next = (node); \\
} while (0)
#define list_entry(ptr, type, member) \\
((type*)((char*)(ptr) – offsetof(type, member)))

int main(void) {
DLink_t head;
Task_t t1 = {1, 0, {0}}, t2 = {2, 0, {0}}, t3 = {3, 0, {0}};

list_init(&head);

list_append(&head, &t1.link);
list_append(&head, &t2.link);
list_append(&head, &t3.link);

/* 遍历：从 head->next 到 head 前一个 */
for (DLink_t *p = head.next; p != &head; p = p->next) {
Task_t *t = list_entry(p, Task_t, link);
printf("task id=%d\\n", t->id);
}

/* 删除 t2：O(1)，已知节点指针即可 */
list_remove(&t2.link);

printf("after remove t2:\\n");
for (DLink_t *p = head.next; p != &head; p = p->next) {
Task_t *t = list_entry(p, Task_t, link);
printf("task id=%d\\n", t->id);
}

return 0;
}

安全遍历（遍历过程中可能删除当前节点时，必须先保存下一节点）：

DLink_t *p, *next;
for (p = head.next; p != &head; p = next) {
next = p->next; /* 先保存，再处理 p；处理时可能 list_remove(p) */
Task_t *t = list_entry(p, Task_t, link);
if (need_remove(t)) list_remove(p);
}

2.5 要点小结

2.5.1 移植要点

三、双向非循环链表（Doubly Linked List, Non-Circular）

3.1 原理

双向非循环链表的节点有 prev 和 next，但首节点的 prev 和尾节点的 next 为 NULL，不形成环。适合需要按优先级查找、从尾部取节点等场景。节点通常从内存池中获取：静态节点数组 + 占用表，分配时从池中取一槽、释放时还回池，避免堆碎片，适合嵌入式。

NULL <-> [A] <-> [B] <-> [C] -> NULL
^prev ^next

3.2 数据结构定义

节点内同时包含业务数据与 prev/next，节点即数据（非侵入式）。链表头由调用方维护，NULL 表示空。

/* 节点：业务数据 + prev/next */
typedef struct DNode {
int id;
int priority; /* 可用于优先级调度 */
struct DNode *prev;
struct DNode *next;
} DNode_t;

DNode_t *head = NULL; /* 链表头，NULL 表示空 */

3.3 Demo：完整实现（含内存池创建节点）

下面示例体现从内存池创建节点的完整流程：池由节点数组 + 占用表组成；分配时找空闲槽、标记占用、清空后返回指针；释放时根据指针算槽位、清空并标记空闲。添加节点时先从池中取一块，拷贝数据后按双向链表尾插（空链则作为新头，非空则接在尾后）。

#include <stdio.h>
#include <string.h>

#define POOL_SIZE 8
#define SLOT_FREE 0
#define SLOT_USED 1

typedef struct DNode {
int id;
int priority;
struct DNode *prev;
struct DNode *next;
} DNode_t;

/* 内存池：节点数组 + 占用表（槽位 FREE=空闲，USED=已占用） */
static DNode_t node_pool[POOL_SIZE];
static unsigned char slot_used[POOL_SIZE];

static void pool_init(void) {
memset(slot_used, SLOT_FREE, sizeof(slot_used));
memset(node_pool, 0, sizeof(node_pool));
}

/* 从池中分配一个节点：找空闲槽 -> 标记已占用 -> 清空 -> 返回指针 */
static DNode_t* pool_alloc(void) {
for (int i = 0; i < POOL_SIZE; i++) {
if (slot_used[i] == SLOT_FREE) {
slot_used[i] = SLOT_USED;
memset(&node_pool[i], 0, sizeof(DNode_t));
return &node_pool[i];
}
}
return NULL;
}

/* 将节点还回池：根据指针算槽位 -> 清空 -> 标记空闲 */
static void pool_free(DNode_t *node) {
if (node == NULL) return;
DNode_t *base = &node_pool[0];
if (node < base || node >= base + POOL_SIZE) return;
int i = (int)(node – base);
memset(&node_pool[i], 0, sizeof(DNode_t));
slot_used[i] = SLOT_FREE;
}

/* 添加节点：从池中取一块 -> 填数据 -> 按双向链表尾插（空链则作新头） */
static int dlist_append(DNode_t **head, int id, int priority) {
DNode_t *node = pool_alloc();
if (node == NULL) return –1;
node->id = id;
node->priority = priority;
node->next = NULL;

if (*head == NULL) {
node->prev = NULL;
*head = node;
return 0;
}
DNode_t *tail = *head;
while (tail->next != NULL) tail = tail->next;
node->prev = tail;
tail->next = node;
return 0;
}

/* 已知节点指针，O(1) 从链上摘除（不还池，由调用方 pool_free） */
static void dlist_remove(DNode_t **head, DNode_t *node) {
if (head == NULL || *head == NULL || node == NULL) return;
if (node->prev != NULL)
node->prev->next = node->next;
else
*head = node->next;
if (node->next != NULL)
node->next->prev = node->prev;
}

/* 按优先级取节点：遍历找最大 priority，摘除后返回（调用方负责 pool_free） */
static DNode_t* dlist_pop_by_priority(DNode_t **head) {
if (*head == NULL) return NULL;
DNode_t *best = *head;
for (DNode_t *p = *head; p != NULL; p = p->next) {
if (p->priority > best->priority) best = p;
}
dlist_remove(head, best);
return best;
}

int main(void) {
DNode_t *head = NULL;
pool_init();

dlist_append(&head, 1, 1);
dlist_append(&head, 2, 3); /* 高优先级 */
dlist_append(&head, 3, 2);

DNode_t *p = dlist_pop_by_priority(&head);
if (p) {
printf("pop id=%d priority=%d\\n", p->id, p->priority); /* 2, 3 */
pool_free(p);
}
return 0;
}

头插（当已有节点指针时，可将其作为新头）：node->prev = NULL; node->next = *head; 若原头非空则 (*head)->prev = node; 最后 *head = node;。

/* 头插 */
static void dlist_push(DNode_t **head, DNode_t *node) {
node->prev = NULL;
node->next = *head;
if (*head != NULL) (*head)->prev = node;
*head = node;
}

上述 Demo 已体现从内存池创建节点：node_pool + slot_used 构成池，pool_alloc 取节点、pool_free 还回，dlist_append 内部先 pool_alloc 再尾插；取出或删除后由调用方 pool_free 还池。

3.4 使用示例

上面 Demo 中的 main 即完整使用示例：pool_init() 初始化池；三次 dlist_append(&head, id, priority) 从池中取节点并尾插；dlist_pop_by_priority(&head) 按优先级取出节点；用完后 pool_free(p) 还回池。若需“仅链表操作、节点由外部传入”，可单独使用 dlist_remove，并自行保证节点来源与释放方式一致。

3.5 要点小结

3.5.1 移植要点

四、三种技术差异对比

4.1 结构示意

#mermaid-svg-j3BOmiqt3MaR8L2E{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-j3BOmiqt3MaR8L2E .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-j3BOmiqt3MaR8L2E .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-j3BOmiqt3MaR8L2E .error-icon{fill:#552222;}#mermaid-svg-j3BOmiqt3MaR8L2E .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-j3BOmiqt3MaR8L2E .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-j3BOmiqt3MaR8L2E .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-j3BOmiqt3MaR8L2E .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-j3BOmiqt3MaR8L2E .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-j3BOmiqt3MaR8L2E .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-j3BOmiqt3MaR8L2E .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-j3BOmiqt3MaR8L2E .marker{fill:#333333;stroke:#333333;}#mermaid-svg-j3BOmiqt3MaR8L2E .marker.cross{stroke:#333333;}#mermaid-svg-j3BOmiqt3MaR8L2E svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-j3BOmiqt3MaR8L2E p{margin:0;}#mermaid-svg-j3BOmiqt3MaR8L2E .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-j3BOmiqt3MaR8L2E .cluster-label text{fill:#333;}#mermaid-svg-j3BOmiqt3MaR8L2E .cluster-label span{color:#333;}#mermaid-svg-j3BOmiqt3MaR8L2E .cluster-label span p{background-color:transparent;}#mermaid-svg-j3BOmiqt3MaR8L2E .label text,#mermaid-svg-j3BOmiqt3MaR8L2E span{fill:#333;color:#333;}#mermaid-svg-j3BOmiqt3MaR8L2E .node rect,#mermaid-svg-j3BOmiqt3MaR8L2E .node circle,#mermaid-svg-j3BOmiqt3MaR8L2E .node ellipse,#mermaid-svg-j3BOmiqt3MaR8L2E .node polygon,#mermaid-svg-j3BOmiqt3MaR8L2E .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-j3BOmiqt3MaR8L2E .rough-node .label text,#mermaid-svg-j3BOmiqt3MaR8L2E .node .label text,#mermaid-svg-j3BOmiqt3MaR8L2E .image-shape .label,#mermaid-svg-j3BOmiqt3MaR8L2E .icon-shape .label{text-anchor:middle;}#mermaid-svg-j3BOmiqt3MaR8L2E .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-j3BOmiqt3MaR8L2E .rough-node .label,#mermaid-svg-j3BOmiqt3MaR8L2E .node .label,#mermaid-svg-j3BOmiqt3MaR8L2E .image-shape .label,#mermaid-svg-j3BOmiqt3MaR8L2E .icon-shape .label{text-align:center;}#mermaid-svg-j3BOmiqt3MaR8L2E .node.clickable{cursor:pointer;}#mermaid-svg-j3BOmiqt3MaR8L2E .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-j3BOmiqt3MaR8L2E .arrowheadPath{fill:#333333;}#mermaid-svg-j3BOmiqt3MaR8L2E .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-j3BOmiqt3MaR8L2E .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-j3BOmiqt3MaR8L2E .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-j3BOmiqt3MaR8L2E .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-j3BOmiqt3MaR8L2E .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-j3BOmiqt3MaR8L2E .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-j3BOmiqt3MaR8L2E .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-j3BOmiqt3MaR8L2E .cluster text{fill:#333;}#mermaid-svg-j3BOmiqt3MaR8L2E .cluster span{color:#333;}#mermaid-svg-j3BOmiqt3MaR8L2E div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-j3BOmiqt3MaR8L2E .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-j3BOmiqt3MaR8L2E rect.text{fill:none;stroke-width:0;}#mermaid-svg-j3BOmiqt3MaR8L2E .icon-shape,#mermaid-svg-j3BOmiqt3MaR8L2E .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-j3BOmiqt3MaR8L2E .icon-shape p,#mermaid-svg-j3BOmiqt3MaR8L2E .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-j3BOmiqt3MaR8L2E .icon-shape rect,#mermaid-svg-j3BOmiqt3MaR8L2E .image-shape rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-j3BOmiqt3MaR8L2E .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-j3BOmiqt3MaR8L2E .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-j3BOmiqt3MaR8L2E :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

双向非循环链表

单向链表

next

next

next

next

next

next

prev

prev

prev

双向循环链表

next

next

next

prev

prev

prev

Sentinel

N1

N2

N1

N2

N3

NULL

N1

N2

N3

4.2 对比表

五、使用场景与选型

5.1 使用场景

5.2 速查表

六、学习建议

七、移植使用清单

移植时可按下表快速定位要修改的内容；每类链表的详细步骤见各节「移植要点」。

7.1 快速对照表

7.2 移植步骤概览