线性表之双向链表

链表花里胡哨，一应俱全

前言

在这之前，我们已经学习了单链表。我们发现这些链表都是一个接一个朝一个方向接下去，有时，我们想要查找某个结点的时候还得从头开始遍历查找，尽管我们已经学习了顺序表，查找某个数据确实很方便，但是要想插入某个数据就麻烦了。对于这两个缺点，我们今天再来学习一种链表，很好地弥补了这两个缺点。

一、什么是双向链表

在我们了解双向链表之前，我们来认识到底有多少种链表

如上图，我们用一幅图片展示链表之间的关系，根据排列组合可以知道，上面一共有2*2*2=8种，这8种链表挺像的但又不太像。我们之前学习的单链表全称是 不带头单向不循环链表。而我们今天所要学习的双向链表全称是 带头双向循环链表。你就根据文字意思比较一下，两者是不是互补的关系，那么我们将这两种链表学习了之后，相信其他链表也能够信手拈来了。

我们仅看文字可能无法直观地看出来什么，接下来我用几张对比图来看看这几种链表

说了半天，如何来实现双向链表呢？其实你别看它是双向的，实现起来反而比单链表更加简单，不信咱们接下来继续看。

二、双向链表的实现

与之前单链表的实现一样，我主要是用代码来展示实现，其中有一些注意事项我会拿出来着重强调一下。同样地，我们实现双向链表也需要建立三个文件LIst.c ,List.h ,test.c

List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//定义结点
typedef int LTDatatype;
typedef struct LTNode
{LTDatatype data;struct LTNode* next;struct LTNode* prev;
}LTNode;//双向链表的创建
//由于双向链表有一个特殊的地方：一定有一个哨兵位结点，因此不能从空指针开始插入来创建，因此我们得先创一个哨兵位结点//双向链表的创建
LTNode* Init();//尾插
void LTPushBack(LTNode* phead, LTDatatype x);//头插
void LTPushFront(LTNode* phead, LTDatatype x);//打印
void LTPrint(LTNode* phead);//判断链表是否为空
bool LTEmpty(LTNode* phead);//尾删
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** pphead);void LTDesTroy2(LTNode* phead);

如上图所示，这是双向链表的头文件部分，首先不同之处是，结点的组成部分不一样，由于双向链表多了一个指向前驱结点的功能，因此也就多了一个指针域，其他部分与单链表大差不差。还有的就是双向链表的创建与单链表的创建有所区别，对于单链表，我们直接从空进行插入创建，对于双向链表，它本身就有一个结点，我们称它为“哨兵位”结点，它可以说是双向结点的一个标志（其实这是带头结点链表的一个标志，我们这里是在与单链表进行区别）然后我们之后在“哨兵位”结点后面进行操作，从而创建一个双向链表。至于链表最基本的增删改查功能，双向链表同样具备，下面就来给大家展示。

List.c

#define  _CRT_SECURE_NO_WARNINGS
#include"List.h"//申请结点
LTNode* LTBuyNode(LTDatatype x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = newnode->prev = newnode;
//对于双向链表来说，它的两个指针是不指向NULL，由于是循环的，我们绕一圈之后还是会指向它本身的
}//对于双向链表的初始化，其实就是创建一个哨兵位结点，如果没有哨兵位结点就是一个单链表了
LTNode* Init()
{LTNode* phead = LTBuyNode(-1);//一般哨兵位里面存放的是一些无效的数据return phead;
}//尾插
void LTPushBack(LTNode* phead, LTDatatype x)
{assert(phead);// phead phead->prev newnode;LTNode* newnode = LTBuyNode(x);newnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}//头插
void LTPushFront(LTNode* phead, LTDatatype x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead newnode phead->nextnewnode->prev = phead;newnode->next = phead->next;phead->next = newnode;phead->next->prev = newnode;
}//打印
void LTPrint(LTNode* phead)
{//定义一个指针，来遍历打印链表LTNode* pcur = phead->next;//注意：遍历的指针要从第一个有效数据开始，即哨兵位结点后面的那个结点while (pcur !=phead)//注意：双向链表不会遇到NULL，但是我们遇到phead结点时，我们就认为这个遍历一圈了{printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}//判断链表是否为空
bool LTEmpty(LTNode* phead)
{assert(phead);
//对于双向链表空的情况就是哨兵位结点的next指针指向它自己即为空return phead->next == phead;//当这个成立时返回true，否则返回false
}
//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//判断该链表是否为空LTNode* del = phead->prev;//phead del->prev delphead->prev = del->prev;del->prev->next = phead;free(del);del = NULL;
}//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//phead del del->nextLTNode* del = phead->next;phead->next = phead->next->next;phead->next->next->prev = phead;free(del);del = NULL;
}//查找
LTNode* LTFind(LTNode* phead, LTDatatype x)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}//在指定位置之后插入数据
void LTInsert(LTNode* pos, LTDatatype x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//pos newnode pos->nextnewnode->prev = pos;newnode->next = pos->next;pos->next = newnode;pos->next->prev = newnode;
}//在指定位置删除数据
void LTErase(LTNode* pos)
{assert(pos);//pos->prev pos pos->nextpos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}//销毁
void LTDesTroy(LTNode** pphead)
{assert(pphead && *pphead);//pphead 表示的是哨兵位结点的地址，*pphead表示的是哨兵位的内容LTNode* pcur = (*pphead)->next;while (pcur != *pphead){LTNode* NEXT = pcur->next;//对于删除操作要保存上一个数据，否则就找不到下一个了free(pcur);pcur = NEXT;}free(*pphead);*pphead = NULL;pcur = NULL;
}void LTDesTroy2(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* NEXT = pcur->next;free(pcur);pcur = NEXT;}free(phead);phead=pcur=NULL;
}

这里我们需要注意的是对于双向链表来说，如果要想一个指针来遍历一圈链表的话，我们的结束条件是 pcur->next==phead,而且这个pcur指针是从phead->next开始遍历的。因为对于双向链表来说它是不会指向NULL的，那么我们想要将这个链表遍历一遍的话就要转一圈，我们设立的“哨兵位结点”里面存放的并非有效的数据，故我们要从第一个有效数据的位置开始遍历即phead->next。

test.c

#define  _CRT_SECURE_NO_WARNINGS
#include"List.h"test()
{LTNode* plist = Init();LTPushBack(plist,1);LTPushBack(plist,2);LTPushBack(plist,3);LTPushBack(plist,4);LTPushBack(plist,5);LTPrint(plist);//LTNode* pos = LTFind(plist, 3);//LTInsert(pos, 111);//LTPrint(plist);//LTErase(pos);//LTPrint(plist);//if (pos == NULL)//{//	printf("没找到！");//}//else//{//	printf("找到啦！");//}
//	LTDesTroy(&plist);
//	LTPrint(plist);//下面这个销毁与上面的销毁的差别在于参数不同，一个传递的是二级指针，我们可以直接在函数中进行销毁操作，//另外一个传递的是一级指针，我们无法改变其哨兵位结点的内容，故最后我们得 手动将其哨兵位结点置为空LTDesTroy2(plist);plist = NULL;
}
int main()
{test();return 0;
}

这个文件是对我们所写的代码进行测试用的，这里面有一个我们需要注意一下：在上面的销毁这一操作中，我们即可以传递一级指针，我们也可以传递二级指针。有时候我们如果想要接口（函数方法）一致的话（统一使用一级指针），那么我们要手动的将“哨兵位”结点置为NULL。因为，我们传递一级指针的时候，并不会修改头结点的值。