1# Doubly Linked List<a name="EN-US_TOPIC_0000001078588390"></a> 2 3- [Basic Concepts](#section1990715203418) 4- [Available APIs](#section848334511411) 5- [How to Develop](#section01781261552) 6- [Development Example](#section67569495514) 7 - [Example Description](#section48761994551) 8 - [Sample Code](#section1280202685519) 9 - [Verification](#section5811249105512) 10 11 12## Basic Concepts<a name="section1990715203418"></a> 13 14A doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains a pointer to the previous node and a pointer to the next node in the sequence of nodes. The pointer head is unique. 15 16A doubly linked list allows access from a list node to its next node and also the previous node on the list. This data structure facilitates data search, especially traversal of a large amount of data. The symmetry of the doubly linked list also makes operations, such as insertion and deletion, easy. However, pay attention to the pointer direction when performing operations. 17 18## Available APIs<a name="section848334511411"></a> 19 20The doubly linked list module provides the following APIs. For more details about the APIs, see the API reference. 21 22<a name="table9827162254713"></a> 23<table><tbody><tr id="row2089515228470"><td class="cellrowborder" valign="top" width="8.14%"><p id="p4895182214473"><a name="p4895182214473"></a><a name="p4895182214473"></a>Category</p> 24</td> 25<td class="cellrowborder" valign="top" width="32.09%"><p id="p58951922124713"><a name="p58951922124713"></a><a name="p58951922124713"></a>API</p> 26</td> 27<td class="cellrowborder" valign="top" width="59.77%"><p id="p5895122134719"><a name="p5895122134719"></a><a name="p5895122134719"></a>Description</p> 28</td> 29</tr> 30<tr id="row20895152284710"><td class="cellrowborder" rowspan="2" valign="top" width="8.14%"><p id="p18951922144714"><a name="p18951922144714"></a><a name="p18951922144714"></a>Initializing a linked list</p> 31</td> 32<td class="cellrowborder" valign="top" width="32.09%"><p id="p789516220474"><a name="p789516220474"></a><a name="p789516220474"></a><span>LOS_ListInit</span></p> 33</td> 34<td class="cellrowborder" valign="top" width="59.77%"><p id="p38951422144710"><a name="p38951422144710"></a><a name="p38951422144710"></a>Initializes a specified doubly linked list node as a doubly linked list.</p> 35</td> 36</tr> 37<tr id="row289552216475"><td class="cellrowborder" valign="top"><p id="p11895222194718"><a name="p11895222194718"></a><a name="p11895222194718"></a><span>LOS_DL_LIST_HEAD</span></p> 38</td> 39<td class="cellrowborder" valign="top"><p id="p3895222184710"><a name="p3895222184710"></a><a name="p3895222184710"></a>Defines a doubly linked list node and initializes the node as a doubly linked list.</p> 40</td> 41</tr> 42<tr id="row1689522210476"><td class="cellrowborder" rowspan="2" valign="top" width="8.14%"><p id="p12896132294720"><a name="p12896132294720"></a><a name="p12896132294720"></a>Adding a node</p> 43</td> 44<td class="cellrowborder" valign="top" width="32.09%"><p id="p789611221477"><a name="p789611221477"></a><a name="p789611221477"></a><span>LOS_ListAdd</span></p> 45</td> 46<td class="cellrowborder" valign="top" width="59.77%"><p id="p9896122134715"><a name="p9896122134715"></a><a name="p9896122134715"></a>Inserts the specified node to the head of a doubly linked list.</p> 47</td> 48</tr> 49<tr id="row188961225475"><td class="cellrowborder" valign="top"><p id="p18961122154718"><a name="p18961122154718"></a><a name="p18961122154718"></a><span>LOS_ListTailInsert</span></p> 50</td> 51<td class="cellrowborder" valign="top"><p id="p188961322144712"><a name="p188961322144712"></a><a name="p188961322144712"></a>Inserts the specified node to the end of a doubly linked list.</p> 52</td> 53</tr> 54<tr id="row5896112264710"><td class="cellrowborder" rowspan="2" valign="top" width="8.14%"><p id="p28961122174717"><a name="p28961122174717"></a><a name="p28961122174717"></a>Deleting a node</p> 55</td> 56<td class="cellrowborder" valign="top" width="32.09%"><p id="p28961422154710"><a name="p28961422154710"></a><a name="p28961422154710"></a><span>LOS_ListDelete</span></p> 57</td> 58<td class="cellrowborder" valign="top" width="59.77%"><p id="p289610224473"><a name="p289610224473"></a><a name="p289610224473"></a>Deletes the specified node from a doubly linked list.</p> 59</td> 60</tr> 61<tr id="row3896522124711"><td class="cellrowborder" valign="top"><p id="p0896152213471"><a name="p0896152213471"></a><a name="p0896152213471"></a><span>LOS_ListDelInit</span></p> 62</td> 63<td class="cellrowborder" valign="top"><p id="p48965226475"><a name="p48965226475"></a><a name="p48965226475"></a>Deletes the specified node from the linked list and uses the node to initialize the linked list.</p> 64</td> 65</tr> 66<tr id="row1689602294714"><td class="cellrowborder" valign="top" width="8.14%"><p id="p18961222164716"><a name="p18961222164716"></a><a name="p18961222164716"></a>Checking whether a doubly linked list is empty</p> 67</td> 68<td class="cellrowborder" valign="top" width="32.09%"><p id="p78961522184715"><a name="p78961522184715"></a><a name="p78961522184715"></a><span>LOS_ListEmpty</span></p> 69</td> 70<td class="cellrowborder" valign="top" width="59.77%"><p id="p16896172254720"><a name="p16896172254720"></a><a name="p16896172254720"></a>Checks whether a linked list is empty.</p> 71</td> 72</tr> 73<tr id="row128977221474"><td class="cellrowborder" rowspan="2" valign="top" width="8.14%"><p id="p138971322174717"><a name="p138971322174717"></a><a name="p138971322174717"></a>Obtaining structure information</p> 74</td> 75<td class="cellrowborder" valign="top" width="32.09%"><p id="p138971922194712"><a name="p138971922194712"></a><a name="p138971922194712"></a><span>LOS_DL_LIST_ENTRY</span></p> 76</td> 77<td class="cellrowborder" valign="top" width="59.77%"><p id="p08971022144720"><a name="p08971022144720"></a><a name="p08971022144720"></a>Obtains the address of the structure that contains the linked list. The first input parameter of the API indicates a node in the list, the second input parameter indicates the name of the structure to be obtained, and the third input parameter indicates the name of the linked list in the structure.</p> 78</td> 79</tr> 80<tr id="row17897102264718"><td class="cellrowborder" valign="top"><p id="p1889792218473"><a name="p1889792218473"></a><a name="p1889792218473"></a><span>LOS_OFF_SET_OF</span></p> 81</td> 82<td class="cellrowborder" valign="top"><p id="p1897822194713"><a name="p1897822194713"></a><a name="p1897822194713"></a>Obtains the offset of a member in a specified structure relative to the start address of the structure.</p> 83</td> 84</tr> 85<tr id="row4897192254715"><td class="cellrowborder" rowspan="2" valign="top" width="8.14%"><p id="p3897922164714"><a name="p3897922164714"></a><a name="p3897922164714"></a>Traversing a doubly linked list</p> 86</td> 87<td class="cellrowborder" valign="top" width="32.09%"><p id="p58971222194713"><a name="p58971222194713"></a><a name="p58971222194713"></a><span>LOS_DL_LIST_FOR_EACH</span></p> 88</td> 89<td class="cellrowborder" valign="top" width="59.77%"><p id="p28971222194714"><a name="p28971222194714"></a><a name="p28971222194714"></a>Traverses a doubly linked list.</p> 90</td> 91</tr> 92<tr id="row589792254710"><td class="cellrowborder" valign="top"><p id="p689792264718"><a name="p689792264718"></a><a name="p689792264718"></a><span>LOS_DL_LIST_FOR_EACH_SAFE</span></p> 93</td> 94<td class="cellrowborder" valign="top"><p id="p148975222479"><a name="p148975222479"></a><a name="p148975222479"></a>Traverses a doubly linked list, and stores the next node of the current node for security verification.</p> 95</td> 96</tr> 97<tr id="row208971622174718"><td class="cellrowborder" rowspan="2" valign="top" width="8.14%"><p id="p168977224474"><a name="p168977224474"></a><a name="p168977224474"></a>Traversing the structure that contains the doubly linked list</p> 98</td> 99<td class="cellrowborder" valign="top" width="32.09%"><p id="p1489752216479"><a name="p1489752216479"></a><a name="p1489752216479"></a><span>LOS_DL_LIST_FOR_EACH_ENTRY</span></p> 100</td> 101<td class="cellrowborder" valign="top" width="59.77%"><p id="p10897522194717"><a name="p10897522194717"></a><a name="p10897522194717"></a>Traverses the specified doubly linked list and obtains the address of the structure that contains the linked list node.</p> 102</td> 103</tr> 104<tr id="row10897622104713"><td class="cellrowborder" valign="top"><p id="p2897112215478"><a name="p2897112215478"></a><a name="p2897112215478"></a><span>LOS_DL_LIST_FOR_EACH_ENTRY_SAFE</span></p> 105</td> 106<td class="cellrowborder" valign="top"><p id="p13898102220475"><a name="p13898102220475"></a><a name="p13898102220475"></a>Traverses the specified doubly linked list, obtains the structure address of the node that contains the linked list, and stores the structure address that contains the next node of the current node.</p> 107</td> 108</tr> 109</tbody> 110</table> 111 112## How to Develop<a name="section01781261552"></a> 113 114The typical development process of the doubly linked list is as follows: 115 1161. Call **LOS\_ListInit/LOS\_DL\_LIST\_HEAD** to initialize a doubly linked list. 1172. Call **LOS\_ListAdd** to insert a node to the list. 1183. Call **LOS\_ListTailInsert** to insert a node to the end of the list. 1194. Call **LOS\_ListDelete** to delete the specified node. 1205. Call **LOS\_ListEmpty** to check whether a linked list is empty. 1216. Call **LOS\_ListDelInit** to delete a specified node, and initialize the linked list based on this node. 122 123> **NOTE:** 124>- Pay attention to the operations of the front and back pointer of the node. 125>- The linked list operation APIs are underlying APIs and do not check whether the input parameters are empty. You must ensure that the input parameters are valid. 126>- If the memory of a linked list node is dynamically requested, release the memory after deleting the node. 127 128## Development Example<a name="section67569495514"></a> 129 130### Example Description<a name="section48761994551"></a> 131 132This example implements the following: 133 1341. Initialize a doubly linked list. 1352. Add nodes. 1363. Delete a node. 1374. Check whether the operation is performed successfully. 138 139### Sample Code<a name="section1280202685519"></a> 140 141The sample code is as follows: 142 143``` 144#include "stdio.h" 145#include "los_list.h" 146 147static UINT32 ListSample(VOID) 148{ 149 LOS_DL_LIST listHead = {NULL,NULL}; 150 LOS_DL_LIST listNode1 = {NULL,NULL}; 151 LOS_DL_LIST listNode2 = {NULL,NULL}; 152 153 // Initialize the linked list. 154 printf("Initial head\n"); 155 LOS_ListInit(&listHead); 156 157 // Add node 1 and node 2 and verify their relationship. 158 LOS_ListAdd(&listHead, &listNode1); 159 if (listNode1.pstNext == &listHead && listNode1.pstPrev == &listHead) { 160 printf("Add listNode1 success\n"); 161 } 162 163 LOS_ListTailInsert(&listHead, &listNode2); 164 if (listNode2.pstNext == &listHead && listNode2.pstPrev == &listNode1) { 165 printf("Tail insert listNode2 success\n"); 166 } 167 168 // Delete the two nodes. 169 LOS_ListDelete(&listNode1); 170 LOS_ListDelete(&listNode2); 171 172 // Check that the linked list is empty. 173 if (LOS_ListEmpty(&listHead)) { 174 printf("Delete success\n"); 175 } 176 177 return LOS_OK; 178} 179``` 180 181### Verification<a name="section5811249105512"></a> 182 183The development is successful if the return result is as follows: 184 185``` 186Initial head 187Add listNode1 success 188Tail insert listNode2 success 189Delete success 190``` 191 192
