FreeRTOS 链表详解

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

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 的就绪列表 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;
}