你真的会数据结构吗：双向链表

❀❀❀ 文章由@不准备秃的大伟原创 ❀❀❀

♪♪♪ 若有转载，请联系博主哦~ ♪♪♪

❤❤❤ 致力学好编程的宝藏博主，代码兴国！❤❤❤

各位铁汁们，大家好啊，这里是持续不断学习的大伟。不知道大家有没有开学或者是上班了呢？反正博主是开学了，那既然开学了，咱们的心态也要从假期生活转变为学习生活了，就需要一丝不苟的汲取知识了，那么废话不多说，赶紧开始今天的学习吧！

上一篇文章我们提到了单向链表，什么，忘了？那还不赶紧回去复习---------> ：单链表

此外，我们还谈到了链表的八种形态，上一篇我们实现的是单向循环不带头链表，今天我们要实现的就是带头双向循环链表，如图：

那么问题来了，有小伙伴一直都好奇的 “带头” 是什么意思，其实很简单：“头” 就是头结点，一般不存储有效数据，而是像一个哨兵一样占着头结点的位置，所以我们一般把“头”称之为“哨兵位” 。那么，开码！

当然了，老规矩三个文件：DLT.h , DLT.c , test.c

DLT.c

首先我们需要定义一个结构体，那我们需要什么样的指针呢？当然了，1.保存链表节点的变量data 2.以便找到链表节点的后面节点的next节点，这些和单链表都是一样的 3.由于是双向链表，所以我们需要一个以便找到链表前面的节点，我们命名为prev：

typedef int LTDataType;
//当然了，一如既往的重命名
typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}DLNode;

接下来就是各种功能的声明：（双向链表和单链表的功能基本差不多，大家自己想一想哦~(ง •_•)ง）

DLNode* LTCreative();
//创建哨兵位
bool DLEmpty(DLNode* phead);
//检查链表是否为空
DLNode* LTBuyNode(LTDataType x);
//创建节点
DLNode* LTSearch(DLNode* phead, LTDataType x);
//寻找某节点
void LTPrint(DLNode* phead);
//打印链表
void LTInsert(DLNode* pos, LTDataType x);
//链表某位置插入
void LTPushFront(DLNode* phead, LTDataType x);
//链表头插
void LTPushBack(DLNode* phead, LTDataType x);
//链表尾插
void LTErase(DLNode* pos);
//链表删除某位置节点
void LTPopFront(phead);
//链表头删
void LTPopBack(DLNode* phead);
//链表尾删
void LTDestroy(DLNode* phead);
//摧毁链表

当然，别忘了头文件的声明：

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

DLT.c

创建头结点

DLNode* LTCreative()
{DLNode* phead = LTBuyNode(-1);
//这里调用了创建节点，并给予哨兵位无效的数据，如-1phead->next = phead;phead->prev = phead;
//由于此时链表没有其他节点，所以哨兵位的前面后面都是自己return phead;
}

创建节点

DLNode* LTBuyNode(LTDataType x)
{DLNode* newnode = (DLNode*)malloc(sizeof(DLNode));//向内存申请空间空间if (newnode == NULL){perror("malloc fail");return NULL;}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;
//因为暂时不确定前后关系，所以全都指向空return newnode;
}

检查链表是否为空

bool DLEmpty(DLNode* phead)
{assert(phead);return phead->next == phead;//如果哨兵位的下一位是自己（前一位也一样）
}

插入节点

void LTInsert(DLNode* pos, LTDataType x)
{assert(pos);DLNode* newnode = LTBuyNode(x);
//创建节点DLNode* prev = pos->prev;prev->next = newnode;pos->prev = newnode;newnode->next = pos;newnode->prev = prev;
}

这里简单给大家画了个图，虽然很丑，但是伴着走读代码应该是很好理解的，不然，你自己试试？上面最后五行代码确实但凭看是比较难理解的，但是看着图，我们就会发现：先创建个prev来充当（保存）pos前面位置的节点，然后改变newnode与prev的前后关系，再改变pos与newnode的关系。

这里大家有没有意识到为什么博主是先写的某位置的插入，而不是头插或者尾插？想必聪明的你已经想到原因了：因为可以复用！

不信，接下来给你展示：

头插

void LTPushFront(DLNode* phead, LTDataType x)
{assert(phead);LTInsert(phead->next,x);
}

尾插

void LTPushBack(DLNode* phead, LTDataType x)
{assert(phead);LTInsert(phead, x);//哨兵位的上一个位置就是链表的尾
}

打印

void LTPrint(DLNode* phead)
{DLNode* cur = phead->next;
//当然，哨兵位不打印while (cur != phead){printf("%d<-->", cur->data);cur = cur->next;}
//遍历链表printf("\n");
}

查找某节点

DLNode* LTSearch(DLNode* phead, LTDataType x)
{assert(phead);DLNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}
//和打印很像，都是要遍历一遍链表

删除某位置的节点

void LTErase(DLNode* pos)
{assert(pos);DLNode* prev = pos->prev;DLNode* next = pos->next;prev->next = next;next -> prev = prev;free(pos);
}

同样的，博主也来一张手稿图：简单来说，就是找到pos位置的前后两个位置，然后将prev和next联系起来，这样子就直接把pos位置的节点略过了（当然，别忘了释放pos位置的空间）。

同样的，为什么博主先写删除某位置，而不是头删或者尾删，大家大声喊出来那两个字：复用！

尾删

void LTPopBack(DLNode* phead)
{assert(phead);assert(!DLEmpty(phead));
//链表为空当然不好删除了，对吧~LTErase(phead->prev);
}

头删

void LTPopBack(DLNode* phead)
{assert(phead);assert(!DLEmpty(phead));LTErase(phead->next);
}

摧毁链表

void LTDestroy(DLNode* phead)
{assert(phead);DLNode* cur = phead->next;
//先将哨兵位当做循环结束的标志，再最后释放while (cur != phead){DLNode* next = cur->next;free(cur);cur = next;}free(phead);
}

o啦，到此我们的双向链表就结束了，是不是感觉要比单链表写的爽啊？毕竟可以有四个地方复用嘛，那，玩一玩呗~：

test.c

test()
{DLNode* plist = LTCreative();LTPushFront(plist, 1);//1LTPrint(plist);LTPushFront(plist, 2);//2<-->1LTPrint(plist);LTPushFront(plist, 3);//3<-->2<-->1LTPrint(plist);LTPushBack(plist, 4);//3<-->2<-->1<-->4LTPrint(plist);LTPushBack(plist, 5);//3<-->2<-->1<-->4<-->5LTPrint(plist);DLNode* pos = LTSearch(plist, 2);if (pos != NULL){LTErase(pos);//3<-->1<-->4<-->5}LTPrint(plist);LTPopBack(plist);//3<-->1<-->4LTPrint(plist);LTPopFront(plist);//1<-->4LTPrint(plist);
}int main()
{test();return 0;
}

我们来看看结果是否对的上：