FreeRTOS链表详解
一、先搞懂：链表到底是什么？
链表是一种动态存储数据的结构，核心是 “用指针把离散的节点串起来”，像一串糖葫芦：
- 「节点」：每个糖葫芦（存储一个数据），包含两部分：
- 数据域：存储实际要保存的数据（比如数字、结构体、指针）；
- 指针域：存储下一个（或上一个）节点的地址，相当于糖葫芦的竹签，把节点连起来。
- 「链表」：所有节点通过指针域串联形成的整体，不需要连续的内存空间（和数组最大的区别）。
对比数组，你就能秒懂链表的核心优势：
| 特性 | 数组（比如int arr[10]） | 链表 |
|---|---|---|
| 内存分配 | 连续内存块 | 离散内存块（按需分配） |
| 插入 / 删除 | 需移动大量元素（效率低） | 只需改指针（效率高） |
| 容量扩展 | 固定大小（无法动态扩展） | 可动态添加节点（无上限） |
| 访问方式 | 下标直接访问（arr[3]） | 必须从头遍历（顺序访问） |
二、最基础的两种链表：单向链表 vs 双向链表
FreeRTOS 中用的是双向链表（方便正反遍历、插入删除），但先从单向链表入门，再过渡到双向链表更易理解。
1. 单向链表（入门必备）
- 结构：每个节点只有一个指针，指向下一个节点，最后一个节点的指针为
NULL（表示链表结束）。 - 核心：只能从 “头节点” 往后遍历，不能反向查找。
（1）单向链表节点定义（C 语言代码）
c
运行
// 定义节点结构体：数据域 + 指针域 struct Node { int data; // 数据域：存储整数（可替换为任意类型，比如结构体） struct Node *next; // 指针域：指向同类型的下一个节点 }; // 为了书写方便，重定义类型名（类似FreeRTOS的typedef） typedef struct Node ListNode; （2）单向链表的核心操作（3 个最常用）
① 创建节点（申请内存 + 赋值）
c
运行
// 创建一个新节点，返回节点指针 ListNode* createNode(int data) { // 1. 动态分配内存（链表节点通常动态创建，按需分配） ListNode *newNode = (ListNode*)malloc(sizeof(ListNode)); // 2. 给节点赋值 newNode->data = data; // 数据域存值 newNode->next = NULL; // 新节点默认是最后一个，next指向NULL return newNode; }② 插入节点（尾部插入，最简单）
- 找到链表的最后一个节点（最后一个节点的
next是NULL）； - 把最后一个节点的
next指针，指向新创建的节点； - 新节点的
next保持NULL（因为它现在是新的尾部）。
// 单链表节点定义 typedef struct Node { int data; // 数据域 struct Node *next; // 指针域：指向下一个节点 } ListNode; // 尾部插入节点：head是链表头指针的地址（二级指针） void insertNode(ListNode **head, int data) { // 步骤1：创建新节点 ListNode *newNode = createNode(data); // 步骤2：如果链表为空，新节点就是头节点 if (*head == NULL) { *head = newNode; return; } // 步骤3：遍历找到链表最后一个节点 ListNode *p = *head; while (p->next != NULL) { p = p->next; // 指针后移，直到找到最后一个节点 } // 步骤4：把新节点接在最后一个节点后面 p->next = newNode; } // 创建新节点（辅助函数） ListNode* createNode(int data) { ListNode *newNode = (ListNode*)malloc(sizeof(ListNode)); // 申请内存 newNode->data = data; // 给数据域赋值 newNode->next = NULL; // 新节点默认是尾部，next指向NULL return newNode; }步骤 1：创建新节点（createNode函数）
- 核心作用：申请一块内存，封装 “数据” 和 “指针”，形成一个独立的节点。
- 关键代码解释：
(ListNode*)malloc(sizeof(ListNode))：向系统申请一块和ListNode结构体大小相同的内存，强制转换为ListNode*类型（因为malloc返回void*）；newNode->next = NULL：这是尾部插入的关键！新节点一开始是 “孤立” 的，它的next必须设为NULL，表示它暂时是 “最后一个节点”，后续接在链表尾部时才不会出错。
示意图（新节点创建后）：plaintext
newNode: [data=传入的值] -> next = NULL 步骤 2：判断链表是否为空（if (*head == NULL)）
- 核心逻辑：如果链表还没有任何节点（头指针
*head是NULL），新节点就直接成为 “头节点”。 - 为什么用
ListNode **head（二级指针）？- 因为要修改 “头指针本身” 的值（让它指向新节点）。如果用一级指针
ListNode *head，函数内修改的只是head的副本，外部的头指针不会变，链表还是空的。 - 简单说：要修改指针变量本身，就传它的地址（二级指针）。
- 因为要修改 “头指针本身” 的值（让它指向新节点）。如果用一级指针
示意图（链表为空时插入）：plaintext
插入前：*head = NULL（链表空） 插入后：*head -> newNode: [data=值] -> next = NULL 步骤 3：遍历找到链表尾部（while (p->next != NULL)）
- 核心目标：找到最后一个节点（
next为NULL的节点）。 - 逐行解释：
ListNode *p = *head：定义一个 “临时指针p”，从 “头节点” 开始遍历（p一开始指向头节点）；while (p->next != NULL)：循环条件：只要p的next不是NULL，说明p不是最后一个节点，继续往后找；p = p->next：p指针 “移动” 到下一个节点（相当于 “顺着糖葫芦的竹签往下走”）。
- 示意图（遍历过程）：假设链表已有节点：
head -> 节点1 -> 节点2 -> NULL- 初始：
p = 节点1（p->next = 节点2，不是NULL，进入循环）； - 第一次循环：
p = p->next→p = 节点2（p->next = NULL，循环结束）； - 最终：
p指向最后一个节点（节点 2）。
- 初始：
步骤 4：连接新节点（p->next = newNode）
- 核心操作：把最后一个节点的
next指针，指向新创建的节点，让新节点成为新的尾部。 - 示意图（连接后）：连接前：
节点2 -> NULL，newNode -> NULL连接后：节点2 -> newNode -> NULL - 为什么新节点的
next不用改？- 因为
createNode中已经把newNode->next设为NULL，连接后它自然是最后一个节点，无需额外操作。
- 因为
（3）单向链表使用示例
int main() { ListNode *head = NULL; // 链表头指针，初始为空 // 插入3个节点 insertNode(&head, 10); insertNode(&head, 20); insertNode(&head, 30); // 遍历链表，输出：10 20 30 traverseList(head); return 0; }- 初始状态：
ListNode *head = NULL（链表空）； - 插入第一个节点（data=10）：
newNode：[10] -> NULL；*head == NULL→*head = newNode；- 链表：
head -> [10] -> NULL；
- 插入第二个节点（data=20）：
newNode：[20] -> NULL；*head != NULL→ 定义p = head（p指向 [10]）；p->next = NULL（循环不执行）；p->next = newNode→ 链表：head -> [10] -> [20] -> NULL；
- 插入第三个节点（data=30）：
newNode：[30] -> NULL；p = head（指向 [10]）；p->next = [20] != NULL→p = p->next（指向 [20]）；p->next = NULL（循环结束）；p->next = newNode→ 链表：head -> [10] -> [20] -> [30] -> NULL。
最容易踩的 2 个坑（重点提醒）
- 忘记给新节点的
next设NULL：如果newNode->next是随机值（malloc 申请的内存未初始化），遍历的时候会陷入死循环； - 用一级指针
ListNode *head当参数：插入第一个节点时，head的副本被修改，外部head还是NULL，链表始终为空。
（2）双向链表的核心优势
- 可以从表头往后遍历，也可以从表尾往前遍历；
- 删除任意节点时，只需通过
prev和next找到前后节点，直接修改指针即可（无需遍历找前驱）。
比如删除节点p：
c
运行
// p是要删除的节点 p->prev->next = p->next; // 前节点的next指向后节点 p->next->prev = p->prev; // 后节点的prev指向前节点 free(p); // 释放节点内存1. FreeRTOS 链表的特殊设计
- 环形结构：没有 “NULL 结尾”，最后一个节点的
next指向表头，表头的prev指向最后一个节点（方便循环遍历）； - 根节点（xListEnd）：不存储实际数据，仅作为链表的 “锚点”（方便插入删除操作，不用判断表头为空）；
- 节点带 “辅助值”（xItemValue）：用于排序（比如延时列表按延时时间排序，就绪列表按优先级排序）。
2. 和通用双向链表的对应关系
| 通用双向链表 | FreeRTOS 链表（List） | 作用 |
|---|---|---|
| 节点数据域 | pvOwner | 指向节点的拥有者（比如 TCB） |
| 节点前驱指针 | pxPrevious | 指向前一个列表项 |
| 节点后继指针 | pxNext | 指向后一个列表项 |
| 链表头 | xListEnd | 链表根节点（锚点） |
比如 FreeRTOS 的就绪列表pxReadyTasksLists，就是一个数组，每个元素是一个双向环形链表，对应一个优先级的任务队列 —— 这就是多任务调度的基础！
四、链表的核心要点总结（必记）
- 节点是链表的基本单位：必须包含 “数据域” 和 “指针域”；
- 链表的核心是 “指针串联”：通过指针域把离散的内存块连起来，无需连续内存；
- 动态分配内存：链表节点通常用
malloc创建（FreeRTOS 中也支持静态分配），按需扩展； - 操作核心是 “指针移动”：遍历、插入、删除本质都是修改指针指向；
- FreeRTOS 的链表是 “增强版双向环形链表”：为任务管理、排序优化设计，本质还是链表的核心逻辑。
五、动手实践：写一个简单的双向链表（加深理解）
c
运行
#include <stdio.h> #include <stdlib.h> // 双向链表节点定义 typedef struct DoubleNode { int data; struct DoubleNode *prev; struct DoubleNode *next; } DoubleListNode; // 创建节点 DoubleListNode* createDoubleNode(int data) { DoubleListNode *newNode = (DoubleListNode*)malloc(sizeof(DoubleListNode)); newNode->data = data; newNode->prev = NULL; newNode->next = NULL; return newNode; } // 尾部插入节点 void insertDoubleNode(DoubleListNode **head, int data) { DoubleListNode *newNode = createDoubleNode(data); if (*head == NULL) { *head = newNode; return; } DoubleListNode *p = *head; while (p->next != NULL) { p = p->next; } p->next = newNode; newNode->prev = p; // 双向链表：新节点的prev指向最后一个节点 } // 遍历链表（正序） void traverseDoubleList(DoubleListNode *head) { DoubleListNode *p = head; while (p != NULL) { printf("%d ", p->data); p = p->next; } printf("\n"); } // 主函数测试 int main() { DoubleListNode *head = NULL; insertDoubleNode(&head, 100); insertDoubleNode(&head, 200); insertDoubleNode(&head, 300); traverseDoubleList(head); // 输出：100 200 300 return 0; }
