◆博主名称：少司府

欢迎来到少司府的博客☆*: .｡. o(≧▽≦)o .｡.:*☆

⭐数据结构系列个人专栏：

初阶数据结构_少司府的博客-CSDN博客

⭐编程基础训练系列个人专栏：

编程基础50题_少司府的博客-CSDN博客

⭐天行健，君子以自强不息

目录

​编辑

一、链表的分类

二、双向链表的结构

1、双向链表的简化图

2、双向链表的结构

三、双向链表的实现

1、.h文件中链表功能函数的声明

2、.c文件中函数功能的实现

---

一、链表的分类

        根据链表的特性（带头还是不带头、单向还是双向、循环还是不循环）可以把链表分为8类。

        如图：

之前我们讲的单链表实际上是不带头单向不循环链表，此处的带头指的是是否具有哨兵位。

哨兵位是为了避免处理空链表的情况而设置的，它本身不存储任何有效的数据。

其next指针指向第一个节点，prev指针指向最后一个节点。

本文主要讲的是带头双向循环链表（简称双向链表）的定义与实现。

二、双向链表的结构

        1、双向链表的简化图

        

        如图，在单链表中，头节点指针phead在一开始需要置为NULL，而双链表的哨兵位却不需要这样操作。下文会给出解释。

        2、双向链表的结构

        如图：

双向链表的结构一般是由一个数据位和两个指针构成。

其中一个指针next指向下一个节点，另一个指针prev指向前一个节点，实现节点之间的连接。

老生常谈，利用typedef重命名数据类型以及节点名字。

        

三、双向链表的实现

        1、.h文件中链表功能函数的声明

        在了解了顺序表、单链表之后，我们大概清楚了这一类表都有哪些功能。

        无非就是：“增删查找”这四个字。

这里声明了头部、尾部的插入删除以及指定位置的插入删除。

当然不要忘了初始化、打印函数的声明：

有了初始化自然也得有销毁：

以及查找函数的声明：

2、.c文件中函数功能的实现

        下面开始实现函数的功能：

        在初始化之前，我们需要申请一个节点才能初始化。每次插入数据都要申请一个节点，干脆将申请节点的功能封装成一个函数，方便调用。

        

如图，malloc申请空间，perror判断是否申请成功。

我们需要将申请到的节点的next指针和perv指针都指向它自己，防止野指针的出现。

返回值为申请到的节点的地址。

        申请节点的功能实现后就可以实现初始化的功能：

如图，创建一个哨兵位，哨兵位传入一个无效的值（假设-1为无效的值）。

        接下来实现打印函数：

如图，定义一个pcur指针指向头节点的下一个节点，遍历链表，如果pcur不为头节点（哨兵位），则打印该节点的数据位，遇到头节点就退出并打印换行。

        尾插功能的实现：

如图，先assert断言，不能传入空指针。

尾插申请一个节点，传入数据x。

先对新节点进行处理，新节点的prev指针指向前一个节点，next指针指向头节点。

再对原本最后一个节点和头节点处理，原本最后一个节点的next指针指向newnode，头节点的prev指针也指向newnode。

        测试尾插功能：

可以看到功能是成功实现的。

        下面是头插功能的实现：

头插实现的基本思路和尾插一样，先是assert断言，再实现头插功能。

一样是先对新节点newnode进行处理，newnode的next指针指向原本头节点（哨兵位）的下一个节点，newnode的prev指针指向头节点。

再对头节点和第一个有效节点进行处理，第一个有效节点的prev指针指向新节点newnode，头节点的next指针也指向新节点。

        测试：

样例通过。

        尾删函数的实现：

在尾删之前要先保证链表的有效性，且链表不能为空链表。严格来讲哨兵位是不能算在链表内的，只有哨兵位的话是不能直接进行删除的。

这里定义一个del指针指向尾节点。

让尾节点的前一个节点的next指针指向头节点，头节点的prev指针指向尾节点的前一个节点。

之后再free释放尾节点，并将尾节点置为空。

        头删函数的实现：

思路和尾删一样，头删的前提是链表有效且不为空。

定义del指针指向要删除的节点。

第一个有效节点的下一个节点的prev指针指向哨兵位，头节点的next指针指向第一个有效节点的下一个节点。

free释放并将del置为空。

        测试尾删和头删功能：

如图，当链表中数据都删完了之后（不包括哨兵位），只打印换行，因此有两个换行。

测试样例通过。

        查找函数的实现：

如图，查找的核心思想无非就一个：遍历。

传入链表的头节点以及要查找的数据。

遍历链表，找到了就返回该数据所在节点的地址，没找到就返回空指针NULL。

        测试：

如图，样例测试查找数据3，找到了，成功返回并打印。

        指定位置pos之后插入数据的功能的实现：

如图，传入pos位置的指针以及要插入的数据x。

断言，pos指针不能为空。

申请节点，将x放入新节点中。

一样是先对新节点newnode处理，newnode的next指针指向pos位置的下一个节点，newnode的prev指针指向pos节点。

再令pos下一个节点的prev指向newnode，pos的next指针指向新节点newnode。

        测试：

成功在数据3的位置之后插入66。

        删除指定位置pos的节点：

断言，pos不能为空。

让pos前一个节点的next指向pos的后一个节点，让pos后一个节点的prev指针指向pos的前一个节点，实现前后节点的连接。

连接完成后free释放pos节点并将它置为空。

        测试：

测试通过，成功删除数据3。

        销毁功能的实现：

如图，传入头节点（哨兵位）的地址，断言，头节点不能为空。

定义一个指针pcur指向第一个有效节点。

遍历，先定义一个next指针将pcur下一个节点保存，free释放pcur，并将next赋给pcur，当pcur指向头节点的时候跳出循环。

free释放头节点并将其置为空。

以上，就是双向链表的功能及实现。