单链表和双向链表区别 and 双向链表的增删改查！
目录
1>>闲话
2>>单链表和双向链表
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>>总结
今天学习了双向链表的相关内容，包括双向链表的增删改查，打印销毁等等，还有单链表和双链表的区别，希望能帮助到大家！如果觉得这篇文章对你有帮助的话，可以求一个一键三连嘛~谢谢谢谢！
附录：
素材来源网络，如有侵权，请联系删除，谢谢啦~