【双向链表】的建立、插入、删除、查找和销毁
目录
前言
二、实现节点的插入
1.尾插
2.头插
3.打印插入的节点数据判断函数实现是否正确
三、实现节点的删除
1.尾删
2.头删
四、实现特定节点的查找，特定位置的删除、插入
1、查找
2.特定位置后插入数据
3.删除特定位置的数据
五、双向链表的销毁
总结
前言
本文将讲解有关双向链表的建立，插入、删除，查找数据以及双向链表的销毁。有关代码大家可以复制主页的git链接进行查看哟！😏😁
一、建立双向链表
带头双向循环链表简称 ”双向链表“
这⾥的“带头”跟前⾯我们说的“头节点”是两个概念，实际前⾯的在单链表阶段称呼不严谨，但是为了我们更好的理解就直接称为单链表的头节点。
带头链表⾥的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这⾥“放哨 的” “哨兵位”存在的意义： 遍历循环链表避免死循环。
类似于单链表的插入删除查找，这里我们同样建立三个文件，头文件list.h用来定义结构体以及声明函数，源文件list.c进行函数的具体实现,test.c用来检测函数的实现
由图1，可知我们的节点中应该包括：数据+指向下一个节点的指针+指向上一个节点的指针
则我们在头文件中建立得
//方便后续更改数据类型
typedef int LTdatatype;//定义双向链表结点的结构
typedef struct ListNode
{LTdatatype data;struct ListNode* next;struct ListNode* prev;}LTNode;二、实现节点的插入
在插入节点之前我们需要单独写一个函数来创建节点，来避免代码的冗余.由前面结构体的结构可知，我们创建的节点有next和prev两个指针，为了实现循环我们该如何确定其指向呢？
如图易知只有当next和prev都指向自身时，才能实现自循环
//创建结点
LTNode* LTbuynode(LTdatatype x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail!");exit(1);//如果申请失败则直接退出}//创建成功newnode->data = x;//自循环，指向自己newnode->prev = newnode->next = newnode;return newnode;
}
前面我们提到双向链表有一个哨兵位作为头节点，因此在插入有效数据之前我们要先对链表进行初始化，这里我们用LTinit函数来实现。
注意🤔：这里是我们要将创建的指针变量的地址传入才能改变指针变量的值。这里由于哨兵位中的数据无效，所以我们随便取一个值即可
//初始化链表
void LTinit(LTNode** phead)
{//创建双向链表的哨兵位*phead = LTbuynode(-1);//这里随便给哨兵位一个值即可}1.尾插
让我们来分析一下尾插的情景：
如图，由phead我们就能知道最后一个节点d3的地址为phead->pre.因此我们只需要传哨兵位节点的指针和要插入的数据即可。修改指针的指向我们可以先修改newnode（蓝线），再修改原链表（绿线）
//尾插
void LTPushback(LTNode* phead, LTdatatype x)
{//头节点不能为NULLassert(phead);//首先创建新结点LTNode* newnode = LTbuynode(x);newnode->prev = phead->prev;newnode->next = phead;//注意这里我们不能调换两个等式的顺序，不然phead->prev会被覆盖phead->prev->next = newnode;phead->prev = newnode;//但是也可以不以头节点为中介，可以newnode//phead->prev = newnode;//newnode->prev->next = newnode;}
2.头插
头插可以同理进行分析：
我们先修改newnode的指向，然后再处理head和d1的指向
//头插
void LTPushfront(LTNode* phead, LTdatatype x)
{assert(phead);//创建新结点LTNode* newnode = LTbuynode(x);//phead newnode phead->nextnewnode->prev = phead;newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;
}
3.打印插入的节点数据判断函数实现是否正确
这里我们定义一个函数遍历链表打印链表中的元素
注意：哨兵位不是有效数据，我们要从第一个有效节点开始打印！循环结束条件应该是到打完最后一个节点时停止
//打印
void LTPrint(LTNode* phead)
{assert(phead);//跳过头结点从第一个有效结点开始打印LTNode* pcur = phead->next;while (pcur!=phead)//到最后一个结点时停止打印{printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");//记得换行}
三、实现节点的删除
1.尾删
易知要删去末尾的节点，我们只需要知道phead即可，因为phead->prev即为del的地址。这里为了方便我们将将删去的节点的地址用del存储起来
//尾删
void LTDetback(LTNode* phead)
{//必须有效且非空链表assert(phead && phead->next != phead);//phead del->prev del//我们将删除节点的位置存储起来LTNode* del = phead->prev;phead->prev = del->prev;del->prev->next = phead;
}注意：如果链表为空没有有效节点或者链表头节点为空，无论是头删还是尾删我们都不能实现删除！！！
2.头删
注意：此时头删是删除第一个有效节点，哨兵位不能动它！
这里同尾删，我们用del记录下删除点的位置
//头删
void LTDetfront(LTNode* phead)
{assert(phead && phead->next != phead);//phead del del->nextLTNode* del = phead->next;phead->next = del->next;del->next->prev = phead;
}
四、实现特定节点的查找，特定位置的删除、插入
1、查找
从有效节点开始遍历链表，找到了就返回该节点的地址，没有找到就返回NULL
//查找
LTNode* LTfind(LTNode* phead, LTdatatype x)
{assert(phead);//从第一个有效结点开始查找LTNode* pos = phead->next;while (pos != phead){if (pos->data == x)return pos;pos = pos->next;}//如果最后没有找到返回NULLreturn NULL;
}
2.特定位置后插入数据
基本思路：先由LTfind函数找到特定位置，然后再将数据插入到该位置之后，这里我们重新写一个函数，专门用来传查找到的位置的地址 ；同理这里我们先改变newnode的指向，然后再改变原链表的指向
//在指定位置后插入新节点
void LTposinsert(LTNode* pos, LTdatatype x)
{//首先判断pos不是空指针assert(pos);LTNode* newnode = LTbuynode(x);//pos newnode pos->nextnewnode->prev = pos;newnode->next = pos->next;pos->next->prev = newnode;pos->next = newnode;}3.删除特定位置的数据
基本思路：找到该数据的位置，将地址传入函数，然后直接删除，要记得最后将pos置为NULL！
//删除特定位置的节点
void LTdelpos(LTNode* pos)
{assert(pos);//pos->prev pos pos->nextpos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);//记住把pos置为NULLpos = NULL;
}五、双向链表的销毁
为了保证接口的一致性，减少记忆，这里我们仍然传值（这里即为一级指针）来销毁链表。
注意：这里因为只是传值，所以我们要对原始创建的指针变量销毁。如:假如是LTdestory（plist）
我们需要再test.c中对plist再进行销毁。
//销毁链表
void LTdestory(LTNode* phead)//注意这里是传参，所以原来传入的指针还未被销毁
{assert(phead);//从有效节点开始删除LTNode* pcur = phead->next;while (pcur != phead){//先把后一个节点保存不然等会找不到了LTNode* next = pcur->next;free(pcur);//释放内存，pcur变成野指针pcur = next;}//最后pcur指向phead，但phead还没销毁free(phead);phead = NULL;}
总结
完结撒花🎆🎇🎆🎇👍
如果对你有帮助的话，不放点赞收藏关注一下啦，一起努力~
以上就是所有有关双向链表的知识点啦，需要全部代码的友友可以戳下方链接哟：
具体代码
https://gitee.com/qingruxu-dw/test_c/blob/master/shuangxiang/shuangxiang.sln