目录

1. C语言的链表
2. FreeRTOS中的链表实现
3. 链表节点的插入实验

写在最前面的：

列表和列表项是直接从FreeRTOS源码的注释中的list和list item翻译过来的，其实就是我们C语言中的链表和节点。

一、C语言的链表

链表是C语言中的一种基础的数据结构。在操作系统中用的非常多。

举个通俗的例子，链表就像一个晾衣架，节点就是上面的钩子，节点与节点之间首尾相连。钩子不能代表很多东西，但是可以挂很多东西，节点类似，链表的节点不是用来存储大量数据的，但是可以挂很多数据。

链表分为单向链表和双向链表。

1. 单向链表：

   链表的定义？以单向链表为例，如图，该链表有n个节点，前一个节点都有一个箭头指向后一个节点，首尾相连，组成一个圈。

   

   节点本身必须包含一个指向下一个节点的指针，除此以外，还可以携带哪些信息？

   其实，节点就是一个自定义的数据结构，在这个数据结构里面可以有单个的数据，数组，指针数据和自定义的结构体数据类型数据...具体代码如下：

   struct node
   {
       struct node *next;           /* 指向下一个节点 */
   	char data1;                  /* 单个的数据 */
   	unsigned char array[];       /* 数组 */
   	unsigned long *prt;          /* 指针数据 */
   	struct userstruct data2;     /* 自定义结构体类型数据 */
   	/* ...... */
   };

   通常，我们只在节点里包含一个指向下一个节点的指针。我们通过链表存储的数据里内嵌一个节点来实现将存储的数据挂在链表里。具体代码如下：

   

   下面图形帮助理解：

   

2. 双向链表

   与单向链表的区别是，节点中有两个节点指针，一个指向前一个节点，一个指向后一个节点。如下图辅助理解：

   

补充知识点

链表与数组有什么区别？嵌入式面试常问

它们两者确实很像，但实际上，链表是通过节点将离散的数据链接成一个表，通过对节点的插入和删除来实现数据的存取；而数组是通过开辟一段连续的内存空间来存储数据。另外，数组有起始地址和结束地址，而链表是一个圈，没有首尾之分。

我们为了方便节点的插入和删除，人为地引入了一个根节点。这也是我们引入根节点的原因。

二、FreeRTOS中的链表实现

在学习之前，我们要知道：

FreeRTOS中与链表相关的操作都是在list.c和list.h中实现的。第一次使用，我们在include文件夹下新建list.h然后添加到工程FreeRTOS/Source这个组文件，在freertos文件夹下新建list.c然后添加到工程FreeRTOS/Source这个组文件中。

        1. 定义链表节点数据结构

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

                这里要注意：红框标注的分号一定要有。否则报错。

                下面图形帮助理解：             

        这里需要补充的是：

        TickType_t是一个数据类型的重定义，还有很多，都放在了portmacro.h头文件中（首次使用在include文件夹下新建，然后添加到工程FreeRTOS/Source这个组文件中）。如下图(portmacro.h头文件内容)：

      其中我们需要了解的是：

（1）<stdint.h> 是 C 标准库的一部分，旨在解决不同平台上整数类型大小不一致的问题。例如，在某些平台上 int 可能是 16 位，而在另一些平台上是 32 位。这会导致代码在移植时出现问题。<stdint.h> 通过提供固定宽度的整数类型（如 8 位、16 位、32 位、64 位），确保程序行为在不同系统上保持一致。
（2）stddef .h 头文件定义了各种变量类型和宏。这些定义中的大部分也出现在其它头文件中

  2. 链表节点初始化        

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

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

        3. 定义链表根节点的数据结构

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

1. 链表节点计数器，用于表示该链表下有多少个节点，根节点除外。
2. 链表节点索引指针，用于遍历指针。
3. 链表最后一个节点，字面理解是最后一个节点，实际上也是链表的第一个节点，所谓头就是尾，尾也是头，因为链表是一个圈。这个节点我们称之为生产者。

        【这里注意的是，List_t是struct xLIST重定义之后的名字。这是结构体使用typedef数据类型定义的一种方法。区别于独立出来的那种形式，但意义是一样的。】

        链表精简节点结构体在list.h中定义。且放在链表根节点的数据结构前面。

        综上，下面图形帮助理解：

        4. 链表根节点初始化

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

下面图形帮助理解：

        5. 将节点插入到链表的尾部

        也就是将一个新的节点，插入到一个空的链表。

        那么如何将节点插入到链表的尾部呢？

        结合上图理解，假设我们的链表是一个双向链表，假设它前面有一个节点，它们连接的方式就是上图"原来"的指向，此时我们要将一个新的节点插入到链表的尾部，原来的连接也就不复存在，“NEW”指代新的节点，最后要实现步骤是：NEW节点指向的下一个节点就是END（步骤1），而END的上一个也就指向了NEW（步骤4），同样，原来END的上一个节点(尾部前面的节点)的下一个指向NEW（步骤3），原来END的下一个节点也就是NEW的下一个节点（步骤2）。本程序是按照步骤1~4进行编程的(体会用意)。

        将节点插入到链表的尾部在list.c中实现的。如下图（里面的标号与上图指向一致）：

        最后要记录一下它属于哪一个链表，并将该链表的节点计数器加1。

        也可以参考下面的图解：

留下一个问题思考：按照其它的赋值顺序行吗？步骤123打乱顺序，4还放在最后？

        6.将节点按照链表的升序排列插入到链表(放在list.c中)

        这个函数可以结合上一个函数(vListInserEnd())会更好理解。

        这里面的序号可以参考上一小节的第一个图。

        里面的for循环我们可以理解：

        初次，将链表的初值赋给pxIterator这个链表节点的结构体指针。根据pxIterator指向的下一个节点指针里的排序值与新插入节点的排序值做比较，当判断相等时，也就是最后一次执行循环体，此时pxIterator也就是要插入那个位置的上一个节点指针。

        也可以参考下面的图解：

        7. 将节点从链表删除(放在list.c中)

        最后，将要删除的节点的指向链表赋为空，表示不指向任一个链表；同时原来链表的节点计数器-1，并返回当前链表的节点数。

        也可以参考下面的图解：

        8.学习节点带参宏的小函数有哪些？都是怎么实现的

        

/* 初始化节点的拥有者 */
#define listSET_LIST_ITEM_OWNER( pxListItem, pxOwner)\
	   ( ( pxListItem ) ->pvOwner = ( void * ) ( pxOwner ) )
			
/* 读取节点的拥有者 */
#define listGET_LIST_ITEM_OWNER( pxListItem )\
		( ( pxListItem ) -> pvOwner )
			
/* 初始化节点排序辅助值 */
#define listSET_LIST_ITEM_VALUE( pxListItem, xValue )\
		 ( ( pxListItem ) -> xItemValue = ( xValue ))
			
/* 获取节点排序辅助值 */
#define listGET_LIST_ITEM_VALUE( pxListItem )\
		( (pxListItem ) -> xItemValue )
			
/* 获取链表根节点的节点计数器的值 */
#define listGET_ITEM_VALUE_OF_HEAD_ENTRY( pxList )\
		( ( ( pxList ) -> xListEnd ).pxNext -> xItemValue )
			
/* 获取链表的入口节点 */
#define listGET_HEAD_ENTRY( pxList )\
		( ( ( pxList ) -> xListEnd ).pxNext )
			
/* 获取节点的下一个节点 */
#define listGET_NEXT( pxListItem )\
		( ( pxListItem ) -> pxNext )
			
/* 获取链表的最后一个节点 */
#define listGET_END_MARKER( pxList )\
		( ( ListItem_t const * ) ( & ( ( pxList ) -> xListEnd ) ) )
			
/* 判断链表是否为空 */
#define listLIST_IS_EMPTY( pxList )\
		( ( BaseType_t ) ( ( pxList ) -> uxNumberOfItems == ( UBaseType_t ) 0 ) )
			
/* 获取链表的节点数 */
	#define listCURRENT_LIST_LENGTH( pxList )\
			 ( ( pxList ) -> uxNumberOfItems )
			
/* 获取链表第一个节点的OWNER，即TCB */
#define ListGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList )
{
	List_t * const pxConstList = ( pxList );
	/* 节点索引指向链表第一个节点 */     \                                                  
	( pxConstList ) -> pxIndex = ( pxConstList ) -> pxIndex -> pxNext ;                              
	/* 这个操作有啥用 */                \                                                                                        
	if( ( void *) ( pxConstList ) -> pxIndex == ( void * ) & ( ( pxConstList ) -> xListEnd ) )   \
	{
		( pxConstList ) -> pxIndex = ( pxConstList ) -> pxIndex -> pxNext;
	}
	/* 获取节点的OWNER,即TCB */         \                                                                              
	( pxTCB ) = ( pxConstList ) -> pxIndex -> pvOwner;
} 

三、链表节点的插入实验（参考源代码）