摘要：前面说了单向链表，今天再结合一下FreeRTOS的链表源码说一下双向链表。注：链表项就是节点，节点就是链表项，都是指的一个东西，叫啥都无所谓。

一、定义链表结构体

//定义链表，同时也是链表头
typedef struct xLIST
{  
    volatile unsigned   int uxNumberOfItems;   
    ListItem_t *  pxIndex; 
    MiniListItem_t xListEnd;                          
} List_t;

二、定义mini节点项

迷你节点也是节点，但迷你节点仅用于标记链表的末尾和挂载其他插入链表中的节点，用户是用不到迷你节点的，链表头节点和普通节点可以不一样

typedef struct xMINI_LIST_ITEM
{
    volatile unsigned   int xItemValue;   /* 辅助值，用于帮助节点做升序排列. */
    struct xLIST_ITEM   * pxNext; 
    struct xLIST_ITEM   * pxPrevious;
}MiniListItem_t;

下面这个头即使链表定义，也是链表头，链表头节点和普通节点可以不一样

三、定义节点

节点在FreeRTOS中叫做链表项

//定义链表节点
typedef struct xLIST_ITEM
{       
    volatile unsigned   int  xItemValue;          
    struct xLIST_ITEM *  pxNext;     
    struct xLIST_ITEM *  pxPrevious; 
    void * pvOwner;                       //用于指向该节点的拥有者              
    struct xLIST *  pxContainer;          //用于指向该节点所在的链表，通常指向链表的根节点
              
}ListItem_t;

四、初始化链表

初始化链表就是给链表的头结点各个参数赋值

void vListInitialise( List_t * const pxList)
{
    /*初始化时，列表中的列表项数量为 0（不包含 xListEnd） */
    pxList->uxNumberOfItems = 0;    
    /* 初始化时，列表中只有 xListEnd，因此 pxIndex 指向 xListEnd */
    pxList->pxIndex = (ListItem_t *) &(pxList->xListEnd); 
    /* xListEnd 的值初始化为最大值，用于列表项升序排序时，排在最后 */
    pxList->xListEnd.xItemValue = portMAX_DELAY;    
    /* 初始化时，列表中只有 xListEnd，因此上一个和下一个列表项都为 xListEnd 本身 */
    pxList->xListEnd.pxNext =(ListItem_t *) &(pxList->xListEnd); 
    pxList->xListEnd.pxPrevious = (ListItem_t *) &(pxList->xListEnd); 
}

左右两个图意思都一样

五、初始化节点

void vListInitialiseItem(ListItem_t * const pxItem )
{
   /* 初始化时，列表项所在列表设为空 */
    pxItem->pxContainer = NULL;
}

六、将节点插入到链表的尾部

void vListInsertEnd( List_t * const pxList,ListItem_t * const pxNewListItem )
{
    /* 获取列表 pxIndex 指向的列表项 */
    ListItem_t * const headEnd = pxList->pxIndex;
    /* 更新待插入列表项的指针成员变量 */
    pxNewListItem->pxNext = headEnd;
    pxNewListItem->pxPrevious = headEnd->pxPrevious;
    /* 更新列表中原本列表项的指针成员变量 */
    headEnd->pxPrevious->pxNext = pxNewListItem;
    headEnd->pxPrevious = pxNewListItem;
        /* 标记待插入列表项的所在列表成员变量 */
    pxNewListItem->pxContainer = pxList;
   /* 列表中列表项的数量+1 */
    (pxList->uxNumberOfItems)++;
}

此函数就是将待插入的列表项插入到列表 pxIndex 指向列表项的前面，要注意的时，pxIndex 不一定指向 xListEnd，而是有可能指向列表中任意一个列表项。

我手画一张图来解释吧

七、链表节点插入并排序

void vListInsert( List_t * const pxList,ListItem_t * const pxNewListItem )
{
    ListItem_t * pxIterator;
    const int xValueOfInsertion = pxNewListItem->xItemValue;

    /* 如果待插入列表项的值为最大值 */
    if( xValueOfInsertion == portMAX_DELAY)
    {
        /* 插入的位置为列表 xListEnd 前面 */
        pxIterator = pxList->xListEnd.pxPrevious;
    }
    else
    {
         /* 遍历列表中的列表项，找到插入的位置 */
        for( pxIterator = (ListItem_t*)&(pxList->xListEnd); pxIterator->pxNext->xItemValue <= xValueOfInsertion; pxIterator = pxIterator->pxNext )
        {
            
        }
    }
 /* 根据升序排列，将节点插入  在pxIterator后面插入新节点*/   
    pxNewListItem->pxNext = pxIterator->pxNext;
    pxNewListItem->pxNext->pxPrevious = pxNewListItem;
    pxNewListItem->pxPrevious = pxIterator;
    pxIterator->pxNext = pxNewListItem;
     
    /* 记住该节点所在的链表 */
    pxNewListItem->pxContainer = pxList;
   /* 链表节点计数器++ */
    ( pxList->uxNumberOfItems )++;
}

在将待插入列表项插入列表之前，会前遍历列表，找到待插入列表项需要插入的位置。待插入列表项需要插入的位置是依照列表中列表项的值按照升序排序确定的。

八、删除链表节点

int uxListRemove( ListItem_t * const pxItemToRemove )
{
 /* 获取节点所在的链表 */
    List_t * const pxList = pxItemToRemove->pxContainer;
 
 /* 将指定的节点从链表删除*/
    pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
    pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;
    

    /* 如果 pxIndex 正指向待移除的列表项 */
    if( pxList->pxIndex == pxItemToRemove )
    {
        /* pxIndex 指向上一个列表项 */
        pxList->pxIndex = pxItemToRemove->pxPrevious;
    }
    else
    {

    }
   /* 将待移除列表项的所在列表指针清空 */
    pxItemToRemove->pxContainer = NULL;
   /* 链表节点计数器-- */
    ( pxList->uxNumberOfItems )--;
   /* 返回链表中剩余节点的个数 */
    return pxList->uxNumberOfItems;
}

要删除节点，首先就必须要找到节点

要注意的是函数 uxListRemove()移除后的列表项，依然于列表有着单向联系，即移除后列表项中用于指向上一个和下一个列表项的指针，依然指向列表中的列表项。

九、实例

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//定义链表节点
typedef struct xLIST_ITEM
{       
    volatile unsigned   int  xItemValue;          
    struct xLIST_ITEM *  pxNext;     
    struct xLIST_ITEM *  pxPrevious; 
    void * pvOwner;                       //用于指向该节点的拥有者              
    struct xLIST *  pxContainer;          //用于指向该节点所在的链表，通常指向链表的根节点
              
}ListItem_t;

typedef struct xMINI_LIST_ITEM
{
    volatile unsigned   int xItemValue;   /* 辅助值，用于帮助节点做升序排列. */
    struct xLIST_ITEM   * pxNext; 
    struct xLIST_ITEM   * pxPrevious;
}MiniListItem_t;

//定义链表，同时也是链表头
typedef struct xLIST
{  
    volatile unsigned   int uxNumberOfItems;   
    ListItem_t *  pxIndex; 
    MiniListItem_t xListEnd;                          
} List_t;

void vListInitialise( List_t * const pxList)
{
    pxList->uxNumberOfItems = 0;    
    pxList->pxIndex = (ListItem_t *) &(pxList->xListEnd); 
    pxList->xListEnd.xItemValue = 100;    
    pxList->xListEnd.pxNext =(ListItem_t *) &(pxList->xListEnd);     /*lint !e826 !e740 !e9087 The mini list structure is used as the list end to save RAM.  This is checked and valid. */
    pxList->xListEnd.pxPrevious = (ListItem_t *) &(pxList->xListEnd); /*lint !e826 !e740 !e9087 The mini list structure is used as the list end to save RAM.  This is checked and valid. */
}

void vListInitialiseItem(ListItem_t * const pxItem )
{
    pxItem->pxContainer = NULL;
}
//列表项(节点)末尾插入函数，将节点插入到链表的尾部  
void vListInsertEnd( List_t * const pxList,ListItem_t * const pxNewListItem )
{
    ListItem_t * const headEnd = pxList->pxIndex;

    pxNewListItem->pxNext = headEnd;
    pxNewListItem->pxPrevious = headEnd->pxPrevious;

    headEnd->pxPrevious->pxNext = pxNewListItem;
    headEnd->pxPrevious = pxNewListItem;
    
    /* 记住该节点所在的链表. */
    pxNewListItem->pxContainer = pxList;
 
    (pxList->uxNumberOfItems)++;
}

void vListInsert( List_t * const pxList,ListItem_t * const pxNewListItem )
{
    ListItem_t * pxIterator;
    const int xValueOfInsertion = pxNewListItem->xItemValue;


    if( xValueOfInsertion == 100 )
    {
        pxIterator = pxList->xListEnd.pxPrevious;
    }
    else
    {
        for( pxIterator = (ListItem_t*)&(pxList->xListEnd); pxIterator->pxNext->xItemValue <= xValueOfInsertion; pxIterator = pxIterator->pxNext )
        {
            
        }
    }
 /* 根据升序排列，将节点插入  在pxIterator后面插入新节点*/   
    pxNewListItem->pxNext = pxIterator->pxNext;
    pxNewListItem->pxNext->pxPrevious = pxNewListItem;
    pxNewListItem->pxPrevious = pxIterator;
    pxIterator->pxNext = pxNewListItem;
     
    /* 记住该节点所在的链表 */
    pxNewListItem->pxContainer = pxList;
 /* 链表节点计数器++ */
    ( pxList->uxNumberOfItems )++;
}
int uxListRemove( ListItem_t * const pxItemToRemove )
{
 /* 获取节点所在的链表 */
    List_t * const pxList = pxItemToRemove->pxContainer;
 
 /* 将指定的节点从链表删除*/
    pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
    pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;
    

    /*调整链表的节点索引指针 */
    if( pxList->pxIndex == pxItemToRemove )
    {
        pxList->pxIndex = pxItemToRemove->pxPrevious;
    }
    else
    {

    }
 /* 初始化该节点所在的链表为空，表示节点还没有插入任何链表 */
    pxItemToRemove->pxContainer = NULL;
 /* 链表节点计数器-- */
    ( pxList->uxNumberOfItems )--;
 /* 返回链表中剩余节点的个数 */
    return pxList->uxNumberOfItems;
}

/* 定义链表根节点 */
struct xLIST List_Test;

/* 定义节点 */
struct xLIST_ITEM List_Item1;
struct xLIST_ITEM List_Item2;
struct xLIST_ITEM List_Item3;

int main(void)
{
    /* 定义链表根节点 */
    struct xLIST List_Test;

    /* 定义节点 */
    struct xLIST_ITEM List_Item1;
    struct xLIST_ITEM List_Item2;
    struct xLIST_ITEM List_Item3;
    
    /* 链表根节点初始化 */
    vListInitialise(&List_Test); 

    /* 节点 1 初始化 */
    vListInitialiseItem(&List_Item1);
    List_Item1.xItemValue = 1;

    /* 节点 2 初始化 */
    vListInitialiseItem(&List_Item2);
    List_Item2.xItemValue = 2;

    /* 节点 3 初始化 */
    vListInitialiseItem(&List_Item3);
    List_Item3.xItemValue = 3;

    /* 将节点插入链表，按照升序排列 */ 
    vListInsert( &List_Test, &List_Item2);
    vListInsert( &List_Test, &List_Item1);
    vListInsert( &List_Test, &List_Item3);
 
 while(1);
}

然后随便找个32的代码，用keil仿真试一试；

仔细看一下这张图

这个其实就是FreeRTOS的链表源码，是不是很简单？

工程下载源码：

链接：https://pan.baidu.com/s/1g34z7l3MSrf12lawF4hKLA?pwd=o8xc 
提取码：o8xc

这个工程是一个普通的裸机例程只是加入了FreeRTOS的链表源码，可以自己动手说一下，深入理解链表，因为要想学好任何一个RTOS，必须掌握的基础知识就是链表和队列。