前言
这篇博客我们来继续探讨链表,上篇博客我们讨论了单链表,其实链表的种类有很多,但最常用的除了单链表之外,还有个双向链表,今天我们就来总结下双向链表
💓 个人主页:小张同学zkf
⏩ 文章专栏:数据结构
若有问题 评论区见📝
🎉欢迎大家点赞👍收藏⭐文章
目录
1.链表的分类
链表的结构非常多样,以下情况组合起来就有8种(2 x 2 x 2)链表结构
我们上篇博客的单链表其实就是不带头单向不循环链表
那本篇博客的双向链表就是带头双向循环链表
2.双向链表的结构
注意:这里的“带头”跟前面我们说的“头节点”是两个概念,实际前面的在单链表阶段称呼不严 谨,带头链表里的头节点,实际为“哨兵位”,哨兵位节点不存储任何有效元素,只是站在这里“放哨的” ,“哨兵位”存在的意义: 遍历循环链表避免死循环。
3.实现双向链表
那么双向链表如何实现那
老规矩依旧三个文件,头文件,两源文件
我们先来在头文件把各个函数声明好,先定义双向链表节点结构体
这个就是双向链表节点的结构体,里面有两个指针,一个指针指向下一个节点,一个指针指向上一个节点
接着把各个函数声明好
声明好之后,我们就开始在.c文件中进行定义
双向链表不能为空,它始终都有一个节点,是哨兵位(头结点),所以我们先定义一个申请节点的函数,申请节点空间,跟我们的单链表一样都是用malloc申请
代码如下:
头结点,我们不需要任何数据,所以传个-1就行
我们接着来初始化双向链表,那有人直接上来把俩指针置空,我们好好想想这样初始化对吗
好了,代码如下
初始化好后我们就开始尾插
无论尾插,还是头插,都不影响头结点的变化,就算是头插,也是在头结点之后插入,头结点永远不变
考虑好这一点,我们接下来画图分析如何尾插那
首先,我们先通过申请节点函数,申请新节点。
我们可以看到新来的节点newnoad上一个节点指向d3,但d3的位置我们如何获取那,d3是不是就是头结点的上一个节点,所以我们可以根据头结点来获取,newnoad下一个节点是头结点,所以直接指向头结点就行了,接着是头结点phead上一个指向指向新的尾结点,d3下一个节点就是newnoad新的尾结点。
分析完了就可以写代码了
别忘了,我们把哨兵位(头结点)传进来要确保有效,不能为空,否则双向链表就无效,所以要断言头结点。
尾插玩我们来看头插,头插一定于要记得对于双向链表来说,头插是在头结点之后插入,不是再头结点之前!!!!
我们画图分析
由图可以清晰看出是在head后面插的,但我们要知道这个指向顺序,我们一定要先让newnoad的下一个节点指向d1,再让newnoad上一节点指向head,接着就是指向新节点的过程,我们假如让head先指向新的节点,那我们无法通过head得知d1的位置,就会很麻烦,我们可以先通过head指向d1得知d1的位置,再通过d1的上一个节点指向newnoad,最后再phead直接指向新节点就可以了,这个顺序比较方便点
OK分析完就可以写代码了
别忘了断言双链表是否有效
插完我们再来看删,我们先来看尾删
分析完可以写代码了
代码如下
注意这里不仅要判断双链表是否有效,还要判断链表不能为空,否则无法删除,feel完记得置空
尾删完我们头删,我们画图分析
代码如下
我们继续来定义在指定位置之后删除的函数
我们依旧画图分析
但我们得考虑一个特殊情况,当pos节点是尾结点时,那就是尾插,但是由于尾插函数需要传头结点,所以不能直接调用尾插函数,我们这个逻辑分析,也符合尾插的应用,所以这个特殊情况也是符合我们刚刚分析的顺序
代码如下
我们接下来定义删除节点的函数
我们画图表示
代码如下
我们定义打印函数
打印函数就特别简单,直接遍历函数,while循环的条件就是当节点的下一个指针不指向头结点时,循环成立,如果是跳出循环
代码如下
我们定义一个查找函数
查找函数也是遍历条件个打印函数一样
代码如下
我们最后定义销毁函数
销毁函数,挨个遍历节点,然后销毁节点,最后头结点释放掉
代码如下
我们要注意一点
定义完函数,别忘了用另一个源文件进行检测
以下是双向链表的所有代码
.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int LTDataType;
//定义双向链表节点的结构
typedef struct ListNode
{
LTDataType data;
struct ListNode* next;
struct ListNode* prev;
}LTNode;
//声明双向链表中提供的方法
//初始化
//void LTInit(LTNode** pphead);
LTNode* LTInit();
void LTDesTroy(LTNode* phead);
void LTPrint(LTNode* phead);
//插入数据之前,链表必须初始化到只有一个头结点的情况
//不改变哨兵位的地址,因此传一级即可
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);
//删除pos节点
void LTErase(LTNode* pos);
LTNode* LTFind(LTNode* phead, LTDataType x);
.c
#include"List.h"
void LTPrint(LTNode* phead)
{
LTNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("\n");
}
//申请节点
LTNode* LTBuyNode(LTDataType x)
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if (node == NULL)
{
perror("malloc fail!");
exit(1);
}
node->data = x;
node->next = node->prev = node;
return node;
}
//初始化
//void LTInit(LTNode** pphead)
//{
// //给双向链表创建一个哨兵位
// *pphead = LTBuyNode(-1);
//}
LTNode* LTInit()
{
LTNode* phead = LTBuyNode(-1);
return phead;
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
//phead phead->prev newnode
newnode->prev = phead->prev;
newnode->next = phead;
phead->prev->next = newnode;
phead->prev = newnode;
}
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
//phead newnode phead->next
newnode->next = phead->next;
newnode->prev = phead;
phead->next->prev = newnode;
phead->next = newnode;
}
//尾删
void LTPopBack(LTNode* phead)
{
//链表必须有效且链表不能为空(只有一个哨兵位)
assert(phead && phead->next != phead);
LTNode* del = phead->prev;
//phead del->prev del
del->prev->next = phead;
phead->prev = del->prev;
//删除del节点
free(del);
del = NULL;
}
//头删
void LTPopFront(LTNode* phead)
{
assert(phead && phead->next != phead);
LTNode* del = phead->next;
//phead del del->next
phead->next = del->next;
del->next->prev = phead;
//删除del节点
free(del);
del = NULL;
}
LTNode* LTFind(LTNode* phead, LTDataType x)
{
LTNode* pcur = phead->next;
while (pcur != phead)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
//没有找到
return NULL;
}
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = LTBuyNode(x);
//pos newnode pos->next
newnode->next = pos->next;
newnode->prev = pos;
pos->next->prev = newnode;
pos->next = newnode;
}
//删除pos节点
void LTErase(LTNode* pos)
{
//pos理论上来说不能为phead,但是没有参数phead,无法增加校验
assert(pos);
//pos->prev pos pos->next
pos->next->prev = pos->prev;
pos->prev->next = pos->next;
free(pos);
pos = NULL;
}
void LTDesTroy(LTNode* phead)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
LTNode* next = pcur->next;
free(pcur);
pcur = next;
}
//此时pcur指向phead,而phead还没有被销毁
free(phead);
phead = NULL;
}
test.c
#include"List.h"
void ListTest01()
{
//LTNode* plist = NULL;
//LTInit(&plist);
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPrint(plist);
LTNode* find = LTFind(plist, 3);
//LTInsert(find, 66);
LTErase(find);
find = NULL;
LTPrint(plist);
LTDesTroy(plist);
//plist = NULL;
//if (find == NULL)
//{
// printf("找不到!\n");
//}
//else {
// printf("找到了!\n");
//}
//LTPushFront(plist, 1);
//LTPrint(plist);
//LTPushFront(plist, 2);
//LTPrint(plist);
//LTPushFront(plist, 3);
//
//
测试尾删
//LTPopBack(plist);
//LTPrint(plist);
//LTPopBack(plist);
//LTPrint(plist);
//LTPopBack(plist);
//LTPrint(plist);
测试头删
//LTPopFront(plist);
//LTPrint(plist);
//LTPopFront(plist);
//LTPrint(plist);
//LTPopFront(plist);
//LTPrint(plist);
//LTPopBack(plist);
//LTPrint(plist);
}
int main()
{
ListTest01();
return 0;
}
结束语
本篇博客有关双向链表的实现总结结束,中间有什么问题,可以评论区发出来,中间有些细节,可能没有那么深入,欢迎大家来补充
OK,感谢观看!!!
版权声明:本文为博主作者:小张同学zkf原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/m0_74091744/article/details/137777737