【数据结构】从零开始逐步实现带哨兵位循环双向链表 | 学会用 “思路草图“ 将思路转变成代码

前言：

本章节将继续讲解链表，在上一章节中我们学习了单链表，本章将对其他的链表进行简要介绍，旨在让读者理解单链表和双链表各自存在的意义。将着重讲解带哨兵位双向循环链表，对常用的接口函数进行逐个讲解，本章开始引入可以将思路轻松转换成代码的 "思路草图" 方法。站在初学者的角度上进行讲解和分析。通过本章的学习，还能够帮助大家理解解 "代码复用" 的意义。

一、链表的分类

0x01 链表的分类

① 单向或者双向

② 带头或者不带头

③ 循环或者非循环

0x02 常用的链表

根据上面的分类我们可以细分出8种不同类型的链表，这么多链表我们一个个讲解这并没有意义。我们实际中最常用的链表是 "无头单向非循环链表" 和 "带头双向循环链表" ，至于 "无头单项非循环链表" 我们在上一章已经讲述过了，我们下面将讲解 "带头双向循环列表" ！

? 解读：

① 无头单向非循环链表：结构简单，一般不会多带带用来存储数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等。此外，在笔试中单链表的出现频率较多。

② 带头双向循环链表：结构最复杂，但是实现反而简单。一般用来多带带存储数据，实际中使用的链表数据结构都是带头双向链表。另外，这个结构虽然结构复杂，但是使用代码实现后会发现结构会带来很多优势。双向链表严格来说只需要快速的实现两个接口，insert 和 earse 头尾的插入和删除就可以搞定了，这就是结构的优势！

二、双链表的定义

0x00 定义双链表

typedef int DLNodeDataType;       // DLNodeDataType == inttypedef struct DoubleListNode {    DLNodeDataType data;          // 用来存放结点的数据    struct DoubleListNode* next;  // 指向后继节点的指针    struct DoubleListNode* prev;  // 指向前驱节点的指针} DLNode;  // 重命名为DLNode

? 解读：和之前一样，为了方便后续使用我们将类型 typedef 一下。首先创建结构体，因为双链表，所以我们将它取为 DoubleListNode。为了方便后续地使用，我们再把这个结构体重命名成 DLNode（非常合理的简写，DoubleListNode）。
 

0x01 接口函数

? 这是需要实现几个接口函数：

DLNode* DListInit();// DLNode* CreateNewNode(DLNodeDataType x);void DListPrint(DLNode* pHead);void DListPushBack(DLNode* pHead, DLNodeDataType x);void DListPushFront(DLNode* pHead, DLNodeDataType x);void DListPopBack(DLNode* pHead);void DListPopFront(DLNode* pHead);DLNode* DListFind(DLNode* pHead, DLNodeDataType x);void DListInsert(DLNode* pos, DLNodeDataType x);void DListEarse(DLNode* pos);

三、详解接口函数的实现

0x00 初始化双链表（DListInit）

我们之前在学习无头非循环单链表时，我们使用的是二级指针的方法来接收参数的。本节我们将采用传递返回值的方法来完成。

? DList.h

#pragma once#include #include #include typedef int DLNodeDataType;       // DLNodeDataType == inttypedef struct DoubleListNode {    DLNodeDataType data;          // 用来存放结点的数据    struct DoubleListNode* next;  // 指向后继节点的指针    struct DoubleListNode* prev;  // 指向前驱节点的指针} DLNode;  // 重命名为DLNode       DLNode* DListInit();

? 解读：既然要初始化带头的链表，就需要动态内存开辟，所以我们要引入 #include  这个头文件。我们既然要采用返回值的方法，我们就需要把函数类型设定为 DLNode* 。

? DList.c

DLNode* DListInit() {    //哨兵位头节点    DLNode* pHead = (DLNode*)malloc(sizeof(DLNode));    pHead->next = pHead;    pHead->prev = pHead;    return pHead;}

? 解读：这里我们使用 malloc 函数开辟一块空间作为 "哨兵位" pHead ，最后将其进行一个初始化。最后再将 pHead 作为结果返回回去，外面就可以接收到了。这就是返回值的方法，当然这里也可以采用二级指针的方法来完成。

0x01 双向链表打印（DListPrint）

? DList.h

void DListPrint(DLNode* pHead);

? 解读：用结构体指针 pHead 接收， 这里的 pHead 表示哨兵位。

? DList.c

void DListPrint(DLNode* pHead) {    assert(pHead != NULL); //防止pHead为空        DLNode* cur = pHead->next; //因为pHead存的不是有效数据，所以要从pHead的下一个节点开始    while(cur != pHead) {        printf("%d ", cur->data); //打印        cur = cur->next;    }    printf("/n"); //换行}

? 解读：

① 我们要防止 pHead 为空，暴力解决方法就是用 assert 断言下即可。

② 创建遍历指针 cur，因为 pHead 是哨兵位所以存的不是有效数据，我们想要遍历链表就需要从 pHead->next 开始（即第一个有效数据节点），当 cur 等于 pHead 就相当于全部走了一遍了，这时就结束。

0x02 创建新节点（CreateNewList）

⚡ 创建新节点要经常用，为了方便复用，根据经验我们先把 CreateNewNode 写好：

DLNode* CreateNewNode(DLNodeDataType x) {    //动态内存开辟一块 DLNode 大小的空间给 new_node    DLNode* new_node = (DLNode*)malloc(sizeof(DLNode));    //检查malloc    if (new_node == NULL) {        printf("malloc failed!/n");        exit(-1);    }    //放置数据    new_node->data = x;    //初始化    new_node->next = NULL;    new_node->prev = NULL;    //返回    return new_node;}

0x02 双向链表尾插（DListPushBack）

? DList.h

void DListPushBack(DLNode* pHead, DLNodeDataType x);

? 解读：因为不用改变 pList，所以不需要使用二级指针。

DLNode* pList = DListInit();

? DList.c

void DListPushBack(DLNode* pHead, DLNodeDataType x) {    assert(pHead != NULL); //防止pHead为空       DLNode* tail = pHead->prev; //创建尾指针    DLNode* new_node = CreateNewNode(x); //创建新节点    //思路草图： pHead                 tail   new_node(尾插目标)    tail->next = new_node;    new_node->prev = tail;    new_node->next = pHead;    pHead->prev = new_node;}

? 解读：

① 首先防止 pHead 为空。

② 因为要实现尾插，我们要找出尾部节点。我们这里并不需要像之前学单链表时需要创建寻尾指针找到尾部节点，直接从 pHead->prev 那里取就可以了。是不是非常的方便？找都不用找了直接 O(1) 解决，真的是不爽不要钱！随后创建新节点，直接调用我们刚才写的  CreateNewNode 接口即可。

③ 实现尾插操作，画出来可以更好地写出代码。在注释里写一个简单地思路草图也是可以的，只要画好他们之间的链接关系，再写代码会变得非常简单：

思路草图： pHead                                tail   new_node(尾插目标) 

然后再根据尾插的思路，我们就可以轻松写出代码了：

将 tail 与 new_node 相互链接起来：

    tail->next = new_node;    new_node->prev = tail;

将 new_node 与 pHead 相互链接起来：

    new_node->next = pHead;    pHead->prev = new_node;

（ "双链表"的尾插就这么写好了，是不是比之前学的 "单链表" 简单多了？）

? 如果你没有看懂草图，可以看下面画的更详细的解析图：

? Test.c

我们来测试一下我们刚才写的几个接口：

#include "DList.h"void TestList1() {    DLNode* pList = DListInit();    DListPushBack(pList, 1);    DListPushBack(pList, 2);    DListPushBack(pList, 3);    DListPushBack(pList, 4);    DListPrint(pList);}int main() {    TestList1();    return 0;}

? 运行结果：

0x03 双向链表头插（DListPushFront）

? DList.h

void DListPushFront(DLNode* pHead, DLNodeDataType x);

? 解读：双向链表头插，即在第一个数据前面，也就是哨兵位和第一个数据之间插入一个数据。

? DList.c

void DListPushFront(DLNode* pHead, DLNodeDataType x) {    assert(pHead != NULL); //防止pHead为空        DLNode* new_node = CreateNewNode(x); //创建新节点    DLNode* pHeadNext = pHead->next; //标出第一个节点    //思路草图： pHead  new_node(头插目标)  pHeadNext    pHead->next = new_node;    new_node->prev = pHead;    new_node->next = pHeadNext;    pHeadNext->prev = new_node;}

? 解读：

① 首先防止 pHead 为空。

② 既然是插入，那就创建新节点。双向链表头插，我们要找到第一个节点，通过 pHead->next 就可以拿到了，我们将它取名为 pHeadNext（表示第一个节点）。在哨兵位和第一个数据之间插入数据，画出草图就是：

思路草图： pHead  new_node(头插目标)  next

根据草图我们开始写代码，将他们互相链接起来即可！

将 pHead 与 new_node 相互链接起来：

    pHead->next = new_node;    new_node->prev = pHead;

将 new_node 与 pHeadNext 相互链接起来：

    new_node->next = pHeadNext;    pHeadNext->prev = new_node;

? Test.c

#include "DList.h"void TestList2() {    DLNode* pList = DListInit();    DListPushFront(pList, 10);    DListPushFront(pList, 20);    DListPushFront(pList, 30);    DListPushFront(pList, 40);    DListPrint(pList);}int main() {    TestList2();    return 0;}

? 运行结果：

0x04 双链表尾删（DListPopBack）

? DList.h

void DListPopBack(DLNode* pHead);

? DList.c

void DListPopBack(DLNode* pHead) {    assert(pHead != NULL); //防止pHead为空    //这里要注意下 防止哨兵位也被干掉的情况 pHead->next == pHead 表示链表为空，不能删除了    assert(pHead->next != pHead);    //思路草图： pHead          tailPrev  tail(待删目标)    DLNode* tail = pHead->prev;    DLNode* tailPrev = tail->prev;    //释放    free(tail);    //链接    tailPrev->next = pHead;    pHead->prev = tailPrev;}

? 解读：

① 首先防止 pHead 为空，这里还要预防下哨兵位被不小心干掉的情况，哨兵位指向自己就说明链表为空，链表为空就不能再继续删除了，断言 pHead->next == pHead 就可以了。

② 因为是尾删，我们要把尾部指针和它的前驱指针标出来。我们来画一下思路草图：

思路草图： pHead          tailPrev  tail(待删目标)

另外，这里使用前驱指针是为了避免 free 掉之后就没法链接了。

我们有了 tailPrev 了，所以我们先 free 掉 tail 也关系，此时 tail 已经被释放掉了，我们做一个类似于 "缝针" 的操作即可：

将 tailPrev 与 pHead 相链接起来即可：

    tailPrev->next = pHead;    pHead->prev = tailPrev;

❓ 可能会有人疑惑为什么老是要把他们标出来，这里我来解释一下为什么。标出来可以让代码看起来更清楚，写完思路草图之后可以更好地写出代码，代码也更加好读，多设定几个变量增加可读性是非常值当的事情！当然你非这么干也行：

pHead->prev->prev->next = pHead;pHead->prev = pHead->prev->prev;free(pHead->prev);这位仁兄干嘛要跟自己过不去呢……乱七八糟的，读起来都费劲！定义一下好处很多，链接顺序随便换都没有问题。

? Test.c

#include "DList.h"void TestList3() {    DLNode* pList = DListInit();    DListPushBack(pList, 1);    DListPushBack(pList, 2);    DListPushBack(pList, 3);    DListPushBack(pList, 4);    DListPrint(pList);    DListPopBack(pList);    DListPrint(pList);}int main() {    TestList3();    return 0;}

? 运行结果：

0x05 双链表头删（DListPopFront）

? DList.h

void DListPopFront(DLNode* pHead);

? DList.c

void DListPopFront(DLNode* pHead) {    assert(pHead != NULL); // 防止pHead为空    assert(pHead->next != pHead); // 防止链表为空    //思路草图：  pHead  pHeadNext(待删目标)  pHeadNextNext    DLNode* pHeadNext = pHead->next;    DLNode* pHeadNextNext = pHeadNext->next;    //链接    pHead->next = pHeadNextNext;    pHeadNextNext->prev = pHead;    //释放    free(pHeadNext);}

? 解读：

① 断言部分老生常谈的事了，这里就不重复了。

② 头删，直接画思路草图：

思路草图：  pHead    pHeadNext(待删目标)    pHeadNextNext

                                         ?                                     ?

                          第一个节点（有效数据）         即第二个节点

③ 链接完之后删除即可。

? Test.c

#include "DList.h"void TestList4() {    DLNode* pList = DListInit();    DListPushBack(pList, 1);    DListPushBack(pList, 2);    DListPushBack(pList, 3);    DListPushBack(pList, 4);    DListPrint(pList);    DListPopFront(pList);    DListPrint(pList);}int main() {    TestList4();    return 0;}

? 运行结果：

0x06 双链表查找（DListFind）

? DList.h

DLNode* DListFind(DLNode* pHead, DLNodeDataType x);

? DList.c

DLNode* DListFind(DLNode* pHead, DLNodeDataType x) {    assert(pHead); //防止pHead为空    DLNode* cur = pHead->next;    while(cur != pHead) {        if (cur->data == x)            return cur;        cur = cur->next;    }    return NULL;}

? 解读：很简单，和打印的思路一样。只需要创建一个 cur 从第一个有效节点（pHead->next）开始遍历链表就可以了。如果 cur->data 和传入的 x，即需要查找的值相同就返回 cur，cur 是带有值和地址的。如果整个链表都走完了还没有找到相同的值，就返回 NULL 。

? Test.c

没什么测的，懒得测了。自己测去吧。 （划掉）

0x07 双链表pos位置之前插入（DListInsert）

? DList.h

void DListInsert(DLNode* pos, DLNodeDataType x);

? 解读：根据性质，这里甚至都不需要哨兵位，我们只需要传入 pos 和待插入的值 x 即可。

? DList.c

void DListInsert(DLNode* pos, DLNodeDataType x) {    assert(pos != NULL); // 防止传入的pos为空    DLNode* new_node = CreateNewNode(x);    DLNode* posPrev = pos->prev; //pos前驱    //思路草图： posPrev  newnode(待插目标)   pos    posPrev->next = new_node;    new_node->prev = posPrev;    new_node->next = pos;    pos->prev = new_node;}

? 解读：

① 防止 pos 传入为空。

② 首先创建新节点。因为是在 pos 位置之前插入，为了方便，我们先标出 pos 的前驱指针 posPrev，随后我们画出草图：

思路草图：posPrev  newnode(待插目标)   pos

将 posPrev 与 new_node 相互链接起来：

    posPrev->next = new_node;    new_node->prev = posPrev;

将 new_node 与 pos 相互链接起来：

    new_node->next = pos;    pos->prev = new_node;

⚡ 此时，DListInsert 就大功告成了！它就是双向链表最核心的两个接口之一，我们可以将这个万能的 "pos位置之前插入" 复用到我们刚才写的尾插和头插那里，即 DListPushBack 和 DListPushFront 中：

// 尾删（NEW）void DListPushBack(DLNode* pHead, DLNodeDataType x) {    assert(pHead != NULL); //防止pHead为空        /*    DLNode* tail = pHead->prev; //创建尾指针    DLNode* new_node = CreateNewNode(x); //创建新节点    //思路草图： pHead                 tail   new_node(尾插目标)    tail->next = new_node;    new_node->prev = tail;    new_node->next = pHead;    pHead->prev = new_node;    */    DListInsert(pHead, x);}

? 解读：传入 pHead 进入 DListInsert 中，可以找到尾部节点，即可完成尾插。

// 头删（NEW）void DListPushFront(DLNode* pHead, DLNodeDataType x) {    assert(pHead != NULL); //防止pHead为空        /*    DLNode* new_node = CreateNewNode(x); //创建新节点    DLNode* pHeadNext = pHead->next; //提出第一个节点    //思路草图： pHead  new_node(头插目标)  First    pHead->next = new_node;    new_node->prev = pHead;    new_node->next = pHeadNext;    pHeadNext->prev = new_node;    */    DListInsert(pHead->next, x);}

? 解读：头插，将 pHead->next 传入 DListInsert 中即可完成头插。

0x08 双链表删除pos位置（DListEarse）

? DList.h

void DListEarse(DLNode* pos);

? DList.c

void DListEarse(DLNode* pos) {    assert(pos != NULL); //防止传入的pos为空    DLNode* posPrev = pos->prev; //标出pos的前驱指针    DLNode* posNext = pos->next; //标出pos的后继指针    //思路草图： posPrev  pos(待删目标)  posNext    posPrev->next = posNext;    posNext->prev = posPrev;    //释放    free(pos);}

? 解读：

① 防止 pos 传入为空。

② 既然要删除 pos 位置的节点，我们先标出 pos 的前驱指针 posPrev 和 pos 的后继指针 posNext ，随后我们画出草图：

思路草图： posPrev  pos(待删目标)  posNext

之后我们开始 "缝针" ，将 posPrev 与 posNext 相互链接起来：

posPrev->next = posNext;posNext->prev = posPrev;

最后再将 pos 释放即可。

⚡ 此时，DListEarse 也搞定了！我们可以将这个万能的 "pos位置删除" 复用到之前写的尾删和头删那里，即 DListPopBack 和 DListPopFront 中：

// 尾删（NEW）void DListPopBack(DLNode* pHead) {    assert(pHead != NULL); //防止pHead为空    assert(pHead->next != pHead); //防止链表为空    /*    //思路草图： pHead          tailPrev  tail(待删目标)    DLNode* tail = pHead->prev;    DLNode* tailPrev = tail->prev;    //释放    free(tail);    //链接    tailPrev->next = pHead;    pHead->prev = tailPrev;    */    DListEarse(pHead->prev);}

? 解读：尾删，将 pHead->prev 传入 DListEarse 中即可完成尾删。

// 头删（NEW）void DListPopFront(DLNode* pHead) {    assert(pHead != NULL); // 防止pHead为空    assert(pHead->next != pHead); // 防止链表为空    /*    //思路草图：  pHead  pHeadNext(待删目标)  pHeadNextNext    DLNode* pHeadNext = pHead->next;    DLNode* pHeadNextNext = pHeadNext->next;    //链接    pHead->next = pHeadNextNext;    pHeadNextNext->prev = pHead;    //释放    free(pHeadNext);    */    DListEarse(pHead->next);}

? 解读：头删，将 pHead->next 传入 DListEarse 中即可完成头删。

四、总结

? 所以，双向链表严格来说只需要快速地实现 insert 和 earse 这两个接口就可以搞定了。为什么会这么简单？别问，问就是结构的优势！

如果以后让你快速实现一个双向链表，你把 "pos位置之前插入" 和 "删除pos位置" 这两个接口写好，头尾的插入和删除直接复用就可以搞定了。

五、完整代码

最后附上完整代码（包含测试用地代码）

? DList.h

#pragma once#include #include #include typedef int DLNodeDataType;       // DLNodeDataType == inttypedef struct DoubleListNode {    DLNodeDataType data;          // 用来存放结点的数据    struct DoubleListNode* next;  // 指向后继节点的指针    struct DoubleListNode* prev;  // 指向前驱节点的指针} DLNode;  // 重命名为DLNode       DLNode* DListInit();void DListPrint(DLNode* pHead);void DListPushBack(DLNode* pHead, DLNodeDataType x);void DListPushFront(DLNode* pHead, DLNodeDataType x);void DListPopBack(DLNode* pHead);void DListPopFront(DLNode* pHead);DLNode* DListFind(DLNode* pHead, DLNodeDataType x);void DListInsert(DLNode* pos, DLNodeDataType x);void DListEarse(DLNode* pos);

? DList.c

#include "DList.h"DLNode* DListInit() {    //哨兵位头节点    DLNode* pHead = (DLNode*)malloc(sizeof(DLNode));    pHead->next = pHead;    pHead->prev = pHead;    return pHead;}DLNode* CreateNewNode(DLNodeDataType x) {    //动态内存开辟一块 DLNode 大小的空间给 new_node    DLNode* new_node = (DLNode*)malloc(sizeof(DLNode));    //检查malloc    if (new_node == NULL) {        printf("malloc failed!/n");        exit(-1);    }    //放置数据    new_node->data = x;    //初始化    new_node->next = NULL;    new_node->prev = NULL;    //返回    return new_node;}void DListPrint(DLNode* pHead) {    assert(pHead != NULL); //防止pHead为空        DLNode* cur = pHead->next; //因为pHead存的不是有效数据，所以要从pHead的下一个节点开始    while(cur != pHead) {        printf("%d ", cur->data); //打印        cur = cur->next;    }                                              printf("/n"); //换行}void DListPushBack(DLNode* pHead, DLNodeDataType x) {    assert(pHead != NULL); //防止pHead为空    DListInsert(pHead, x);}void DListPushFront(DLNode* pHead, DLNodeDataType x) {    assert(pHead != NULL); //防止pHead为空    DListInsert(pHead->next, x);}void DListPopBack(DLNode* pHead) {    assert(pHead != NULL); //防止pHead为空    assert(pHead->next != pHead); //防止链表为空    DListEarse(pHead->prev);}void DListPopFront(DLNode* pHead) {    assert(pHead != NULL); // 防止pHead为空    assert(pHead->next != pHead); // 防止链表为空        DListEarse(pHead->next);}DLNode* DListFind(DLNode* pHead, DLNodeDataType x) {    assert(pHead != NULL); //防止pHead为空    DLNode* cur = pHead->next;    while(cur != pHead) {        if (cur->data == x)            return cur;        cur = cur->next;    }    return NULL;}// 在pos位置之前插入void DListInsert(DLNode* pos, DLNodeDataType x) {    assert(pos != NULL); // 防止传入的pos为空    DLNode* new_node = CreateNewNode(x);    DLNode* posPrev = pos->prev; //pos前驱    //思路草图：posPrev  newnode(待插目标)   pos    posPrev->next = new_node;    new_node->prev = posPrev;    new_node->next = pos;    pos->prev = new_node;}// 删除pos位置void DListEarse(DLNode* pos) {    assert(pos != NULL); //防止传入的pos为空    DLNode* posPrev = pos->prev; //标出pos的前驱指针    DLNode* posNext = pos->next; //标出pos的后继指针    //思路草图： posPrev  pos(待删目标)  posNext    posPrev->next = posNext;    posNext->prev = posPrev;    //释放    free(pos);}

? Test.c

#include "DList.h"void TestList1() {    DLNode* pList = DListInit();    DListPushBack(pList, 1);    DListPushBack(pList, 2);    DListPushBack(pList, 3);    DListPushBack(pList, 4);    DListPrint(pList);}void TestList2() {    DLNode* pList = DListInit();    DListPushFront(pList, 10);    DListPushFront(pList, 20);    DListPushFront(pList, 30);    DListPushFront(pList, 40);    DListPrint(pList);}void TestList3() {    DLNode* pList = DListInit();    DListPushBack(pList, 1);    DListPushBack(pList, 2);    DListPushBack(pList, 3);    DListPushBack(pList, 4);    DListPrint(pList);    DListPopBack(pList);    DListPrint(pList);}void TestList4() {    DLNode* pList = DListInit();    DListPushBack(pList, 1);    DListPushBack(pList, 2);    DListPushBack(pList, 3);    DListPushBack(pList, 4);    DListPrint(pList);    DListPopFront(pList);    DListPrint(pList);}int main() {    TestList1();    // TestList2();    // TestList3();    // TestList4();        return 0;}

参考资料：

Microsoft. MSDN(Microsoft Developer Network)[EB/OL]. []. .

百度百科[EB/OL]. []. https://baike.baidu.com/.

声明：本章的 DoubleListNode 源代码参考自C++的STL库！

? 笔者：王亦优

? 更新： 2021.11.15

❌ 勘误： 无

? 声明： 由于作者水平有限，本文有错误和不准确之处在所难免，本人也很想知道这些错误，恳望读者批评指正！