开源鸿蒙 双向链表

  • 2022-08-09
  • 浏览 (503)

双向链表

基本概念

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

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

功能说明

双向链表模块为用户提供下面几种功能,接口详细信息可以查看API参考。

| | | | ——– | ——– | | 功能分类 | 接口描述 | | 初始化链表 | - LOS_ListInit:将指定双向链表节点初始化为双向链表
- LOS_DL_LIST_HEAD:定义一个双向链表节点并以该节点初始化为双向链表 | | 增加节点 | - LOS_ListAdd:将指定节点插入到双向链表头端
- LOS_ListTailInsert:将指定节点插入到双向链表尾端 | | 删除节点 | - LOS_ListDelete:将指定节点从链表中删除
- LOS_ListDelInit:将指定节点从链表中删除,并使用该节点初始化链表 | | 判断双向链表是否为空 | LOS_ListEmpty:判断链表是否为空 | | 获取结构体信息 | - LOS_DL_LIST_ENTRY:获取包含链表的结构体地址,接口的第一个入参表示的是链表中的某个节点,第二个入参是要获取的结构体名称,第三个入参是链表在该结构体中的名称
- LOS_OFF_SET_OF:获取指定结构体内的成员相对于结构体起始地址的偏移量 | | 遍历双向链表 | - LOS_DL_LIST_FOR_EACH:遍历双向链表
- LOS_DL_LIST_FOR_EACH_SAFE:遍历双向链表,并存储当前节点的后继节点用于安全校验 | | 遍历包含双向链表的结构体 | - LOS_DL_LIST_FOR_EACH_ENTRY:遍历指定双向链表,获取包含该链表节点的结构体地址
- LOS_DL_LIST_FOR_EACH_ENTRY_SAFE:遍历指定双向链表,获取包含该链表节点的结构体地址,并存储包含当前节点的后继节点的结构体地址 |

开发流程

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

  1. 调用LOS_ListInit/LOS_DL_LIST_HEAD初始双向链表。

  2. 调用LOS_ListAdd向链表插入节点。

  3. 调用LOS_ListTailInsert向链表尾部插入节点。

  4. 调用LOS_ListDelete删除指定节点。

  5. 调用LOS_ListEmpty判断链表是否为空。

  6. 调用LOS_ListDelInit删除指定节点并以此节点初始化链表。

icon-note.gif 说明: - 需要注意节点指针前后方向的操作。

  • 链表操作接口,为底层接口,不对入参进行判空,需要使用者确保传参合法。

  • 如果链表节点的内存是动态申请的,删除节点时,要注意释放内存。

编程实例

实例描述

本实例实现如下功能:

  1. 初始化双向链表。

  2. 增加节点。

  3. 删除节点。

  4. 测试操作是否成功。

示例代码

示例代码如下:

#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};

    //首先初始化链表
    printf("Initial head\n");
    LOS_ListInit(&listHead);

    //添加节点1和节点2,并校验他们的相互关系
    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");
    }

    //删除两个节点
    LOS_ListDelete(&listNode1);
    LOS_ListDelete(&listNode2);

    //确认链表为空
    if (LOS_ListEmpty(&listHead)) {
        printf("Delete success\n");
    }

    return LOS_OK;
}

结果验证

编译运行得到的结果为:

Initial head 
Add listNode1 success 
Tail insert listNode2 success
Delete success 

你可能感兴趣的文章

开源鸿蒙 kernel

开源鸿蒙 时间管理

开源鸿蒙 附录

开源鸿蒙 内核编码规范

开源鸿蒙 基本数据结构

开源鸿蒙 CMSIS支持

开源鸿蒙 POSIX支持

开源鸿蒙 标准库支持

开源鸿蒙 中断管理

开源鸿蒙 事件

0  赞