链表-双向非通用链表

目录

前言

• 20201010
• 在阅读 RTOS LiteOS 内核源码时发现该内核使用的链表时 通用链表 ，而 FreeRTOS 内核使用的时 非通用链表 ，所以，有必要发布一下关于链表实现的笔记。
• 以下内容为个人笔记，涉及一些非专业词汇，敬请谅解，谢谢。

链接

• 我的Gitee
• 非通用链表完整C语言源码

参考

• 上面链接
• FreeRTOS 内核源码
• 野火

概念

• 正常表达

  • 链表：
    • 链表为 C 中一种基础的数据结构。
    • 看成环形晾衣架即可。
  • 节点：
    • 节点组成链表

• 自理解概念

  • 链表：圆形的晾衣架
  • 节点：挂钩
    • 包含上一个
    • 下一个
    • 钩子等其它需要的信息
  • 袜子：挂在到 钩子 的东西
    • 包含 被钩子
    • 袜子携带的信息
      

• 通用链表与非通用链表的区别

  • 通用链表节点内容很少一般只有 上一个 和 下一个 。
  • 通用链表节点被放到信息结构体中，通过偏移找到所在的结构体（即是通过偏移找到袜子头）
  • 而非通用链表是在节点中携带信息结构体的指针的（即是节点就携带信息）。
  • 别人通俗理解，读者不必理会本小点
    • 通用链表是把袜子放到晾衣架的圆形圈上，袜子与圆形圈接触部分为袜子接待的节点。（ 信息携带节点 ）
    • 非通用链表是。（ 节点携带信息 ）

笔录草稿

双向链表

• 双向链表理解图

• 原理：链表包括 根节点 和 普通节点

  • 根节点主要管理链表的，一般包括

    • 上一个
    • 下一个
    • 存在多少个等信息
      

  • 普通节点主要用于钩住袜子（即是携带信息）

节点及节点结构体代码

• 普通节点
  • 存放节点信息
  • 挂载东西（挂钩），如挂载袜子等等
    

/*
 * The linked list node
 */
struct LIST_ITEM_LSS_T
{   
    struct LIST_ITEM_LSS_T * pxNext; // 下一个
    struct LIST_ITEM_LSS_T  * pxPrevious; // 上一个
    
    /* 节点属性，（根据个人需求增减以下内容） */
    uint32_t xItemValue; // 记号值，一般用于排序
    void * pvOwner; // 挂钩，即携带的信息
    void * pvContainer; // 归属，即属于哪一个链表
};
typedef struct LIST_ITEM_LSS_T listItem_t;

• root节点（链表点）
  • 存放链表的信息
  • 有一个 mini节点，用于驳接和定位（相当于位置校准点），不挂载如何东西，且简洁为妙
    • mini节点

      mini节点的记号值在双向链表中为最大值，因为最大是尾也是头。

      

/* mini 节点结构体 */
struct LIST_MINI_ITEM_LSS_T
{
    /* 指向，（根据单、双链表删减以下内容） */
    struct node *pxPrevious; // 上一个节点
    struct node *pxNext; // 下一个节点
     /* 节点属性，（根据个人需求增减以下内容） */
    uint32_t xItemValue; // 记号值，在双向链表中为最大值
};
typedef struct LIST_MINI_ITEM_LSS_T ListMiniItem_t;

/* 链表结构体，即根节点 */
struct LIST_LSS_T
{
    /* 节点属性，（根据个人需求增减以下内容） \*/
    uint32_t uxNumberOfItems; // 节点数，统计粘附在本链表上的节点数
    struct LIST_ITEM_LSS_T * pxIndex; // 索引，链表索引，指向链表中的某个节点
    struct LIST_MINI_ITEM_LSS_T xListEnd; // 链表根节点
};
typedef struct LIST_LSS_T List_t;

链表操作的函数代码

链表初始化函数

1. 链表索引指向该链表的 尾节点 （尾节点，即也是头节点）
2. 链表 尾节点 记号值赋值为最大值（ 根节点包含尾节点 ）
3. 初始化尾节点的 上一个 及 下一个 ，分别都指向**尾节点
4. 初始化节点总数为 0。

/**
  * @brief  链表初始化
  * @param 
  * @retval 
  * @author lzm
  */
void listInit(list_t * const list)
{
    /* 索引指向最后：尾就是头 */
    list->pxIndex = (listItem_t *) &(list->xListEnd);
    
    /* 链表最大值 */
    list->xListEnd.xItemValue = lssLIST_MAX_VALUE;
    
    list->xListEnd.pxNext = ( listItem_t * ) &( list->xListEnd );
    list->xListEnd.pxPrevious = ( listItem_t * ) &( list->xListEnd );
    
    list->uxNumberOfItems = (lssLIST_BASE_TYPE)0U;
}

节点初始化函数

1. 初始化节点携带的信息为空

/**
  * @brief  节点初始化
  * @param 
  * @retval 
  * @author lzm
  */
void listItemInit(listItem_t * const item)
{
    item->pvContainer = NULL;
}

节点插入链表尾部函数

注意 ：需要插入的节点以下称为 节点A

1. 获取索引（索引即游标，也就是该链表当前指向的节点）
2. 节点A 的 下一个 指向 索引节点 ，
3. 节点A 的 前一个 指向 索引节点 的 前一个
4. 索引节点前一个 的 下一个 指向 节点A
5. 索引节点 的 前一个 指向 节点A
6. 设置 节点A 归属于哪个链表
7. 链表节点计数值 +1

/**
* @brief  插入链表尾部（*双向链表没有绝对的头尾，此处是以游标为参考物*）
* @param 
* @retval 
* @author lzm
*/
void listInsertEnd( list_t * const pxList, listItem_t * const pxNewListItem )
{
    listItem_t * const pxIndex = pxList->pxIndex;

    pxNewListItem->pxNext = pxIndex;
    pxNewListItem->pxPrevious = pxIndex->pxPrevious;

    pxIndex->pxPrevious->pxNext = pxNewListItem;
    pxIndex->pxPrevious = pxNewListItem;

    /* Remember which list the item is in. */
    pxNewListItem->pvContainer = ( void * ) pxList;

    ( pxList->uxNumberOfItems )++;
}

节点有序插入链表函数

注意 ：需要插入的节点以下称为 节点A

1. 获取新节点记号值

   2.找出需要插入的位置

   1. 如果记号值为链表中最大值（即和 尾节点 的记号值相等），则取出尾节点的前一个节点作为参考节点
   2. 如果记号值 不 为链表中最大值，则从尾节点开始找，直至找到 当前节点 的 下一个节点 的记号值为 大于 节点A 的记号值（即是在链表中找出红框节点B）
      
   3. 插入节点
      1. 节点A （ 节点A 为需要插入的节点）的 下一个 指向 索引节点 ，
      2. 节点A 的 前一个 指向 节点B 的 前一个
      3. 节点B的前一个 的 下一个 指向 节点A
      4. 节点B 的 前一个 指向 节点A
      5. 设置 节点A 归属于哪个链表
      6. 链表节点计数值 +1

/**
* @brief  按记号值值插入
* @param 
* @retval 
* @author lzm
*/
void listInsert( list_t * const pxList, listItem_t * const pxNewListItem )
{
    listItem_t *pxIterator;
    const lssLIST_BASE_TYPE xValueOfInsertion = pxNewListItem->xItemValue; // 获取新节点记号值
    
    /* 按顺序寻找 */
    if( xValueOfInsertion == lssLIST_MAX_VALUE )
    {
          pxIterator = pxList->xListEnd.pxPrevious;
    }
    else
    {
          for( pxIterator = ( listItem_t * ) &( pxList->xListEnd ); pxIterator->pxNext->xItemValue <= xValueOfInsertion; pxIterator = pxIterator->pxNext ) /*lint !e826 !e740 The mini list structure is used as the list end to save RAM.  This is checked and valid. */
          {
                /* There is nothing to do here, just iterating to the wanted insertion position. */
          }
    }

    pxNewListItem->pxNext = pxIterator->pxNext;
    pxNewListItem->pxNext->pxPrevious = pxNewListItem;
    pxNewListItem->pxPrevious = pxIterator;
    pxIterator->pxNext = pxNewListItem;

    /* Remember which list the item is in.  This allows fast removal of the
    item later. */
    pxNewListItem->pvContainer = ( void * ) pxList;

    ( pxList->uxNumberOfItems )++;
}

从链表中删除函数

注意 ：被删除的节点以下称为 节点A

1. 获取链表
2. 节点A下一个节点 的 前一个 指向 节点A的前一个节点
3. 节点A前一个节点 的 下一个 指向 节点A的下一个节点
4. 检查链表索引是否指向了 节点A
   1. 是：索引更新为指向 节点A的前一个节点
   2. 否：跳过
5. 清空 节点A 的链表归属
6. 链表节点计数值 -1
7. 返回链表节点数

/**
* @brief  从链表中删除节点
* @param 
* @retval 
* @author lzm
*/
uint32_t listRemove( listItem_t * const pxItemToRemove )
{
/* The list item knows which list it is in.  Obtain the list from the list
item. */
    list_t * const pxList = ( list_t * ) pxItemToRemove->pvContainer;

    pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
    pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;

    /* Make sure the index is left pointing to a valid item. */
    if( pxList->pxIndex == pxItemToRemove )
    {
          pxList->pxIndex = pxItemToRemove->pxPrevious;
    }

    pxItemToRemove->pvContainer = NULL;
    
    ( pxList->uxNumberOfItems )--;

    return pxList->uxNumberOfItems;
}

源码集合

• 内含
  • 节点及链表结构体
  • 节点初始化函数
  • 链表初始化函数
  • 节点插入函数
  • 删除节点函数
  • 配对挂钩与袜子函数
  • 获取节点信息函数
  • 获取记号值函数
  • 获取第一个节点的节点值函数
  • 获取链表的入口节点函数
  • 获取下一个节点函数
  • 获取链表最后一个节点（尾节点）函数
  • 判断链表是否为空函数
  • 获取链表当前节点总数函数
  • 获取链表索引指向的下一个节点函数
• 跳转到 非通用链表完整C语言源码 即可