目录
1>>闲话
3>>双向链表的初始化
4>>双向链表的尾插与头插
4.1>>尾插
4.2>>头插
5>>打印
6>>尾删和头删
6.1>>尾删
6.2>>头删
7>>指定位置之后插入与删除
7.1查找指定位置
7.2>>指定位置后插入
7.3>>指定位置删除
8>>销毁
9>>代码
List.h
List.c
test.c
10>>总结
1>>闲话
感谢大家对小编文章的喜欢，小编会持续更新数据结构直到学完，希望大家能跟小编一起学下去，大学总得学点什么吧！加油同学们，废话不多说，步入今天正题！（代码在目录可以找到）
今天内容重点：实现双向链表的增加、删除、查找、修改这几个主要操作！
2>>单链表和双向链表
其实单链表是一个简称，它的全名——单向不带头不循环链表。单向双向很好理解，一个朝着一个方向，一个可以两个方向都走，那么什么是带头？什么是不带头呢？带头就是带哨兵位，在之前的单链表博客里面，有讲到：
哨兵位就也是一个节点，但是该节点不存储任何的有效数据。哨兵位的创建方便我我们进行头插数据。如果有了哨兵位的话，头插的时候，我们就不再需要改变头节点了。如果还是不是很理解的话，那么先看下面链表的实现。或许看完，你就能够理解了。
那么什么是循环？或是不循环？结束的时候指向空指针就代表不循环，那么指向头结点就代表循环。因此就能明白为什么单链表的全称是单向不带头不循环链表了。
那么双向链表全称是什么呢？它正正好好与单链表完全相反——双向带头循环链表。
其实总共有八种链表
这八种每一行可以任意组成——如带头单向循环、带头单向不循环、不带头双向不循环等等。
3>>双向链表的初始化
双向链表的创建包括值、下一个结点next、上一个结点prev
初始化跟单链表不太一样，需要注意的是，phead的next指针和prev指针指向的是自己，不是NULL因为他是循环链表。val的值可以随机给。
4>>双向链表的尾插与头插
它两都属于插入，就给它们归为一起讲，声明除了函数名都一样。这里有细心的同学问了，为什么phead又是一级指针了？之前不是二级吗？恭喜你，细心让你少走弯路！这里因为传的是哨兵位，更改的只是里面的值，并不是哨兵位的地址，那么因此，可以不用传二级指针！好比a=1 传的是a一样，我用b接受，更改b的值并打印，一样能出结果，因此我们用简单的一级指针就好！
尾插和头插代码的实现必然少不了买结点，那么购买结点其实跟初始化差不多，只多了一个传进来的值x。
4.1>>尾插
这里我们以下面这张图为例（图片来源网络，如有侵权，联系删除）
创建一个结点newnode
那么跟他相邻的两个结点必定要改next与prev，还有新节点的prev和next
这就是代码，新节点的前一个指针为phead哨兵位的前一个指针
新节点的后一个指针为phead哨兵位
phead的前一个指针的下一个指针为新节点（理解为前任的下一任变为彭于晏）
phead的前一个指针为新节点。
这里通过观察得知时间复杂度为O（1）
4.2>>头插
头插的话注意实在哨兵位的后一个插入，不是在哨兵位的前面！
代码解释如下：
新节点的前一个结点是phead头结点
新节点的下一个结点时phead的下一个结点
phead的下一个指针的前一个结点是新节点
phead的下一个指针是新节点。
5>>打印
插完了就可以打印下来看看，那么打印的实现就是从哨兵位的下一个结点开始，直到哨兵位结束！
这里观察能发现，时间复杂度也为O（1），那删除也是吗？随我一起看看：
6>>尾删和头删
6.1>>尾删
这里需要assert断言，如果链表为空（代表只有一个哨兵位）那么哨兵位肯定指向自己，所以当不指向自己，也就是不为空的时候，链表执行尾删。
可以拿del来存储尾结点，增加可读性，
del的前一个指针的下一个指针为哨兵位
哨兵位的前一个指针为del的前一个指针，最后别忘记将del释放并置为空！
6.2>>头删
头删代码大差不差，大家看看就好，就不多赘述啦，想必大家差点睡着了吧！哈哈哈，看看谁能坚持到最后！
接下来上演重头戏！
7>>指定位置之后插入与删除
7.1查找指定位置
查找也比较简单，就是跟打印差不多，当找到x就返回当前结点指针，未找到就返回空指针。
它们的声明插入是传指定的位置，和删除的位置。
7.2>>指定位置后插入
这里和头结点差入差不多，大家看看就好啦！
7.3>>指定位置删除
这里也比较简单，就不多说啦，主要想让大家看看代码，可以试着写写，后面也会放出来的。
8>>销毁
想一个一个销毁，我们只需要提前存好下一个，然后在销毁原先这个就好，这时候又有细心的宝宝提问啦，这里不是形参吗？哨兵位怎么销毁哩？很好，
哨兵位出来的时候在外边销毁，
未执行NULL时plist还指向原先那块空间
执行完后，plist置为空！
9>>代码
到这里就结束啦，附上三个文件代码，感兴趣的宝子下去可以自己试试!
List.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
typedef int type;
typedef struct List {type val;struct List* next;struct List* prev;
}slnode;slnode* sliniti();//初始化void slinsertt(slnode* phead, type x);//尾插
void slinserth(slnode* phead, type x);//头插void slprint(slnode* phead);void sldelt(slnode* phead);//尾删
void sldelh(slnode* phead);//头删slnode* slfind(slnode* phead, type x);//查找void slafter(slnode* pos, type x);//指定位置之后插入
void sldel(slnode* del);//指定位置删除void slruin(slnode* phead);//销毁List.c
#include"List.h"slnode* sliniti() {slnode* phead = (slnode*)malloc(sizeof(slnode));phead->val = -1;phead->prev = phead->next = phead;return phead;
}slnode* buynode(type x) {slnode* phead = (slnode*)malloc(sizeof(slnode));phead->val = x;phead->prev = phead->next = phead;return phead;
}
void slinsertt(slnode* phead, type x) {slnode* newnode=buynode(x);newnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}
void slinserth(slnode* phead, type x) {slnode* newnode = buynode(x);newnode->prev = phead;newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;
}
void slprint(slnode*phead) {slnode* pcur = phead->next;while (pcur != phead) {printf("%d -> ", pcur->val);pcur = pcur->next;}printf("\n");
}void sldelt(slnode* phead) {assert(phead != phead->next);slnode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}void sldelh(slnode* phead) {assert(phead != phead->next);slnode* del = phead->next;phead->next = del->next;del->next->prev = phead;free(del);del = NULL;
}
slnode* slfind(slnode* phead,type x) {slnode* pcur = phead->next;while (pcur != phead) {if (pcur->val == x)return pcur;pcur = pcur->next;}return NULL;
}void slafter(slnode* pos, type x) {slnode* newnode = buynode(x);newnode->prev = pos;newnode->next = pos->next;pos->next->prev = newnode;pos->next = newnode;
}void sldel(slnode* del) {del->prev->next = del->next;del->next->prev = del->prev;}void slruin(slnode* phead) {//销毁slnode* pcur = phead->next;while (pcur != phead) {slnode* next = pcur->next;free(pcur);pcur = next;}free(pcur);pcur = NULL;
}
test.c
#include"List.h"void sllist() {slnode* plist = sliniti();slinserth(plist,1);slinserth(plist, 2);slinserth(plist, 3);slprint(plist);slruin(plist);printf("xxxxxxxxxxxxxxxxx");plist = NULL;
}
int main()
{sllist();return 0;
}10>>总结
今天学习了双向链表的相关内容，包括双向链表的增删改查，打印销毁等等，还有单链表和双链表的区别，希望能帮助到大家！如果觉得这篇文章对你有帮助的话，可以求一个一键三连嘛~谢谢谢谢！
附录：
素材来源网络，如有侵权，请联系删除，谢谢啦~
