1# 双向链表 2 3 4## 基本概念 5 6双向链表是指含有往前和往后两个方向的链表，即每个结点中除存放下一个节点指针外，还增加一个指向前一个节点的指针。其头指针head是唯一确定的。从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点，这种数据结构形式使得双向链表在查找时更加方便，特别是大量数据的遍历。由于双向链表具有对称性，能方便地完成各种插入、删除等操作，但需要注意前后方向的操作。 7 8 9## 功能说明 10 11双向链表模块为用户提供下面几种功能，接口详细信息可以查看API参考。 12 13 | | | 14| -------- | -------- | 15| **功能分类** | **接口名** | 16| 初始化链表 | - LOS_ListInit：将指定节点初始化为双向链表节点<br/>- LOS_DL_LIST_HEAD：定义一个节点并初始化为双向链表节点 | 17| 增加节点 | - LOS_ListAdd：将指定节点插入到双向链表头端<br/>- LOS_ListHeadInsert：将指定节点插入到双向链表头端，同LOS_ListAdd<br/>- LOS_ListTailInsert：将指定节点插入到双向链表尾端 | 18| 增加链表 | - LOS_ListAddList：将指定链表的头端插入到双向链表头端<br/>- LOS_ListHeadInsertList：将指定链表的头端插入到双向链表头端<br/>- LOS_ListTailInsertList：将指定链表的尾端插入到双向链表头端 | 19| 删除节点 | - LOS_ListDelete：将指定节点从链表中删除<br/>- LOS_ListDelInit：将指定节点从链表中删除，并使用该节点初始化链表 | 20| 判断双向链表 | - LOS_ListEmpty：判断链表是否为空<br/>- LOS_DL_LIST_IS_END：判断指定链表节点是否为链表尾端<br/>- LOS_DL_LIST_IS_ON_QUEUE：判断链表节点是否在双向链表里 | 21| 获取结构体信息 | - LOS_OFF_SET_OF：获取指定结构体内的成员相对于结构体起始地址的偏移量<br/>- LOS_DL_LIST_ENTRY：获取双向链表中第一个链表节点所在的结构体地址，接口的第一个入参表示的是链表中的头节点，第二个入参是要获取的结构体名称，第三个入参是链表在该结构体中的名称<br/>- LOS_ListPeekHeadType：获取双向链表中第一个链表节点所在的结构体地址，接口的第一个入参表示的是链表中的头节点，第二个入参是要获取的结构体名称，第三个入参是链表在该结构体中的名称。如果链表为空，返回NULL。<br/>- LOS_ListRemoveHeadType：获取双向链表中第一个链表节点所在的结构体地址，并把第一个链表节点从链表中删除。接口的第一个入参表示的是链表中的头节点，第二个入参是要获取的结构体名称，第三个入参是链表在该结构体中的名称。如果链表为空，返回NULL。<br/>- LOS_ListNextType：获取双向链表中指定链表节点的下一个节点所在的结构体地址。接口的第一个入参表示的是链表中的头节点，第二个入参是指定的链表节点，第三个入参是要获取的结构体名称，第四个入参是链表在该结构体中的名称。如果链表节点下一个为链表头结点为空，返回NULL。| 22| 遍历双向链表 | - LOS_DL_LIST_FOR_EACH：遍历双向链表<br/>- LOS_DL_LIST_FOR_EACH_SAFE：遍历双向链表，并存储当前节点的后继节点用于安全校验 | 23| 遍历包含双向链表的结构体 | - LOS_DL_LIST_FOR_EACH_ENTRY：遍历指定双向链表，获取包含该链表节点的结构体地址<br/>- LOS_DL_LIST_FOR_EACH_ENTRY_SAFE：遍历指定双向链表，获取包含该链表节点的结构体地址，并存储包含当前节点的后继节点的结构体地址 | 24 25 26## 开发流程 27 28双向链表的典型开发流程： 29 301. 调用LOS_ListInit/LOS_DL_LIST_HEAD初始双向链表。 31 322. 调用LOS_ListAdd向链表插入节点。 33 343. 调用LOS_ListTailInsert向链表尾部插入节点。 35 364. 调用LOS_ListDelete删除指定节点。 37 385. 调用LOS_ListEmpty判断链表是否为空。 39 406. 调用LOS_ListDelInit删除指定节点并以此节点初始化链表。 41 42 43>  **说明：** 44> - 需要注意节点指针前后方向的操作。 45> 46> - 链表操作接口，为底层接口，不对入参进行判空，需要使用者确保传参合法。 47> 48> - 如果链表节点的内存是动态申请的，删除节点时，要注意释放内存。 49 50 51## 编程实例 52 53 54### 实例描述 55 56本实例实现如下功能： 57 58 591. 初始化双向链表。 60 612. 增加节点。 62 633. 删除节点。 64 654. 测试操作是否成功。 66 67### 编程示例 68 69本演示代码在./kernel/liteos_a/testsuites/kernel/src/osTest.c中编译验证，在TestTaskEntry中调用验证入口函数ListSample 70 71示例代码如下： 72 73``` 74#include "stdio.h" 75#include "los_list.h" 76 77static UINT32 ListSample(VOID) 78{ 79 LOS_DL_LIST listHead = {NULL,NULL}; 80 LOS_DL_LIST listNode1 = {NULL,NULL}; 81 LOS_DL_LIST listNode2 = {NULL,NULL}; 82 83 //首先初始化链表 84 PRINTK("Initial head\n"); 85 LOS_ListInit(&listHead); 86 87 //添加节点1和节点2，并校验他们的相互关系 88 LOS_ListAdd(&listHead, &listNode1); 89 if (listNode1.pstNext == &listHead && listNode1.pstPrev == &listHead) { 90 PRINTK("Add listNode1 success\n"); 91 } 92 93 LOS_ListTailInsert(&listHead, &listNode2); 94 if (listNode2.pstNext == &listHead && listNode2.pstPrev == &listNode1) { 95 PRINTK("Tail insert listNode2 success\n"); 96 } 97 98 //删除两个节点 99 LOS_ListDelete(&listNode1); 100 LOS_ListDelete(&listNode2); 101 102 //确认链表为空 103 if (LOS_ListEmpty(&listHead)) { 104 PRINTK("Delete success\n"); 105 } 106 107 return LOS_OK; 108} 109``` 110 111 112**结果验证** 113 114 115编译运行得到的结果为： 116 117 118 119``` 120Initial head 121Add listNode1 success 122Tail insert listNode2 success 123Delete success 124``` 125
