FreeRTOS 链表详解

一、链表基础概念

链表是一种动态存储数据的结构，核心是'用指针把离散的节点串起来'，像一串糖葫芦：

• 节点：每个糖葫芦（存储一个数据），包含两部分：
  1. 数据域：存储实际要保存的数据（比如数字、结构体、指针）；
  2. 指针域：存储下一个（或上一个）节点的地址，相当于糖葫芦的竹签，把节点连起来。
• 链表：所有节点通过指针域串联形成的整体，不需要连续的内存空间（和数组最大的区别）。

对比数组，你就能秒懂链表的核心优势：

特性	数组（比如 int arr[10]）	链表
内存分配	连续内存块	离散内存块（按需分配）
插入 / 删除	需移动大量元素（效率低）	只需改指针（效率高）
容量扩展	固定大小（无法动态扩展）	可动态添加节点（无上限）
访问方式	下标直接访问（arr[3]）	必须从头遍历（顺序访问）

二、单向链表与双向链表

FreeRTOS 中用的是双向链表（方便正反遍历、插入删除），但先从单向链表入门，再过渡到双向链表更易理解。

1. 单向链表（入门必备）

• 结构：每个节点只有一个指针，指向下一个节点，最后一个节点的指针为 NULL（表示链表结束）。
• 核心：只能从'头节点'往后遍历，不能反向查找。

（1）单向链表节点定义（C 语言代码）

// 定义节点结构体：数据域 + 指针域
struct Node {
    int data; // 数据域：存储整数（可替换为任意类型，比如结构体）
    struct Node *next; // 指针域：指向同类型的下一个节点
};
// 为了书写方便，重定义类型名（类似 FreeRTOS 的 typedef）
typedef struct Node ListNode;

（2）单向链表的核心操作（3 个最常用）

① 创建节点（申请内存 + 赋值）

// 创建一个新节点，返回节点指针
ListNode* createNode(int data) {
    // 1. 动态分配内存（链表节点通常动态创建，按需分配）
    ListNode *newNode = (ListNode*)malloc(sizeof(ListNode));
    // 2. 给节点赋值
    newNode->data = data; // 数据域存值
    newNode->next = NULL; // 新节点默认是最后一个，next 指向 NULL
    return newNode;
}

② 插入节点（尾部插入，最简单）

1. 找到链表的最后一个节点（最后一个节点的 next 是 NULL）；
2. 把最后一个节点的 next 指针，指向新创建的节点；
3. 新节点的 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，表示它暂时是'最后一个节点'，后续接在链表尾部时才不会出错。

• 步骤 2：判断链表是否为空（if (*head == NULL)）

  • 核心逻辑：如果链表还没有任何节点（头指针 *head 是 NULL），新节点就直接成为'头节点'。
  • 为什么用 ListNode **head（二级指针）？
    • 因为要修改'头指针本身'的值（让它指向新节点）。如果用一级指针 ListNode *head，函数内修改的只是 head 的副本，外部的头指针不会变，链表还是空的。
    • 简单说：要修改指针变量本身，就传它的地址（二级指针）。

• 步骤 3：遍历找到链表尾部（while (p->next != NULL)）

  • 核心目标：找到最后一个节点（next 为 NULL 的节点）。
  • 逐行解释：
    • ListNode *p = *head：定义一个'临时指针 p'，从'头节点'开始遍历（p 一开始指向头节点）；
    • while (p->next != NULL)：循环条件：只要 p 的 next 不是 NULL，说明 p 不是最后一个节点，继续往后找；
    • p = p->next：p 指针'移动'到下一个节点（相当于'顺着糖葫芦的竹签往下走'）。

• 步骤 4：连接新节点（p->next = newNode）

  • 核心操作：把最后一个节点的 next 指针，指向新创建的节点，让新节点成为新的尾部。
  • 为什么新节点的 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;
}

执行流程：

1. 初始状态：ListNode *head = NULL（链表空）；
2. 插入第一个节点（data=10）：
   • newNode：[10] -> NULL；
   • *head == NULL → *head = newNode；
   • 链表：head -> [10] -> NULL；
3. 插入第二个节点（data=20）：
   • newNode：[20] -> NULL；
   • *head != NULL → 定义 p = head（p 指向 [10]）；
   • p->next = NULL（循环不执行）；
   • p->next = newNode → 链表：head -> [10] -> [20] -> NULL；
4. 插入第三个节点（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 个坑（重点提醒）

1. 忘记给新节点的 next 设 NULL：如果 newNode->next 是随机值（malloc 申请的内存未初始化），遍历的时候会陷入死循环；
2. 用一级指针 ListNode *head 当参数：插入第一个节点时，head 的副本被修改，外部 head 还是 NULL，链表始终为空。

2. 双向链表的核心优势

• 可以从表头往后遍历，也可以从表尾往前遍历；
• 删除任意节点时，只需通过 prev 和 next 找到前后节点，直接修改指针即可（无需遍历找前驱）。

比如删除节点 p：

// p 是要删除的节点
p->prev->next = p->next; // 前节点的 next 指向后节点
p->next->prev = p->prev; // 后节点的 prev 指向前节点
free(p); // 释放节点内存

三、FreeRTOS 链表的特殊设计

1. FreeRTOS 链表的特殊设计

• 环形结构：没有'NULL 结尾'，最后一个节点的 next 指向表头，表头的 prev 指向最后一个节点（方便循环遍历）；
• 根节点（xListEnd）：不存储实际数据，仅作为链表的'锚点'（方便插入删除操作，不用判断表头为空）；
• 节点带'辅助值'（xItemValue）：用于排序（比如延时列表按延时时间排序，就绪列表按优先级排序）。

2. 和通用双向链表的对应关系

通用双向链表	FreeRTOS 链表（List）	作用
节点数据域	pvOwner	指向节点的拥有者（比如 TCB）
节点前驱指针	pxPrevious	指向前一个列表项
节点后继指针	pxNext	指向后一个列表项
链表头	xListEnd	链表根节点（锚点）

比如 FreeRTOS 的就绪列表 pxReadyTasksLists，就是一个数组，每个元素是一个双向环形链表，对应一个优先级的任务队列 —— 这就是多任务调度的基础！

四、链表的核心要点总结（必记）

1. 节点是链表的基本单位：必须包含'数据域'和'指针域'；
2. 链表的核心是'指针串联'：通过指针域把离散的内存块连起来，无需连续内存；
3. 动态分配内存：链表节点通常用 malloc 创建（FreeRTOS 中也支持静态分配），按需扩展；
4. 操作核心是'指针移动'：遍历、插入、删除本质都是修改指针指向；
5. FreeRTOS 的链表是'增强版双向环形链表'：为任务管理、排序优化设计，本质还是链表的核心逻辑。

五、动手实践：写一个简单的双向链表（加深理解）

#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;
}