• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1# Doubly Linked List
2
3
4## Basic Concepts
5
6A doubly linked list (DLL) 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. A DLL 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 DLL also makes operations, such as insertion and deletion, easy. However, pay attention to the pointer direction when performing operations.
7
8
9## Available APIs
10
11The table below describes APIs available for the DLL. For more details about the APIs, see the API reference.
12
13| Category                | API Description                                          |
14| ------------------------ | ------------------------------------------------------------ |
15| Initializing a DLL              | - **LOS_ListInit**: initializes a node as a DLL node.<br>- **LOS_DL_LIST_HEAD**: defines a node and initializes it as a DLL node.|
16| Adding a node                | - **LOS_ListAdd**: adds a node to the head of a DLL.<br>- **LOS_ListHeadInsert**: same as **LOS_ListAdd**.<br>- **LOS_ListTailInsert**: inserts a node to the tail of a DLL.|
17| Adding a DLL                | - **LOS_ListAddList**: adds the head of a DLL to the head of this DLL.<br>- **LOS_ListHeadInsertList**: inserts the head of a DLL to the head of this DLL.<br>- **LOS_ListTailInsertList**: inserts the end of a DLL to the head of this DLL.|
18| Deleting a node                | - **LOS_ListDelete**: deletes a node from this DLL.<br>- **LOS_ListDelInit**: deletes a node from this DLL and uses this node to initialize the DLL.|
19| Checking a DLL            | - **LOS_ListEmpty**: checks whether a DLL is empty.<br>- **LOS_DL_LIST_IS_END**: checks whether a node is the tail of the DLL.<br>- **LOS_DL_LIST_IS_ON_QUEUE**: checks whether a node is in the DLL.|
20| Obtaining structure information          | - **LOS_OFF_SET_OF**: obtains the offset of a member in the specified structure relative to the start address of the structure.<br>- **LOS_DL_LIST_ENTRY**: obtains the address of the structure that contains the first node in the DLL. The first input parameter of the API indicates the head 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.<br>- **LOS_ListPeekHeadType**: obtains the address of the structure that contains the first node in the linked list. The first input parameter of the API indicates the head 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. Null will be returned if the DLL is empty.<br>- **LOS_ListRemoveHeadType**: obtains the address of the structure that contains the first node in the linked list, and deletes the first node from the list. The first input parameter of the API indicates the head 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. Null will be returned if the DLL is empty.<br>- **LOS_ListNextType**: obtains the address of the structure that contains the next node of the specified node in the linked list. The first input parameter of the API indicates the head node in the list, the second input parameter indicates the specified node, the third parameter indicates the name of the structure to be obtained, and the fourth input parameter indicates the name of the linked list in the structure. If the next node of the linked list node is the head node and is empty, NULL will be returned.|
21| Traversing a DLL            | - **LOS_DL_LIST_FOR_EACH**: traverses a DLL.<br>- **LOS_DL_LIST_FOR_EACH_SAFE**: traverses the DLL and stores the subsequent nodes of the current node for security verification.|
22| Traversing the structure that contains a DLL| - **LOS_DL_LIST_FOR_EACH_ENTRY**: traverses a DLL and obtains the address of the structure that contains the linked list node.<br>- **LOS_DL_LIST_FOR_EACH_ENTRY_SAFE**: traverses a DLL, obtains the address of the structure that contains the linked list node, and stores the address of the structure that contains the subsequent node of the current node.|
23
24## How to Develop
25
26The typical development process of the DLL is as follows:
27
281. Call **LOS_ListInit** or **LOS_DL_LIST_HEAD** to initialize a DLL.
29
302. Call **LOS_ListAdd** to add a node into the DLL.
31
323. Call **LOS_ListTailInsert** to insert a node into the tail of the DLL.
33
344. Call **LOS_ListDelete** to delete the specified node.
35
365. Call **LOS_ListEmpty** to check whether the DLL is empty.
37
386. Call **LOS_ListDelInit** to delete the specified node and initialize the DLL based on the node.
39
40
41> **NOTE**<br>
42>
43> - Pay attention to the operations before and after the node pointer.
44>
45> - The DLL APIs are underlying interfaces and do not check whether the input parameters are empty. You must ensure that the input parameters are valid.
46>
47> - If the memory of a linked list node is dynamically allocated, release the memory when deleting the node.
48
49
50## Development Example
51
52
53###  Example Description
54
55This example implements the following:
56
57
581. Initialize a DLL.
59
602. Add nodes.
61
623. Delete nodes.
63
644. Check the operation result.
65
66### Sample Code
67
68The sample code can be compiled and verified in **./kernel/liteos_a/testsuites/kernel/src/osTest.c**. The **ListSample** function is called in **TestTaskEntry**.
69
70The sample code is as follows:
71
72```
73#include "stdio.h"
74#include "los_list.h"
75
76static UINT32 ListSample(VOID)
77{
78    LOS_DL_LIST listHead = {NULL,NULL};
79    LOS_DL_LIST listNode1 = {NULL,NULL};
80    LOS_DL_LIST listNode2 = {NULL,NULL};
81
82    // Initialize the DLL.
83    PRINTK("Initial head\n");
84    LOS_ListInit(&listHead);
85
86    // Add node 1 and node 2 and verify their relationship.
87    LOS_ListAdd(&listHead, &listNode1);
88    if (listNode1.pstNext == &listHead && listNode1.pstPrev == &listHead) {
89        PRINTK("Add listNode1 success\n");
90    }
91
92    LOS_ListTailInsert(&listHead, &listNode2);
93    if (listNode2.pstNext == &listHead && listNode2.pstPrev == &listNode1) {
94        PRINTK("Tail insert listNode2 success\n");
95    }
96
97    // Delete the two nodes.
98    LOS_ListDelete(&listNode1);
99    LOS_ListDelete(&listNode2);
100
101    // Check whether the DLL is empty.
102    if (LOS_ListEmpty(&listHead)) {
103        PRINTK("Delete success\n");
104    }
105
106    return LOS_OK;
107}
108```
109
110
111**Verification**
112
113
114The development is successful if the return result is as follows:
115
116
117
118```
119Initial head
120Add listNode1 success
121Tail insert listNode2 success
122Delete success
123```
124