双链表
导言
经过前面几个篇章的内容分享，相信大家对顺序表和单链表的基本操作都已经熟练掌握了。今天咱们将继续分享线性表的链式存储的第二种形式——双链表。在今天的内容中，咱们将介绍双链表的创建以及一些基本操作，接下来跟我一起来看看吧！
一、单链表与双链表
线性表的链式存储称为链表，链表是由数据域和指针域组成。
由一个数据域和一个指针域组成的链表我们称为单链表，单链表的指针域指向后继结点，所以我们在访问单链表时只能从前往后访问。这就导致了一个问题：我们在访问后继结点时的时间复杂度为O(1)，但是在访问前驱结点时的时间复杂度却是O(n)。
为了克服单链表的这种单一访问的缺点，于是我们在单链表的结点上新增了一个指针域，使得链表上的每个结点都由一个数据域和两个指针域组成，双链表的结点结构如下所示：
这两个指针域一个指向后继结点(next)，一个指向前驱结点(prior)，我们将由这种结构的结点构成的链表称为双链表。
双链表和单链表一样，双链表也有带头结点的双链表与不带头结点的双链表，在没有特殊说明的情况下，我们都是以带头结点的双链表进行说明。接下来我们就来看一下与双链表相关的基本操作；
二、双链表类型的创建
我们首先来看一下双链表的类型创建的基本格式：
//双链表类型创建的基本格式
typedef struct DNode {
ElemType data;//数据域
struct DNode* prior, * next;//指针域
}DNode, * DLinkList;//数据类型重命名
//DNode——Double Node——强调的是双链表的结点
//DLinkList——强调的是指向双链表的指针，也就是整个双链表
//prior——在先的，在前的，先前的——指向前驱结点的指针
//next——下一个的，紧接着的，接下来的——指向后继结点的指针
//ElemType——数据元素的数据类型
//data——存储链表数据元素的变量从格式中可以看到，其实双链表与单链表的类型创建格式是一致的，它们之间的差别有以下几点：
- 为了对这两种类型的链表有所区分，单链表的结点类型我们将其定义为
LNode，双链表则是DNode； - 单链表的类型我们将其定义为
LinkList，双链表则是DLinkList； - 在双链表中，我们定义了一个额外的指针
prior用于指向前驱结点；
有了这个基本格式，我们同样还是以整型类型的数据元素为例来定义一个双链表，如下所示：
//双链表类型创建
typedef struct DNode {
int data;
struct DNode* prior, * next;
}DNode, * DLinkList;
int main()
{
DLinkList L;//定义指向双链表的头指针
return 0;
}有了双链表的头指针，接下来我们就可以来创建双链表的头结点并将其初始化了；
三、双链表的初始化
我们先来看一下双链表初始化的基本格式：
//双链表初始化的基本格式
bool InitDLinkList(DLinkList* L)
{
*L = (DNode*)calloc(1, sizeof(DNode));//创建头结点
assert(*L);//如果头结点创建失败，则报错
(*L)->prior = NULL;//初始化前驱指针
(*L)->next = NULL;//初始化后继指针
return true;
}可以看到，对于双链表来说，我们在初始化头结点时不仅要将后继指针进行初始化，还要将前驱指针进行初始化，这样是为了防止这两个指针变成野指针。
- 在单链表中有一点我们没有提到，就是我们在通过
malloc和calloc申请空间后一定要及时的对接收空间的指针进行检测，看是否为空指针。- 当空间申请失败后，这两个函数返回的就是一个空指针，所以为了避免出现问题，我们可以通过assert来进行断言，也可以通过条件语句来进行判断。
- 对指针这一块的知识掌握的不牢固的朋友可以通过【C语言总集篇】指针篇这篇博客来复习一下指针的相关知识点
我们在对双链表初始化之后就可以来通过头插法或者尾插法来创建一个双链表了；
四、双链表的创建
由于双链表的结点结构与单链表的结点结构不同，因此我们在创建双链表时的逻辑也是稍有区别的，如下图所示：
由于多了一个前驱结点，这就导致我们在创建链表时通过头插法在创建第一个表头元素与创建其他的表头元素的步骤稍有不同，如下所示；
用头插法创建第一个表头结点的步骤：
- 新结点的后继指针指向头结点的后继指针指向的对象，即NULL；
- 新结点的前驱指针指向头结点；
- 头结点的后继指针指向新结点；
用C语言来描述的话则是：
//头插法创建第一个表头结点的插入步骤
New_Node->next = Head->next;//新结点的后继指针指向头结点后继指针指向的对象，即NULL
New_Node->prior = Head;//新结点的前驱指针指向头结点
Head->next = New_Node;//头结点的后继指针指向新结点- 注：这个插入顺序要确保第3步的操作一定在第1步操作完后再执行；第2步的操作顺序可以随意放置；
用头插法创建第二个及以上的表头结点的步骤：
- 新结点的后继指针指向头结点的后继指针指向的对象，即表头结点；
- 头结点后继指针指向对象的前驱结点指向新结点；
- 新结点的前驱指针指向头结点；
- 头结点的后继指针指向新结点；
用C语言描述的话则是：
//头插法创建第二个及以上的头结点的插入步骤
New_Node->next = Head->next;//新结点的后继指针指向头结点后继指针指向的对象，即NULL
Head->next->prior = New_Node;//头指针的后继指针指向对象的前驱指针指向新结点
New_Node->prior = Head;//新结点的前驱指针指向头结点
Head->next = New_Node;//头结点的后继指针指向新结点- 注：这个插入顺序要确保第4步的操作一定在第1步与第2步操作完之后执行；第3步操作的顺序可以随意放置；
接下来我们来看一下在这个逻辑下的双链表的头插法的基本格式：
//头插法创建双链表的基本格式
DLinkList DList_HeadInsert(DLinkList* L)
{
DNode* p;//指向新结点的指针
ElemType x = 0;//接收数据元素的变量
……;//获取需要存储的数据元素
while (x != EOF)//通过给循环设置结束条件来控制创建的结束
{
p = (DNode*)calloc(1, sizeof(DNode));//创建新结点
assert(p);//当创建新结点失败时，assert会对指针p进行报错
if (!(*L)->next)//当头结点的后继指针指向空指针时
{
p->data = x;//将数据元素存储到新结点的数据域中
p->next = (*L)->next;//新结点的后继指针指向头结点后继指针指向的对象
p->prior = *L;//新结点的前驱指针指向头结点
(*L)->next = p;//头结点的后继指针指向新结点
}
else
{
p->data = x;//将数据元素存储到新结点的指针域中
p->next = (*L)->next;//新结点的后继指针指向头结点后继指针指向的对象
(*L)->next->prior = p;//头结点的后继指针指向的对象的前驱指针指向新结点
p->prior = *L;//新结点的前驱指针指向头结点
(*L)->next = p;//头结点的后继指针指向新结点
}
……;//获取需要存储的数据元素
}
return (*L);//创建好链表后返回头指针
}但是对于尾插法而言，不管是第一个结点还是最后一个结点的创建，在插入步骤上都是不影响的，因为表尾结点的后继指针肯定是指向NULL的，因此通过尾插法创建的双链表则不需要分情况讨论，对应的尾插法创建格式如下所示：
//尾插法创建双链表的基本格式
DLinkList DList_TailInsert(DLinkList* L)
{
DNode* r = *L;//指向表尾的指针
DNode* s;//指向新结点的指针
ElemType x = 0;//接收数据元素的变量
……;//获取需要存储的数据元素
while (x != EOF)//通过给循环设置结束条件来控制创建的结束
{
s = (DNode*)calloc(1, sizeof(DNode));//创建新结点
assert(s);
s->data = x;//将数据元素存储到新结点的数据域中
s->next = r->next;//新结点的后继指针指向表尾结点的后继指针，即NULL
s->prior = r;//新结点的前驱指针指向表尾结点
r->next = s;//表尾结点的后继指针指向新结点
r = s;//表尾指针指向新结点
……;//获取新的数据元素
}
return(*L);//当链表创建结束，返回头指针
}在创建好双链表后，我们又该如何遍历双链表来访问某个结点呢？
五、双链表的遍历
在给定一个结点后要想对单链表进行遍历的话，我们只能从该结点往后遍历，但是在双链表中，我们既可以从给定结点开始往后遍历，又可以从给定结点开始往前遍历。遍历的方式也很简单，我们只需要将指向双链表的指针往我们需要遍历的方向进行移动就行，如下所示：
//给定结点指针p遍历双链表
while (p->next)//p的后继结点不为空指针
{
p = p->next;//从结点p往后遍历
}
while (p->prior)//p的前驱结点不为空指针
{
p = p->prior;//从结点p往前遍历
}想要对某一个结点进行想过操作时，我们就可以通过这个遍历的方式来找到对应结点并执行相关操作。
六、双链表的查找
由于双链表是与前驱结点以及后继结点进行双向链接的，因此我们在给定双链表的一个结点后，不管是查找该结点的后继结点还是前驱结点，对应的时间复杂度都为O(1)；
在未给定结点的情况下，我们要想查找对应的结点，我们同样可以通过按值查找与按位查找两种查找方式来执行，下面我们来看一下在双链表中，这两种查找方式的基本格式又是如何：
//双链表的按位查找
DNode* GetElem(DLinkList L, int i)
{
if (i < 1)
return NULL;//当查找的位序不合理时返回空指针
DNode* p = L->next;//指向表头结点的指针
int j = 1;//表头结点的位序
while (p && j < i)//当查找结点为空指针时结束循环；当查找结点的位序与目标位序相等时结束循环
{
p = p->next;//继续往后遍历
j++;
}
return p;//查找结束后返回指针p
}如果是已知某一个结点的位序，需要查找另一个结点的位序，我们可以将函数的参数换成已知的结点以及需要查找的结点位序就行，这里就不再展开。下面我们来看一下按值查找的基本格式：
//双链表的按位查找
DNode* LocateElem(DLinkList L, ElemType e)
{
DNode* p = L->next;//指向表头结点的指针
while (p && p->data != e)//当查找结点为空指针时结束循环
//当查找结点的数据域存储的元素与目标元素相等时结束循环
{
p = p->next;//继续往后遍历
}
return p;//查找结束后返回指针p
}对于双链表而言，在进行查找操作时对应的时间复杂度就有以下几种情况：
- 如果是从表头结点或者表尾结点开始进行查找的话，那对应的时间复杂度就是O(n)；
- 如果是已知结点要查找对应的前驱结点或者后继结点的话，那对应的时间复杂度就是O(1)；
- 如果是已知某一结点，需要查找位序在该结点前面或者后面的结点的话，那对应的时间复杂度就是O(n)；
七、双链表的插入
双链表的插入操作也是有前插与后插操作，前插操作的逻辑与单链表一致，都是通过在指点结点的后面插入一个新的结点，再对数据域中存储的数据进行移动从而完成前插操作，下面我们先来看一下双链表前插操作的基本格式：
//双链表的前插操作
bool InsertPriorDNode(DNode* p, ElemType e)
{
assert(p);//指针p为空指针时报错
DNode* q = p->prior;//指针p的前驱结点
assert(q);//指针q为空指针时报错
DNode* s = (DNode*)calloc(1, sizeof(DNode));//创建新结点
assert(s);//指针s为空指针时报错
s->data = e;//将要插入的元素e放入新结点的数据域中
s->next = p;//将新结点的后继指针指向进行前插操作的结点p
p->prior = s;//将结点p的前驱指针指向新结点s
q->next = s;//将前驱结点的后继指针指向新结点s
s->prior = q;//将新结点的前驱指针执行前驱结点q
return true;//完成前插操作后返回true
}在双链表中进行前插操作时，我们有几点需要注意：
- 首先要确定该结点不是头结点，也就是该结点的前驱结点不为空指：
- 当该结点为头结点时，不能进行前插操作，此时给予一定的信息进行提示；
- 当该结点不为头结点时，则可以正常进行前插操作；
- 因为双链表结点的前驱指针直接指向的是前驱结点，因此我们不需要像单链表一样调用函数来查找前驱结点；
- 在进行插入操作时，前驱结点的后继指针执行新结点的操作最好放在最后一步执行；
下面我们来看一下双链表的后插操作：
//双链表的后插操作
bool InsertNextDNode(DNode* p, ElemType e)
{
assert(p);//指针p为空指针时报错
DNode* s = (DNode*)calloc(1, sizeof(DNode));//创建新结点
assert(s);//指针s为空指针时报错
s->data = e;//将要插入的数据放入新结点的数据域中
if (p->next)//结点p的后继结点不为空指针
{
s->next = p->next;//将新结点的后继指针指向结点p的后继结点
p->next->prior = s;//结点p的后继结点的前驱指针执行新结点
s->prior = p;//新结点的前驱指针指向结点p
p->next = s;//结点p的后继指针指向新结点
}
else//结点p的后继结点为空指针
{
s->next = p->next;//将新结点的后继指针指向结点p的后继结点
s->prior = p;//新结点的前驱指针指向结点p
p->next = s;//结点p的后继指针指向新结点
}
return true;//完成后插操作后返回true
}在双链表中我们要执行后插操作，我们也需要注意几点：
- 要判断当前结点的后继结点是否为空指针，从而选择插入操作的执行步骤：
- 当前结点的后继结点不为空指针时，需要将后继结点的前驱指针的指向对象换成新结点；
- 当前结点的后继结点为空指针时，只需要将新结点的后继指针指向空指针就行
- 不管当前结点的后继结点是否为空指针，我们最好都是将当前结点的后继指针指向新结点的操作放在最后执行；
对于双链表而言，不管是前插操作还是后插操作，其对应的时间复杂度都是O(1)，相比于单链表，双链表的执行效率会更高；
八、双链表的删除
如果我想删除双链表中的某个结点时，我们只需要按照以下步骤就能完成删除操作：
- 将当前结点的前驱结点的后继指针指向当前结点的后继结点；
- 将当前结点的后继结点的前驱指针指向当前结点的前驱结点；
- 释放当前结点的空间；
将其转换成C语言则是：
//双链表的删除操作
DNode->prior->next = DNode->next;//将前驱结点的后继指针指向后继结点
DNode->next->prior = DNode->prior;//将后继结点的前驱指针指向前驱结点
free(DNode);//释放当前结点的内存空间如果是删除的结点为表尾结点，则我们只需要将表尾结点的前驱结点指向空指针，然后直接释放表尾结点的空间就行，转换成C语言则是如下所示：
//删除表尾结点
DNode->prior->next = NULL;//表尾结点的前驱结点的后继指针指向空指针
DNode->prior->next = DNode->next;//前驱结点的后继指针，指向后继结点，即空指针
free(DNode);//释放表尾结点的内存空间删除表尾结点时，第一句代码与第二句代码都是可以使用的，效果都一样，二者选其一就行。下面我们将删除操作封装成一个函数的话，则对应的格式如下所示：
//双链表的删除操作
bool DeleteDNode(DNode* p)
{
assert(p);//指针p为空指针时报错
DNode* q = p->prior;//p的前驱结点
assert(q);//当q为空指针时报错
DNode* r = p->next;//p的后继结点
if (r)//后继结点不为空指针时
{
q->next = r;//前驱结点指向后继结点
r->prior = q;//后继结点指向前驱结点
free(p);//释放结点p的内存
}
else
{
q->next = r;//前驱结点指向后继结点，即空指针
free(p);//释放结点p的内存
}
return true;//完成删除操作后返回true
}当对结点进行前删或者后删时，也是相同的逻辑，这不过在这个基础上做一点小小的变动，这里我就不展开介绍了。当我们相对整个双链表进行删除时，我们只需要重复删除表尾结点的操作即可，大家有兴趣的话可以自己尝试着编写一下；
结语
双链表的内容到这里咱们就全部介绍完了，在今天的篇章中，咱们详细介绍了双链表的创建、初始化、查找、插入、删除等基本操作，并给大家附上了对应操作的代码。希望今天的内容能够帮助大家更好的理解双链表及其基本操作。
