FreeRTOS链表实现学习

（1）链表节点的数据结构在list.h中建立// 节点值，通常用于排序（如任务唤醒时间）// 指向下一个节点的指针// 指向前一个节点的指针// 指向拥有此节点的对象（如任务控制块）// 指向此节点所属的链表容器//节点数据类型重定义辅助值用于帮助节点进行顺序排列，辅助值数据类型TickType_t，在Freertos中，凡是涉及数据类型的地方，Freertos都会将标准的C数据类型用typede

lllllllccccc

647人浏览 · 2026-01-08 15:31:02

lllllllccccc · 2026-01-08 15:31:02 发布

FreeRtos中链表的实现

FreeRtos中与链表相关的操作均在list.h和list.c这两个文件中实现

list.h在include文件夹下建立添加至freertos\source工程文件下

list.c在freertos文件夹下建立添加至freertos\source工程文件下

1.实现链表节点

1.1定义链表节点数据结构

（1）链表节点的数据结构在list.h中建立

struct xLIST_ITEM
{
    TickType_t xITEMValue;           // 节点值，通常用于排序（如任务唤醒时间）
    struct xLIST_ITEM *pxNext;       // 指向下一个节点的指针
    struct xLIST_ITEM *pxPrevious;   // 指向前一个节点的指针
    void *pvOwner;                   // 指向拥有此节点的对象（如任务控制块）
    void *pvContainer;               // 指向此节点所属的链表容器
};
typedef struct xLIST_ITEM ListItem_t;  //节点数据类型重定义

辅助值用于帮助节点进行顺序排列，辅助值数据类型TickType_t，在Freertos中，凡是涉及数据类型的地方，Freertos都会将标准的C数据类型用typedef重新设置一个类型名

void *pvOwner; // 指向拥有此节点的对象（如任务控制块）用于指向该节点的拥有者，即该节点内嵌在哪个数据结构中，属于哪个数据结构的成员

经过重定义的数据类型放在portmacro.h放在include文件夹下新建；添加至freertos\source工程文件下

（2）数据类型重定义portmacro.h

#ifndef PORTMACRO_H
#define PORTMACRO_H

#include "stdint.h"
#include "stddef.h"

/*Êý¾ÝÀàÐÍÖØ¶¨Òå*/
#define portCHAR  char
#define portFLOAT float
#define portDOUBLE double
#define portLONG long
#define portSHORT short
#define portSTACK_TYPE uint32_t
#define portBASE_TYPE long

typedef portSTACK_TYPE StackType_t;
typedef long BaseType_t;
typedef unsigned long UBaseType_t;

#if( configUSE_16_BIT_TICKS==1)
typedef uint16_t TickType_t;
#define portMAX_DELAY (TickType_t) 0xffff
#else
typedef uint32_t TickType_t;
#define portMAX_DELAY (TickType_t) 0xffffffffUL
#endif

#endif/* PORTMACRO_H */

TickType_t具体表示16位或32位由configUSE_16_BIT_TICKS这个宏决定，当该宏定义为1时，TickType_t为16位，否则#else部分将会被使用，即默认使用32位。

该宏在FreeRTOSConfig.h放在include文件夹下新建；添加至freertos\source工程文件下

（3）FreeRTOSConfig.h文件

#ifndef FREERTOS_CONFIG_H
#define FREERTOS_CONFIG_H

#define configUSE_16_BIT_TICKS        0

#endif/*FREERTOS_CONFIG_H*/

1.2链表节点初始化

链表节点初始化函数在list.c中实现

void vListInitialiseItem(ListItem_t *const pxItem)
{
	pxItem->pvContaimer=NULL;
	
}

链表节点初始化，链表节点ListItem_t一共有5个成员，但是初始化时只需要将pvContainer初始化为空即可，表示该节点还没有插入任何链表。

2.实现链表根节点

2.1定义链表根节点数据结构

链表根节点的数据结构在list.h中定义

typedef struct xLIST
{
	UBaseType_t uxNumberOfItems;   /*链表节点计数器*/
	ListItem_t *pxIndex;           /*链表节点索引指针*/
	MiniListItem_t xListEnd;       /*链表最后一个节点*/
}List_t;

链表节点计数器：用于表示该链表下有多少个节点，根节点除外、

链表节点索引指针：用于遍历节点

链表最后一个节点链表是首尾相连的，是一个圈，首就是尾，尾就是首，从字面意思理解就是链表的最后一个节点，实际上也就是链表的第一个节点，称为生产者，该生产者的数据类型是精简的节点，在list.h中定义

链表精简节点结构体定义

//Á´±í¾«¼ò½Úµã½á¹¹Ìå¶¨Òå
struct xMINI_LIST_ITEM
{
		TickType_t xITEMValue;  //¸¨ÖúÖµ£¬ÓÃÓÚ°ïÖú½Úµã½øÐÐË³ÐòÅÅÁÐ(ÉýÐò)
		struct xLIST_ITEM *pxNext; //Ö¸ÏòÁ´±íÏÂÒ»¸ö½Úµã
		struct xLIST_ITEM *pxPrevious;  //Ö¸ÏòÁ´±íÉÏÒ»¸ö½Úµã

	
};typedef struct xMINI_LIST_ITEM MiniListItem_t;  //½ÚµãÊý¾ÝÀàÐÍÖØ¶¨Òå

2.2链表根节点初始化

链表根节点初始化在list.c中实现

void vListInitialise(List_t *const pxList)
{
	/*½«Á´±íË÷ÒýÖ¸ÕëÖ¸Ïò×îºóÒ»¸ö½Úµã*/
	pxList->pxIndex=(ListItem_t * )&(pxList->xListEnd);
	
	/*½«Á´±í×îºóÒ»¸ö½ÚµãµÄ¸¨ÖúÅÅÐòµÄÖµÉèÖÃÎª×î´ó£¬È·±£¸Ã½Úµã¾ÍÊÇÁ´±íµÄ×îºó½Úµã*/
	pxList->xListEnd.xItemValue=portMAX_DELAY;
	
	/*½«×îºóÒ»¸ö½ÚµãµÄpxNextºÍpxPreviousÖ¸Õë¾ùÖ¸Ïò×ÔÉí*/
	pxList->xListEnd.pxNext=(ListItem_t * )&(pxList->xListEnd);
	pxList->xListEnd.pxPrevious=(ListItem_t * )&(pxList->xListEnd);
	
	/*³õÊ¼»¯Á´±í½Úµã¼ÆÊýÆ÷µÄÖµÎª0£¬±íÊ¾Á´±íÎª¿Õ*/
	pxList->uxNumberOfItems( UBaseType_t )  0U;
}

将列表索引指针指向最后一个节点，即第一个节点，或第0个节点更准确，因为这个节点不会计入节点计数器

将链表最后一个（也可以理解为第一个）节点的辅助排序的值设置为最大，确保该节点就是链表的最后节点、

将最后一个节点的pxNext和pxPrevious指针均指向节点自身，表示链表为空

初始化链表节点计数器的值为0，表示链表为空

2.3将节点插入链表尾部

将节点插入链表尾部（头部），就是将一个新的节点插入一个空的链表

void vListInsertEnd(List_t *const pxList,ListItem_t *const pxNewListItem)
{
    // 1. 保存链表当前的索引节点（pxIndex是链表的"锚点"，尾插操作围绕它展开）
    ListItem_t *const pxIndex=pxList->pxIndex;
    
    // 2. 新节点的next指向索引节点（因为是循环链表，索引节点是尾插的"边界"）
    pxNewListItem->pxNext=pxIndex;
    // 3. 新节点的previous指向索引节点的原前驱节点（也就是链表的最后一个节点）
    pxNewListItem->pxPrevious=pxIndex->pxPrevious;
    // 4. 原最后一个节点的next指向新节点（完成前驱节点的链接）
    pxIndex->pxPrevious->pxNext=pxNewListItem;
    // 5. 索引节点的previous指向新节点（完成索引节点与新节点的链接）
    pxIndex->pxPrevious=pxNewListItem;
    
    // 6. 标记新节点所属的链表（方便后续判断节点属于哪个链表）
    pxNewListItem->pvContainer=(void*)pxList;
    // 7. 链表节点计数+1（维护链表的节点总数）
    (pxList->uxNumberOfItems)++;
}

假设原链表结构：pxIndex <-> 节点A <-> 节点B <-> pxIndex（pxIndex 是索引节点，节点 B 是最后一个节点）插入新节点后结构：pxIndex <-> 节点A <-> 节点B <-> 新节点 <-> pxIndex

关键步骤的逻辑：

新节点的pxNext = 索引节点（pxIndex）
新节点的pxPrevious = 索引节点的原前驱（节点 B）
节点 B 的pxNext = 新节点
索引节点的pxPrevious = 新节点

2.4将节点按照升序排列插入链表

 /*将节点按照升序排列插入链表*/
void vListInsert(List_t *const pxList, ListItem_t *const pxNewListItem)
{
    ListItem_t *pxIterator;  // 迭代器，用于遍历链表找插入位置
    /*获取节点的排序辅助值*/
    const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;
    
    /*寻找节点要插入的位置*/
    if(xValueOfInsertion == portMAX_DELAY)
    {
        // 如果插入值是最大延迟值（特殊值），直接插入到链表尾端（xListEnd的前一个位置）
        pxIterator = pxList->xListEnd.pxPrevious;
    }
    else
    {
        // 从链表的哨兵节点（xListEnd）开始遍历，找到第一个"下一个节点值 > 插入值"的位置
        for(pxIterator = (ListItem_t *)&(pxList->xListEnd);
                pxIterator->pxNext->xItemValue <= xValueOfInsertion;
                pxIterator = pxIterator->pxNext)
        {
            // 循环体为空，仅通过for条件遍历找位置
        }	
    }

    /*根据升序排列，将节点插入到找到的位置（pxIterator和其下一个节点之间）*/
    // 1. 新节点的下一个节点 = 迭代器当前节点的下一个节点
    pxNewListItem->pxNext = pxIterator->pxNext;
    // 2. 原下一个节点的前一个节点 指向新节点（双向链表反向关联）
    pxNewListItem->pxNext->pxPrevious = pxNewListItem;
    // 3. 新节点的前一个节点 = 迭代器当前节点
    pxNewListItem->pxPrevious = pxIterator;
    // 4. 迭代器当前节点的下一个节点 指向新节点（完成插入）
    pxIterator->pxNext = pxNewListItem;
    
    /*记录该节点所在的链表（标记节点归属）*/
    pxNewListItem->pvContainer = (void *)pxList;
    
    /*链表节点计数器+1（更新链表长度）*/
    (pxList->uxNumberOfItems)++;
}

数据结构背景（FreeRTOS 链表特性）：
- List_t：链表结构体，包含哨兵节点xListEnd（链表头尾的边界，不存储业务数据）、节点数uxNumberOfItems等。
- ListItem_t：链表节点结构体，核心成员：
  - xItemValue：排序用的数值（比如 FreeRTOS 中是任务的延时时间）；
  - pxNext/pxPrevious：双向链表的前后节点指针；
  - pvContainer：指向节点所属的链表（避免节点被重复插入多个链表）。
- portMAX_DELAY：FreeRTOS 的宏，代表最大的延时值（特殊值，插入时直接放到链表末尾）。
插入位置查找逻辑：
- 特殊值处理：如果xItemValue是portMAX_DELAY，直接插入到链表尾（哨兵节点前），因为这是优先级最低的节点（比如延时最长的任务）；
- 普通值处理：从哨兵节点开始遍历，找到第一个 “下一个节点值> 插入值” 的位置，保证插入后链表仍升序。
双向链表插入操作：插入核心是 4 步指针操作（对应代码中 4 行赋值），以pxIterator为 “锚点”，把新节点夹在pxIterator和pxIterator->pxNext之间，同时维护双向链表的正反指针关联，避免链表断裂。
边界安全：哨兵节点xListEnd的存在，让链表遍历无需判断 “是否到尾”，简化了边界条件处理（比如空链表插入、尾部插入都能统一逻辑）。

假设链表初始状态（升序）：xListEnd <-> 节点A(值10) <-> 节点B(值20) <-> xListEnd现在插入节点C(值15)：

遍历找位置：pxIterator从xListEnd开始，检查pxIterator->pxNext（节点 A）值 10 ≤15 → 移动到节点 A；再检查pxIterator->pxNext（节点 B）值 20 >15 → 停止，pxIterator指向节点 A。
插入操作：
- 节点 C 的 pxNext = 节点 A 的 pxNext（节点 B）；
- 节点 B 的 pxPrevious = 节点 C；
- 节点 C 的 pxPrevious = 节点 A；
- 节点 A 的 pxNext = 节点 C；
最终链表：xListEnd <-> 节点A(10) <-> 节点C(15) <-> 节点B(20) <-> xListEnd，节点数从 2 变为 3。

for 循环的标准结构是 for(初始化; 条件判断; 每次循环后执行)，我们逐个分析：

1. 初始化：`pxIterator = (ListItem_t *)&(pxList->xListEnd)`

作用：把遍历的 “起点” 设置为链表的哨兵节点（xListEnd）。
为什么选这里？FreeRTOS 的链表是 “环形双向链表”，xListEnd 是一个不存储业务数据的边界节点（既当尾也当头），从它开始遍历能统一处理 “空链表”“插入到头部” 等所有场景，不用额外写边界判断。
类型转换 (ListItem_t *)：确保pxIterator（ListItem_t*类型）能正确指向xListEnd（ListEnd_t类型，和ListItem_t结构兼容）。

2. 条件判断：`pxIterator->pxNext->xItemValue <= xValueOfInsertion`

作用：判断 “当前节点的下一个节点值” 是否小于等于 “要插入的节点值”，如果满足，说明还没找到插入位置，继续循环。
核心逻辑（升序插入的关键）：我们要找的是「第一个 “下一个节点值> 插入值”」的位置，此时pxIterator就停在这个位置的前一个节点，新节点正好插在pxIterator和它的下一个节点之间。
举例理解：假设链表节点值是 10 → 20 → 30（哨兵节点 xListEnd 在首尾），要插入值 15：
- 初始pxIterator指向 xListEnd，检查xListEnd->pxNext（值 10）≤15 → 满足，继续；
- pxIterator移动到值 10 的节点，检查10->pxNext（值 20）≤15 → 不满足，循环停止；
- 最终pxIterator停在值 10 的节点，新节点 15 就插在 10 和 20 之间。

3. 每次循环后执行：`pxIterator = pxIterator->pxNext`

作用：把遍历指针往后移动一个节点，继续检查下一个位置。
因为循环体是空的，所有遍历逻辑都靠这一步完成。

2.5将节点从链表中删除

/*将节点从链表中移除*/
UBaseType_t uxListRemove(ListItem_t *const pxItemToRemove)
{
    /*获取节点所属的链表（从节点的pvContainer字段读取）*/
    List_t *const pxList = (List_t *)pxItemToRemove->pvContainer;

    /*将指定的节点从双向链表中移除（核心指针操作）*/
    // 1. 被移除节点的下一个节点，其前驱指针指向被移除节点的前驱节点
    pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
    // 2. 被移除节点的前驱节点，其后继指针指向被移除节点的下一个节点
    pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;

    /*调整链表的节点索引指针（pxIndex是链表的遍历索引，避免索引失效）*/
    if(pxList->pxIndex == pxItemToRemove)
    {
        // 如果当前链表的遍历索引正好指向被移除节点，将索引指向其前驱节点
        pxList->pxIndex = pxItemToRemove->pxPrevious;
    }

    /*初始化该节点的所属链表为空，表示该节点未插入任何链表*/
    pxItemToRemove->pvContainer = NULL;

    /*链表节点计数器-1（更新链表长度）*/
    (pxList->uxNumberOfItems)--;

    /*返回链表中剩余节点的个数*/
    return pxList->uxNumberOfItems;
}

假设链表状态：xListEnd <-> A(10) <-> C(15) <-> B(20) <-> xListEnd，且pxIndex指向 C 节点：

移除 C 节点：
- A 的后继指针指向 B，B 的前驱指针指向 A；
- 因为pxIndex原本指向 C，所以更新为 C 的前驱（A 节点）；
- C 的pvContainer设为 NULL，链表节点数从 3 变为 2；
最终链表：xListEnd <-> A(10) <-> B(20) <-> xListEnd，pxIndex指向 A，返回值为 2。

注意：

pxIndex 是List_t结构体中的一个遍历索引指针（FreeRTOS 用于遍历链表的游标）；
如果当前索引正好指向被移除的节点，必须更新索引（指向其前驱），否则后续遍历会访问到已移除的无效节点，导致程序崩溃；
若索引不指向被移除节点，则无需处理，不影响遍历逻辑。

3.链表节点插入实验

新建一个根节点（也可以理解为链表）和3个普通节点，然后将这3个普通节点按照节点的排序辅助值做升序排列插入链表中

#include "list.h"


/*¶¨ÒåÁ´±í¸ù½Úµã*/
struct xLIST List_Test;
/*¶¨Òå½Úµã*/
struct xLIST_ITEM  List_Item1;
struct xLIST_ITEM  List_Item2;
struct xLIST_ITEM  List_Item3;



int main(void)
{
	/*Á´±í¸ù½Úµã³õÊ¼»¯*/
	vListInitialise(&List_Test);
	/*½Úµã1¡¢2¡¢3³õÊ¼»¯*/
	vListInitialiseItem(&List_Item1);
	List_Item1.xITEMValue=1;
	
	vListInitialiseItem(&List_Item2);
	List_Item2.xITEMValue=2;
	
	vListInitialiseItem(&List_Item3);
	List_Item3.xITEMValue=3;
	
	/*½«½Úµã²åÈëÁ´±í£¬°´ÉýÐòÅÅÁÐ*/
	vListInsert(&List_Test,&List_Item1);
	vListInsert(&List_Test,&List_Item3);
	vListInsert(&List_Test,&List_Item2);
	
	for(;;)
	{
	}
}