4.11 双向链表

概述

基本概念

双向链表是指含有往前和往后两个方向的链表,即每个结点中除存放下一个节点指针外,还增加一个指向其前一个节点的指针。其头指针head是唯一确定的。

从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点,这种数据结构形式使得双向链表在查找时更加方便,特别是大量数据的遍历。由于双向链表具有对称性,能方便地完成各种插入、删除等操作,但需要注意前后方向的操作。

开发指导

功能

Huawei LiteOS系统中的双向链表模块为用户提供下面几个接口。

功能分类

接口名

描述

初始化链表

LOS_ListInit

对链表进行初始化。

增加节点

LOS_ListAdd

将新节点添加到链表中。

在链表尾端插入节点

LOS_ListTailInsert

将节点插入到双向链表尾端。

在链表头端插入节点

LOS_ListHeadInsert

将节点插入到双向链表头端

删除节点

LOS_ListDelete

将指定的节点从链表中删除。

判断双向链表是否为空

LOS_ListEmpty

判断链表是否为空。

删除节点并初始化链表

LOS_ListDelInit

将指定的节点从链表中删除,使用该节点初始化链表。

开发流程

双向链表的典型开发流程:

  1. 调用LOS_ListInit初始双向链表。
  2. 调用LOS_ListAdd向链表中增加节点。
  3. 调用LOS_ListTailInsert向链表尾部插入节点。
  4. 调用LOS_ListDelete删除指定节点。
  5. 调用LOS_ListEmpty判断链表是否为空。
  6. 调用LOS_ListDelInit删除指定节点并以此节点初始化链表。

注意事项

  • 需要注意节点指针前后方向的操作。

编程实例

实例描述

使用双向链表,首先要申请内存,删除节点的时候要注意释放掉内存。

本实例实现如下功能:

  1. 调用函数进行初始化双向链表。
  2. 增加节点。
  3. 删除节点。
  4. 测试操作是否成功。

编程示例

代码实现如下:

  1. #include "stdio.h"
  2. #include "los_list.h"
  3. #ifdef __cplusplus
  4. #if __cplusplus
  5. extern "C" {
  6. #endif /* __cpluscplus */
  7. #endif /* __cpluscplus */
  8. static UINT32 DLlist_sample(VOID)
  9. {
  10. LOS_DL_LIST DLlist = {NULL,NULL};
  11. LOS_DL_LIST DLlistNode01 = {NULL,NULL};
  12. LOS_DL_LIST DLlistNode02 = {NULL,NULL};
  13. LOS_DL_LIST DLlistNode03 = {NULL,NULL};
  14. PRINTK("Initial head\n");
  15. LOS_ListInit(&DLlist);
  16. LOS_ListAdd(&DLlist,&DLlistNode01);
  17. if (DLlistNode01.pstNext == &DLlist && DLlistNode01.pstPrev == &DLlist)
  18. {
  19. PRINTK("Add DLlistNode01 success \n");
  20. }
  21. LOS_ListTailInsert(&DLlist,&DLlistNode02);
  22. if (DLlistNode02.pstNext == &DLlist && DLlistNode02.pstPrev == &DLlistNode01)
  23. {
  24. PRINTK("Tail insert DLlistNode02 success \n");
  25. }
  26. LOS_ListHeadInsert(&DLlistNode02,&DLlistNode03);
  27. if (DLlistNode03.pstNext == &DLlist && DLlistNode03.pstPrev == &DLlistNode02)
  28. {
  29. PRINTK("Head insert DLlistNode03 success \n");
  30. }
  31. LOS_ListDelInit(&DLlistNode03);
  32. LOS_ListDelete(&DLlistNode01);
  33. LOS_ListDelete(&DLlistNode02);
  34. if (LOS_ListEmpty(&DLlist))
  35. {
  36. PRINTK("Delete success \n");
  37. }
  38. return LOS_OK;
  39. }
  40. #ifdef __cplusplus
  41. #if __cplusplus
  42. }
  43. #endif /* __cpluscplus */
  44. #endif /* __cpluscplus */

结果验证

编译运行得到的结果为:

  1. Initial head
  2. Add DLlistNode01 success
  3. Tail insert DLlistNode02 success
  4. Head insert DLlistNode03 success
  5. Delete success