# 双链表

双链表是在单链表的基础上做出了改进，每个结点含有两个指针，分别指向直接前驱与直接后继。

双向线性管理表数据结构定义：

typedef struct __list_line {
        struct __list_line      *LINE_plistNext;
        struct __list_line      *LINE_plistPrev;
} LW_LIST_LINE;

• LINE_plistNext：线性表前向指针。
• LINE_plistPrev：线性表后向指针。

SylixOS 中，双链表主要有结点查找、插入、删除等链表操作。

# 指向下一个结点

#include <SylixOS.h>
VOID  _list_line_next (PLW_LIST_LINE  *phead);

函数 _list_line_next 原型分析：

• 参数 phead 是双链表结点指针的指针。

调用 _list_line_next 函数可以让双链表表头指向下一个结点，如下图所示。

# 获取下一个结点

#include <SylixOS.h>
PLW_LIST_LINE  _list_line_get_next (PLW_LIST_LINE  pline);

函数 _list_line_get_next 原型分析：

• 此函数返回双链表下一个结点的指针。
• 参数 pline 是双链表结点的指针。

调用 _list_line_get_next 函数可以获取双链表下一个结点的指针，如下图所示。

SylixOS 内核中也有很多地方用到双向线性管理表，比如 gdb 调试，当我们执行单步调试的上一步或下一步时，程序就会对应执行上一条语句或下一条语句，gdb 调试的断点管理就使用到 _list_line_get_next 函数。

# 获取上一个结点

#include <SylixOS.h>
PLW_LIST_LINE  _list_line_get_prev (PLW_LIST_LINE  pline);

函数 _list_line_get_prev 原型分析：

• 此函数返回双链表上一个结点的指针。
• 参数 pline 是双链表结点的指针。

调用 _list_line_get_prev 函数可以获取双链表上一个结点的指针，如下图所示。

SylixOS 内核中 _list_line_get_prev 函数是与 _list_line_get_next 函数相对应的，这里再以 SylixOS 内核中堆内存的回收为例，SylixOS 的堆内存的分配与回收采用“首次适应、立即聚合”的机制，在堆内存回收的“立即聚合”实现中会使用到 _list_line_get_prev 函数来获得堆内存的左分段，将已申请的空间释放回堆，且下一次优先被分配。

# 双链表头部前方向插入结点

#include <SylixOS.h>
VOID  _List_Line_Add_Ahead (PLW_LIST_LINE          plineNew,
                            LW_LIST_LINE_HEADER   *pplineHeader);

函数 _List_Line_Add_Ahead 原型分析：

• 参数 pline New 是双链表中要插入的新结点的指针。
• 参数 pplineHeader 是双链表头结点指针的指针。

调用 _List_Line_Add_Ahead 函数可以向双链表表头前方向插入一个结点，参数 pplineHeader 将指向这个结点，如下图所示。

SylixOS 内核中的线程私有数据的管理就是使用 _List_Line_Add_Ahead 函数将线程私有数据加入线程私有数据链表。

# 双链表头部后方向插入结点

#include <SylixOS.h>
VOID  _List_Line_Add_Tail (PLW_LIST_LINE          plineNew,
                           LW_LIST_LINE_HEADER   *pplineHeader);

函数 _List_Line_Add_Tail 原型分析：

• 参数 pline New 是双链表中要插入的新结点的指针。
• 参数 pplineHeader 是双链表头结点指针的指针。

调用 _List_Line_Add_Tail 函数可以向链表头后方向插入一个结点，参数 pplineHeader 不变，如下图所示。

SylixOS 内核中线程是最小调度单位，不过也存在虚拟进程的概念，每个虚拟进程对应一个进程控制块，在进程控制块的管理中就使用到 _List_Line_Add_Tail 函数将进程控制块加入进程表。

# 双链表指定结点左方向插入结点

#include <SylixOS.h>
VOID  _List_Line_Add_Left (PLW_LIST_LINE  plineNew,
                           PLW_LIST_LINE  plineRight);

函数 _List_Line_Add_Left 原型分析：

• 参数 pline New 是双链表中要插入的新结点的指针。
• 参数 plineRight 是双链表中指定结点的指针。

调用 _List_Line_Add_Left 函数可以把新的结点插入双链表指定结点的左侧，如下图所示。

SylixOS 内核中任务需要延时等待时会被操作系统加入到等待唤醒链表中，将一个需要等待唤醒的任务加入到等待唤醒链表中使用到 _List_Line_Add_Left 函数。

# 双链表指定结点右方向插入结点

#include <SylixOS.h>
VOID  _List_Line_Add_Right (PLW_LIST_LINE  plineNew,
                            PLW_LIST_LINE  plineLeft);

函数 _List_Line_Add_Right 原型分析：

• 参数 pline New 是双链表中要插入的新结点的指针。
• 参数 plineLeft 是双链表中指定结点的指针。

调用 _List_Line_Add_Right 函数可以把新的结点插入双链表指定结点的右侧。如下图所示。

# 双链表删除结点

#include <SylixOS.h>
VOID  _List_Line_Del (PLW_LIST_LINE          plineDel,
                      LW_LIST_LINE_HEADER   *pplineHeader);

函数 _List_Line_Del 原型分析：

• 参数 pline Del 是要删除的双链表中的结点的指针。
• 参数 pplineHeader 是双链表头结点的指针的指针。

调用 _List_Line_Del 函数可以从双链表中删除一个结点。如下图所示。

SylixOS 内核中双向线性管理表的结点回收会使用到 _List_Line_Del 函数。