数据结构——双链表详解（超详细）

前言：

小编在之前已经写过单链表的创建了，接下来要开始双链表的讲解了，双链表比单链表要复杂一些，不过确实要比单链表更好进行实现！下面紧跟小编的步伐，开启今天的双链表之旅！

1.概念和结构

1.1.哨兵位

1.2.双链表的结构

2.双向链表的实现

2.1.初始化双链表

2.2.双链表的尾插

2.3.双链表的打印

·2.4.双链表的头插

2.5.双链表的尾删

2.6.双链表的头删

2.7.查找双链表的数据

2.8.在指定位置之后插入数据

2.9. 删除指定结点的数据

3.0.销毁双链表

3.链表的分类

1.单向不带头不循环链表（也就是小编前面写的单链表）：

2.单向带头不循环链表：

编辑 3.单向不带头循环链表：

4.单向带头循环链表：

编辑 5.双向带头循环链表：

编辑

6.双向不带头不循环链表：

7.双向带头不循环链表：

编辑 8.双向不带头循环链表：

4.代码展示

4.1.List.h

4.2.List.c

总结

正文：

1.概念和结构

在前面的博客中小编讲述了单链表，其实单链表的全程叫做，单向不带头不循环链表，这里有很多读者朋友就好奇了，单向和不循环还是比较容易理解的，那么不带头又是什么意思呢，其实这里就牵扯到了一个全新的知识点：哨兵位！

1.1.哨兵位

哨兵位这个名字看起来是很威武的，其实了解它之后就知道它仅仅就是名字威武点，它才是真正意义上的头结点，哨兵位是不存数据的，它的存在仅仅就是为了说明这个链表是带头的，是用来“放哨的”，小编在讲述单链表的时候曾多次提到了头结点这个名字，那个时候头结点是链表第一个结点，这个叫法是不太规范的，不过为了让读者朋友更好的去理解链表的知识，小编于是就直接头结点来代替链表第一个结点了，不过各位读者朋友一定要清楚真正的头结点其实就是哨兵位。

1.2.双链表的结构

首先，双链表是带头的链表，说明它的第一个结点是不存数据的，是哨兵位，双链表也是双向的，说明它的结点不仅仅存放着下个结点的数据，也存放着的前一个结点的数据，看着非常复杂，其实有了这个特点以后，在写双链表代码的时候要比单链表要简单许多，等会各位就清楚小编为什么这么说了，它的最后一个特点是循环，这个小编在之前讲解环形链表习题的时候就牵扯到了一点循环链表，下面小编给上双链表的结构图以便大家在等会写代码的时候可以更好的理解：

小编已经讲述了双链表的概念和结构了，下面就是各位最喜欢的节目：双链表代码的书写，下面跟随小编的脚步，开启我们今天的代码之旅喽~

2.双向链表的实现

在写双链表之前，这里小编还是说一下，我们依旧需要创建两个源文件和一个头文件，头文件是负责声明一下写的函数，一个源文件是负责实现函数功能的，另一个是测试用的，废话不多说开始进入正文：

2.1.初始化双链表

在初始话双链表之前，我们肯定要写双向链表结点的结构体，这个结构体其实就是比单链表多了一个存放上一个结点的地址，其他都是一样的，下面直接上代码：

typedef int LTDataType;
typedef struct List {LTDataType date;struct List* next; //存放下一个结点的地址struct List* prev; //存放上一个函数结点的地址
}LTNode;

对于双链表的初始化，这里可不是简简单单的就是把它的下一个结点为空，上一个结点为空了，双链表是带头的，所以其实这里的初始化操作就是创建一个哨兵位，按理说哨兵位是不存放任何数据的，不过我们也是可以给它赋值的，只不过不用它这个值罢了，这里我们就把哨兵位的数据暂时弄为-1，因为这个链表是循环的，所以我们需要让它的下一个结点和上一个结点统一指向自己，这里就可以形成死循环，小编在下面通过图文来让大家去理解：

此时我们已经完成了尾插的操作，下面开始进行链表常见操作：尾插操作

2.2.双链表的尾插

对于插入操作，肯定需要先设置一个新的结点，不然尾插就没有什么结点可插了，对于新节点的创建，小编在之前单链表也写过，不过双链表与单链表最大的不同就是它的下一个结点和上一个结点都要去指向自己，下面直接上手代码图了（这里由于难度不大小编就不在多赘述了）：

//先创建一个新的结点（对于任何插入操作都得有这个玩意）
LTNode* LTbuynode(LTDataType x)
{LTNode* p1 = (LTNode*)malloc(sizeof(LTNode));assert(p1);p1->date = x;p1->next = p1->prev = p1;
}

接下来就进行插入操作了，小编经过深思熟虑以后，决定搭配着图文进行配套讲解，感觉这样讲起来不费劲，各位理解起来也不算太费劲，下面小编随机弄个图来进行讲解：

先创建好结点，创建好后开始进行尾插操作：

之后我们需要让哨兵位的下一个结点指向新创立的结点newlode，让newlode的上一个结点指向哨兵位，：

之后我们为了达成循环的效果，我们要让哨兵位的上一个结点指向新结点，让新结点的下一个结点的指针指向哨兵位，此时我们就完成了尾插操作，其实这里小编感觉我给的例子不是很好，各位读者朋友最好用用一个比较长的链表来实现，那个更容易理解，这里我先对各位说声抱歉。

下面小编给上尾插操作的代码，通过这个代码各位读者朋友就知道为什么小编推荐用长一点的链表来实现这个尾插操作了：

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);  //首先哨兵位不能是空的LTNode* newnode = LTbuynode(x);phead->prev->next = newnode;newnode->next = phead;newnode->prev = phead->prev;phead->prev = newnode;
}

这个代码值得注意的就是，我们再传参的时候并不是像单链表一样传的二级指针，我们传的是一级指针，因为我们并不会对头结点（哨兵位）做出改变，故不用传地址，这个代码还是比较好理解的，各位读者朋友一定要自己先思考，自己先写一遍代码然后再看小编写的，如果直接复制粘贴的话，写完之后知识也不是你的！小编写这篇文章的目的就是让读者朋友去理解的，也让我自己在复习一遍。

2.3.双链表的打印

双链表的打印其实是蛮容易的，不过写这个函数的目的就是为了测试其他函数写的对不对，对于双链表的打印，它和单链表的打印有些许不同，因为双链表我·是一个带头的，死循环的链表，所以我们需要通过控制循环条件来实现对于双链表的打印：

首先我们需要先设置一个结点来代表哨兵位下一个结点（因为哨兵位理论上是不存数据的），然后我们开始循环打印结点的数据，结束的条件自然就是我们不能让设置的这个指针循环到哨兵位结点，一旦循环到了哨兵位结点，则说明此时已经完成了一轮循环，所以此时我们无须在进行循环，直接结束就好了，由于本小节内容无须图像，所以我们便直接展示代码了：

void LTPrint(LTNode* phead)
{LTNode* pour = phead->next;while (pour != phead){printf("%d->", pour->date);pour = pour->next;}printf("\n");
}

·2.4.双链表的头插

这里一定要注意，双链表的头插可不是把新节点插到哨兵位之前，而是插在哨兵位之后，哨兵位之后的第一个节点才是有实际意义的头一个结点，下面小编用图文的方式来给大家讲述一下头插的原理：

这里我们需要设置一个新节点，对于设置新节点的代码小编在上面已经讲述清楚了，为了让文章更加清楚，小编这里用一个长的链表来进行头插操作：

之后我们让d1的上一个结点不在指向哨兵位，而是指向新节点，让新节点的下一个结点指向d1：

之后我们让新节点的上一个结点指向哨兵位，让哨兵位的下一个结点指向新节点：

此时我们已经完成了头插操作，此时哨兵位的下一个结点就是新节点了，下面小编给出这个操作的代码：

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTbuynode(x);LTNode* next = phead->next;newnode->next = next;next->prev = newnode;phead->next = newnode;newnode->prev = phead;
}

此时我们已经完成了头插尾插操作，下面就要进行删除操作，我们先从头删和尾删操作开始喽，读者朋友们继续加油。

2.5.双链表的尾删

双链表的尾删操作也不难，我们都会插入数据了，尾部删除自然而然也会显得很简单，小编之前就说过双链表的代码要比单链表的代码要简单许多，因为此时我们用不到循环来找尾结点，对于尾结点，我们仅需通过哨兵位的上一个结点便可以找到尾结点，从这点就可以看出双链表的便利，行了，废话不多说，下面进入尾删讲解环节：

我们在尾删之前，一定要判断我们想要删除的链表是否是除了哨兵位结点之外还有别的结点，所以我们需要写一个布尔类型的函数来进行对于链表是否为空来进行判断，下面是代码：

bool Listpanduan(LTNode * phead)   //在使用bool关键字的时候记得先有头文件，这里是判断是否除了哨兵位还有没有别的结点了
{return phead == phead->next;
}

首先我们继续使用上面的链表作为例子：

首先我们想要删除尾部的数据，我们就要改变指针的指向，此时我们需要通过尾结点找到它的上一个结点，此时我们直接用d2来说，我们让d2的下一个指针指向哨兵位，再让哨兵位的上一个结点指向d2：

此时我们便让d2成为了新的尾结点，至于d3，我们直接将它free掉：

我们已经完成了双链表的尾删操作，下面小编直接展示代码：

void LTPopBack(LTNode* phead)
{assert(phead);//先判断是不是只有哨兵位assert(!Listpanduan(phead));LTNode* prev = phead->prev;prev->prev->next = phead;phead->prev = prev->prev;free(prev);prev = NULL;
}

尾删操作已经结束了，下面我们快马加鞭，来进入头删环节！

2.6.双链表的头删

双链表的头删操作类似尾删操作，无非就是把指针的指向来回改变指针指向的问题，不过这里也要记住，头删头删，并不是删掉链表的哨兵位，而是删掉哨兵位的下一个结点，这个结点才是真正意义上的头结点，下面我们来进行头删的讲解：

在进行这个代码之前，因为涉及到了删除，我们还是要判断这个链表是否只含有哨兵位，判断完以后就可以进行正常的代码书写了：

首先，我们还是选取上述使用的链表来进行讲解：

之后我们的任务就是把d2变成头结点，这里我们需要改变指针的指向，我们可以想让哨兵位的下一个结点指向它原本下一个结点的下一个结点，也就是d2，再让d2的上一个指针直接指向哨兵位结点：之后我们直接讲d1结点free掉就可以实现头删操作：

上面就是头删操作的实现图，是不是感觉很easy（悄咪咪的说小编当初学的时候可没这样感觉到，嘿嘿）？下面小编给大家展示下这个代码如何书写：

void LTPopFront(LTNode* phead)
{assert(phead);assert(!Listpanduan(phead));LTNode* next = phead->next;phead->next = next->next;next->prev = phead;free(next);next = NULL;
}

此时的我们已经实现了如何进行头删和尾删操作，下面我们开始进行一些特定位置的查找，插入，删除操作，下面跟随小编的脚步，一起实现这些代码吧！

2.7.查找双链表的数据

这个操作可以类比我们在单链表的时候写过的查找单链表数据来记，这个和我们上文在打印时是一样的操作，我们可以通过循环操作来实现，这个查找小编认为就不需要图文进行解释了，小白在这里用文字进行解释，我们也是同样从哨兵位下一个结点开始进行循环寻找我们想要的数据，如果循环到了我们直接返回这个结点，如果经历完循环以后我们还没有找到，那么我们就直接返回空就好，下面是代码实现图，这个操作还是蛮简单的：

LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pour = phead->next;while (pour != phead){if (pour->date == x)return pour;pour = pour->next;}return NULL;
}

2.8.在指定位置之后插入数据

这个操作类似我们之前的插入函数，也是改变指针指向就好了，下面小编就直接开讲啦：

首先，我们需要先设置一个长点的链表，小编就在这里还是以上面的链表为例子，并且记住一旦涉及到插入函数我们首先需要设置一个新的结点，这里我们指定的结点就拿d2进行举例子：

此时我们需要先保存一下d2的下一个结点d3，然后我们可以让d2这个结点的下一个结点指向新结点，让新结点的下一个结点指向d3：

之后我们再让新结点的上一个结点指向d2，让d3的上一个结点指向新结点，此时我们就完成了指定位置之后插入数据：

此时我们已经完成了对于此函数的书写，经过了头插尾插的洗礼后，读者朋友们是不是感觉这个代码变的非常简单呢？下面给出代码：

//在pos位置之后插入节点
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//pos newnode pos->nextnewnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}

2.9. 删除指定结点的数据

这个操作就类似前面的头删尾删操作，废话不多说直接进入正题：

在我们想要删除数据的时候一定要判断该链表是不是只有哨兵位，这个操作在删除操作是必须的，为了不让大家忘记，小编就在这里多叨叨几句。

首先，我们还是以上面的链表举例（ps：这个链表是真好用），此时我们就以删除d2为例，我可不是跟他有仇(。-ω-)zzz。

之后我们进行的操作还是那几部，我们直接让d1的下一个结点指向d3，让d3的上一个结点指向d1，此时我们就建立起了d1和d3之间的联系：

此时我们直接把d2free掉，这里就实现了对于指定位置结点的数据的删除：

这里小编多说一句，如果想要设置指定结点，这里我们可以搭配上面的查找双链表的数据操作来进行同步实现，下面小编给上代码：

void LTErase(LTNode* pos)
{assert(pos);assert(!Listpanduan(pos));LTNode* prev = pos->prev;LTNode* next = pos->next;prev->next = next;next->prev = prev;
}

3.0.销毁双链表

终于，我们实现了对于双链表的部分代码，上面的代码并不是全部，而是小编学过的一部分，双链表指定不可能只有这一点功能，就比如我们可以在指定结点之后插入数据，那么我们是不是也可以在指定位置之前插入数据呢？知识是无穷的，各位读者朋友感兴趣的话可以继续来扩展双链表的功能，下面废话不多说，我们要进入链表销毁喽！

对于双链表的销毁，对比于单链表，双链表的销毁是有点麻烦的，不过麻烦程度是比较小的，我们这里也是用到了循环，我们需要把双链一个一个的进行销毁，此时需要注意的是，我们对哨兵位做出了改变，所以需要传双指针，此时我们可以用一个指针记录哨兵位，之后我们对链表每一个结点进行销毁，最后我们需要把哨兵位也销毁掉，此时我们就实现了对于链表的销毁，写到这里，小编突然觉得前面说的话有点错，删除也没有那么麻烦，可能小编刚才脑子瓦特了，下面展示代码：

void LTDestroy(LTNode** phead)
{LTNode* pour = *phead;while (pour != phead){LTNode* next = pour->next;free(pour);pour = NULL;pour = next;}free(*phead);*phead = NULL;pour = NULL;
}

此时我们已经实现了双链表的各种功能，小编本来想要写到这里就展示所有的源代码，不过小编想起我似乎没讲过链表的分类，于是小编先讲分类，等会在给大家的源码，对此不感兴趣的读者朋友可以直接跳到文章最后~

3.链表的分类

小编在文章开头说过，本文讲的是双向不带头循环链表，所以细心的读者朋友已经知道了链表其实根据类别分为八类，分别是：

1.单向不带头不循环链表（也就是小编前面写的单链表）：

2.单向带头不循环链表：

3.单向不带头循环链表：

4.单向带头循环链表：

5.双向带头循环链表：

6.双向不带头不循环链表：

7.双向带头不循环链表：

8.双向不带头循环链表：

4.代码展示

4.1.List.h

//现在我们来进行双链表的书写
//双链表，是带头双向循环链表
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDataType;
typedef struct List {LTDataType date;struct List* next; //存放下一个结点的地址struct List* prev; //存放上一个函数结点的地址
}LTNode;//初始化双链表
void LTInit(LTNode** pphead);//双链表的尾插
void LTPushBack(LTNode* phead, LTDataType x);//双链表的打印
void LTPrint(LTNode* phead);//双链表的头插
void LTPushFront(LTNode* phead, LTDataType x);//双链表的尾删
void LTPopBack(LTNode* phead);//双链表的头删
void LTPopFront(LTNode* phead);//查找双链表的数据
LTNode* LTFind(LTNode* phead, LTDataType x);//在指定位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);//删除指定节点的数据
void LTErase(LTNode* pos);//销毁双链表
void LTDestroy(LTNode** phead);

4.2.List.c

void LTInit(LTNode** pphead)
{*pphead = (LTNode*)malloc(sizeof(LTNode));assert(*pphead);(*pphead)->date = -1;(*pphead)->next = (*pphead)->prev = *pphead;
}//先创建一个新的结点（对于任何插入操作都得有这个玩意）
LTNode* LTbuynode(LTDataType x)
{LTNode* p1 = (LTNode*)malloc(sizeof(LTNode));assert(p1);p1->date = x;p1->next = p1->prev = p1;
}
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);  //首先哨兵位不能是空的LTNode* newnode = LTbuynode(x);phead->prev->next = newnode;newnode->next = phead;newnode->prev = phead->prev;phead->prev = newnode;
}void LTPrint(LTNode* phead)
{LTNode* pour = phead->next;while (pour != phead){printf("%d->", pour->date);pour = pour->next;}printf("\n");
}void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTbuynode(x);LTNode* next = phead->next;newnode->next = next;next->prev = newnode;phead->next = newnode;newnode->prev = phead;
}bool Listpanduan(LTNode * phead)   //在使用bool关键字的时候记得先有头文件
{return phead == phead->next;
}
void LTPopBack(LTNode* phead)
{assert(phead);//先判断是不是只有哨兵位assert(!Listpanduan(phead));LTNode* prev = phead->prev;prev->prev->next = phead;phead->prev = prev->prev;free(prev);prev = NULL;
}void LTPopFront(LTNode* phead)
{assert(phead);assert(!Listpanduan(phead));LTNode* next = phead->next;phead->next = next->next;next->prev = phead;free(next);next = NULL;
}LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pour = phead->next;while (pour != phead){if (pour->date == x)return pour;pour = pour->next;}return NULL;
}//在pos位置之后插入节点
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//pos newnode pos->nextnewnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}void LTErase(LTNode* pos)
{assert(pos);assert(!Listpanduan(pos));LTNode* prev = pos->prev;LTNode* next = pos->next;prev->next = next;next->prev = prev;
}void LTDestroy(LTNode** phead)
{LTNode* pour = *phead;while (pour != phead){LTNode* next = pour->next;free(pour);pour = NULL;pour = next;}free(*phead);*phead = NULL;pour = NULL;
}