前言
前面学过单向链表，单向链表其实就是单向不带头的非循环链表，它不能随机查找，必须从第一个结点开始一个一个的遍历，查找效率比较低，且只有一个指向下一个结点的指针next，它想找到上一个结点还是比较困难的，所以我们今天学习的双向链表就很好的弥补了它的一些缺点。
一、双向链表的概念
双向链表，又称为双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
如图所示：
二、双向链的结构设计
三、双链表的基本功能接口
如下所示：
//初始化
LTNode* LTInit();
//打印
void LTPrint(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead,LTDateType x);
//尾删
void LTPopBack(LTNode* phead);
//头插
void LTPushFront(LTNode* phead,LTDateType x);
//头删
void LTPopFront(LTNode* phead);
//在pos前插入
void LTInsert(LTNode* pos,LTDateType x);
//删除pos位置的结点
void LTErase(LTNode* pos);
//销毁链表
void LTDestroy(LTNode* phead);
四、双向链表接口的实现
在此之前先看看双链表的大致模样，如下图：
4.1、创建结点
使用malloc函数开辟动态内存空间，在开辟的同时不要忘记检查是否开辟成功，若开辟成功，将新结点的prev和next指针都指向NULL（空），并将X赋值给新结点的数据data，最后返回该结点
LTNode* CreateLNode(LTNode* phead,LTDateType x)
{
//开辟新结点
LTNode* newnode=(LTNode*)malloc(sizeof(LTNode));
//判断malloc是否成功开辟
if(newnode==NULL)
{
printf("malloc fali");
exit(-1);
}
newnode->next=NULL;
newnode->prev=NULL;
newnode->val=x;
//返回新结点
return newnode;
}
4.2、初始化链表
这里我们使用带哨兵位的链表，因为哨兵位不存储有效空间，所以我们就给个-1，将哨兵位的前驱和后继指向自己，即prev和next指针指向自己，最后返回这个头结点，如图所示：
LTNode* LTInit()
{
//创建哨兵位
LTNode* phead=CreateLNode(-1);
//哨兵位后继指向自己
phead->next=phead;
//哨兵位前驱指向自己
phead->prev=phead;
//返回哨兵位结点
return phead;
}
4.3、打印链表
与单链表的打印不同的是，双链表遍历结束的条件并不是 cur等于空，而是cur==phead，也就是等于头结点，因为尾结点的next指向的是头结点。
代码：
void LTPrint(LTNode* phead)
{
//断言
assert(phead);
//为了美观而这样写的
printf("哨兵位<=>");
LTNode* cur=phead->next;
while(cur!=phead)
{
printf("%d<=>",cur->val);
//让cur往后走，遍历链表
cur=cur->next;
}
printf("\n");
}
4.4、尾插结点
操作要点：
创建新结点，找到位结点tail，将尾结点的后继next指向新结点，新结点的前驱prev指向尾结点，再将新结点的后继next指向头结点，头结点的前驱prev指向新结点即可，也就是将几个结点链起来。
void LTPushBack(LTNode* phead,LTDateType x)
{
assert(phead);
//
LTNode* newnodw=CreateLNode(x);
LTNode* tail=phead->prev;
newnode->prev=tail;
tail->next=newnode;
newnode->next=phead;
phead->prev=newnode;
}
4.5、尾删结点
依旧是遍历找到尾结点定义为指针tail，再找到尾结点tail的前驱，并将其定义为指针tailprev，把tail指向的结点释放掉，然后只需修改它们之间的指向就行了，把tailprev的后继next指向phead，phead的前驱prev指向tailprev。若链表只有哨兵位phead将不能进行删除操作。
代码：
void LTPopBack(LTNode* phead)
{
//断言
assert(phead);
LTNode*tail=phead->prev;
LTNode*tailprev=tail->prev;
free(tail);
phead->prev=tailprev;
tailprev->next=phead;
}
4.6、头插结点
创建新结点，将新结点插到头结点（哨兵位的）后面，而不是前面，搞清楚这里就可以改变几个结点指针的指向了，因为d1是phead的next，所以你可以把d1写成phead->next,改变newnode和d1的指向的时候就可以写成newnode->next=phead->next。
代码：
void LTPushFront(LTNode* phead,LTDateType x)
{
//断言
assert(phead);
LTNode* newnode=CreateLNode(x);
newnode->next=phead->next;
phead->next->prev=newnode;
newnode->prev=phead;
phead->next=newnode;
}
4.7、头删结点
定义两个指针，将哨兵位结点的后面一个，也就是第一个结点定义为first，再将first->next定义为second，把first头结点free释放掉置空，最后改变结点的指向就好了，当你把图画好后的操作就相当简单了。如下图所示：
代码：
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(phead->next!=phead);
LTNode* first=phead->next;
LTNode* second=first->next;
phead->next=second;
second->prev=phead;
free(first);
first=NULL;
}
4.8、在pos结点前面插入
有了前面插入操作的基础，实现此接口的功能岂不是轻而易举？通过pos的位置可以直接找到它的前驱将其定义为posprev，然后再改变posprev、newnode和pos的指向，重新接上结点就行了。
代码：
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* posPrev = pos->prev;
LTNode* newnode = CreateLTNode(x);
posPrev->next = newnode;
newnode->prev = posPrev;
newnode->next = pos;
pos->prev = newnode;
}
4.9、删除pos位置的结点
还是一样根据pos的位置找到它的前驱和后继，并将其定义为posPrev和posNext，将这两个结点链接起来，把pos指向的结点free释放掉即可。看图会更清晰：
代码：
void LTErase(LTNode* pos)
{
assert(pos);
LTNode* posNext = pos->next;
LTNode* posPrev = pos->prev;
posPrev->next = posNext;
posNext->prev = posPrev;
free(pos);
}
4.10、查找链表中的某个元素
从哨兵位的后一个结点开始遍历链表，当cur等于phead停止循环，若找到该元素返回该元素，没找到返回NULL。
代码：
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
//cur从phead的next开始走
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->val == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
4.11、链表的销毁
cur从phead的next开始遍历，依次free释放掉每一个结点。文章来源：https://www.toymoban.com/news/detail-753880.html
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}
五、总结 全部代码
list.c
#include"List.h"
LTNode* CreateLTNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->val = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
LTNode* LTInit()
{
LTNode* phead = CreateLTNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
void LTPrint(LTNode* phead)
{
assert(phead);
printf("哨兵位<=>");
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d<=>", cur->val);
cur = cur->next;
}
printf("\n");
}
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* tail = phead->prev;
LTNode* newnode = CreateLTNode(x);
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
void LTPopBack(LTNode* phead)
{
assert(phead);
// 空
assert(phead->next != phead);
LTNode* tail = phead->prev;
LTNode* tailPrev = tail->prev;
free(tail);
tailPrev->next = phead;
phead->prev = tailPrev;
}
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = CreateLTNode(x);
newnode->next = phead->next;
phead->next->prev = newnode;
phead->next = newnode;
newnode->prev = phead;
}
void LTPopFront(LTNode* phead)
{
assert(phead);
// 空
assert(phead->next != phead);
LTNode* first = phead->next;
LTNode* second = first->next;
phead->next = second;
second->prev = phead;
free(first);
first = NULL;
}
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->val == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
// 在pos前面的插入
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* posPrev = pos->prev;
LTNode* newnode = CreateLTNode(x);
posPrev->next = newnode;
newnode->prev = posPrev;
newnode->next = pos;
pos->prev = newnode;
}
// 删除pos位置
void LTErase(LTNode* pos)
{
assert(pos);
LTNode* posNext = pos->next;
LTNode* posPrev = pos->prev;
posPrev->next = posNext;
posNext->prev = posPrev;
free(pos);
}
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}
List.h
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int LTDateType;
typedef struct ListNode
{
struct ListNode* next;
struct ListNode* prev;
LTDateType val;
}LTNode;
//初始化
LTNode* LTInit();
//打印
void LTPrint(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead,LTDateType x);
//尾删
void LTPopBack(LTNode* phead);
//头插
void LTPushFront(LTNode* phead,LTDateType x);
//头删
void LTPopFront(LTNode* phead);
//查看
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos前插入
void LTInsert(LTNode* pos,LTDateType x);
//删除pos位置的结点
void LTErase(LTNode* pos);
//销毁链表
void LTDestroy(LTNode* phead);
走前给个三连呗~
文章来源地址https://www.toymoban.com/news/detail-753880.html
到了这里，关于双向链表超详解——连我奶奶都能学会的复杂链表(带头双向循环)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
