harmony(鸿蒙)Doubly Linked List

2022-08-09
浏览 (817)

Doubly Linked List

Basic Concepts

A 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.

A 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.

Available APIs

The doubly linked list module provides the following APIs. For more details about the APIs, see the API reference.

Function	API	Description
Initializing a linked list	LOS_ListInit	Initializes a specified doubly linked list node as a doubly linked list.
Initializing a linked list	LOS_DL_LIST_HEAD	Defines a doubly linked list node and initializes the node as a doubly linked list.
Adding a node	LOS_ListAdd	Inserts the specified node to the head of a doubly linked list.
Adding a node	LOS_ListTailInsert	Inserts the specified node to the end of a doubly linked list.
Deleting a node	LOS_ListDelete	Deletes the specified node from a doubly linked list.
Deleting a node	LOS_ListDelInit	Deletes the specified node from the linked list and uses the node to initialize the linked list.
Checking whether a doubly linked list is empty	LOS_ListEmpty	Checks whether a linked list is empty.
Obtaining structure information	LOS_DL_LIST_ENTRY	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.
Obtaining structure information	LOS_OFF_SET_OF	Obtains the offset of a member in a specified structure relative to the start address of the structure.
Traversing a doubly linked list	LOS_DL_LIST_FOR_EACH	Traverses a doubly linked list.
Traversing a doubly linked list	LOS_DL_LIST_FOR_EACH_SAFE	Traverses a doubly linked list, and stores the next node of the current node for security verification.
Traversing the structure that contains the doubly linked list	LOS_DL_LIST_FOR_EACH_ENTRY	Traverses the specified doubly linked list and obtains the address of the structure that contains the linked list node.
	LOS_DL_LIST_FOR_EACH_ENTRY_SAFE	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.

How to Develop

The typical development process of the doubly linked list is as follows:

Call LOS_ListInit/LOS_DL_LIST_HEAD to initialize a doubly linked list.
Call LOS_ListAdd to insert a node to the list.
Call LOS_ListTailInsert to insert a node to the end of the list.
Call LOS_ListDelete to delete the specified node.
Call LOS_ListEmpty to check whether a linked list is empty.
Call LOS_ListDelInit to delete a specified node, and initialize the linked list based on this node.

NOTE: - Pay attention to the operations of the front and back pointer of the node. - 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. - If the memory of a linked list node is dynamically requested, release the memory after deleting the node.

Development Example

Example Description

This example implements the following:

Initialize a doubly linked list.
Add nodes.
Delete a node.
Check whether the operation is performed successfully.

Sample Code

The sample code is as follows:

#include "stdio.h"
#include "los_list.h"

static UINT32 ListSample(VOID)
{
    LOS_DL_LIST listHead = {NULL,NULL};
    LOS_DL_LIST listNode1 = {NULL,NULL};
    LOS_DL_LIST listNode2 = {NULL,NULL};

    // Initialize the linked list.
    printf("Initial head\n");
    LOS_ListInit(&listHead);

    // Add node 1 and node 2 and verify their relationship.
    LOS_ListAdd(&listHead, &listNode1);
    if (listNode1.pstNext == &listHead && listNode1.pstPrev == &listHead) {
        printf("Add listNode1 success\n");
    }

    LOS_ListTailInsert(&listHead, &listNode2);
    if (listNode2.pstNext == &listHead && listNode2.pstPrev == &listNode1) {
        printf("Tail insert listNode2 success\n");
    }

    // Delete the two nodes.
    LOS_ListDelete(&listNode1);
    LOS_ListDelete(&listNode2);

    // Check that the linked list is empty.
    if (LOS_ListEmpty(&listHead)) {
        printf("Delete success\n");
    }

    return LOS_OK;
}

Verification

The development is successful if the return result is as follows:

Initial head 
Add listNode1 success 
Tail insert listNode2 success
Delete success

你可能感兴趣的鸿蒙文章

harmony(鸿蒙)Kernel

harmony(鸿蒙)Time Management

harmony(鸿蒙)Kernel Coding Specification

harmony(鸿蒙)Standard Libraries

harmony(鸿蒙)Interrupt Management

harmony(鸿蒙)Memory Management

0 赞

所属分类： 后端技术
本文标签：
版权声明： 原创文章如转载，请注明本文链接: https://m.seaxiang.com/blog/027d6842232f410187a2f09aabbae974