让双向链表不在云里雾里

server/2025/3/16 15:03:22/

又来博客留下我的足迹了,哈哈哈,这次是对于双向链表的理解

目录

创建双向链表

申请结点:

双向链表初始化:

双向链表插入结点:

双向链表删除结点:

双向链表的打印:

双向链表的查找:

双向链表的销毁:

结语:


在双向链表中有头双向循环,无头双向循环,有头双向不循环,无头双向不循环,而我将要介绍的是有头双向循环,别看名字长,其实就是只纸老虎,只要我们理解它的结构,问题自然迎刃而解了结构图如下:

创建双向链表

从上面的结构图我们不然发现,我们创建需要定义什么指针域和数据域

typedef int LTDataType;
typedef struct ListNode
{struct ListNode* prev;//指针域struct ListNode* next;//指针域LTDataType data;//数据域
}LTNode;

申请结点:

与单链表代码差不多,将其指针域置空,就不再过多赘述

LTNode* BuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//申请空间if (newnode == NULL){perror("malloc fail");return;}newnode->data = x;//赋值newnode->next = NULL;newnode->prev = NULL;return newnode;//返回创建的结点
}

双向链表初始化:

我们只需将自己连向自己,下一个指向上一个,上一个指向下一个,如图:

LTNode* LTInit()
{LTNode* phead = BuyNode(-1);//传空,为phead申请空间phead->next = phead->prev;phead->prev = phead->next;return phead;//返回头结点
}

双向链表插入结点:

头插:

我们先将新结点的后指针指向第一个结点的数据域,第一个结点的前指针指向新结点的数据域,新结点的前指针亦然,可能文字可能形容有点模糊,所以我们看下图:

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyNode(x);LTNode* Next = phead->next;//保存下一个结点的地址,防止丢失//新结点与后结点链接newnode->next = Next;Next->prev = newnode;//新结点与头节点链接newnode->prev = phead;phead->next = newnode;
}

温馨提示:如果没有保存下一个结点的地址,则需先跟后结点链接,在与头结点相连

尾插:

链表尾插相对于单链表的尾插来说要容易许多,因为我们可以轻松找到尾,然后改变指针指向即可,如下图:

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyNode(x);//创建新结点LTNode* tail = phead->prev;//找尾//尾结点与新结点相连newnode->prev = tail;tail->next = newnode;//新结点与头结点相连newnode->next = phead;phead->prev = newnode;
}

在指定位置插入:

我们通常会在指定位置之前插入,找到指定位置前一个,然后改变指针方向即可,如图:

void LTInsert(LTNode* phead, LTNode* pos, LTDataType x)
{assert(phead);LTNode* newnode = BuyNode(x);LTNode* front = pos->prev;//找到指定位置前一个结点//新结点与指定结点相连newnode->next = pos;pos->prev = newnode;//新节点与指定结点前一个结点相连front->next = newnode;newnode->prev = front;
}

双向链表删除结点:

头删:

我们先要判断链表是否为空,如果为空就不用删除了;因为之后要释放删除的结点,所以我们还需保存一下,这样就可以了

bool LTEmpty(LTNode* phead)
{return phead == phead->next;
}
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//判断链表是否为空LTNode* del = phead->next;LTNode* Next = phead->next->next;//第一结点的下一个结点与头结点相连Next->prev = phead;phead->next = Next;free(del);//释放掉这个结点del = NULL;
}

尾删:

尾删就比较容易了,将尾结点释放,然后改变指针指向,就这样完成了^ - ^

void LTPopBack(LTNode* phead)
{assert(phead);assert(phead != phead->next);//或assert(!LTEmpty(phead))LTNode* tail = phead->prev;LTNode* Pretail = tail->prev;//头节点与尾结点的前一个结点相连Pretail->next = phead;phead->next = Pretail;free(tail);//释放尾结点tail = NULL;
}

在指定位置删除:

找到要删除结点的前一个和后一个,然后两个结点相互链接,这样就能够删除了,如图:

void LTErase(LTNode* phead, LTNode* pos)
{assert(phead);LTNode* front = pos->prev;//找到前结点LTNode* back = pos->next;//找到后结点//前结点和后结点相连front->next = back;back->prev = front;free(pos);//释放指定节点pos = NULL;
}

双向链表的打印:

提到打印,我们会用到遍历循环,那循环结束的标志是什么呢?有一个好主意,我们可以先从第一个结点开始打印,然后向后循环遍历,直至遍历到头结点,循环结束^_^,如下图:

void LTPrint(LTNode* phead)
{LTNode* begin = phead->next;while (begin != phead)//循环继续条件{printf("%d<=>", begin->data);begin = begin->next;}printf("\n");
}

双向链表的查找:

遍历一遍链表,然后找要查找的元素

LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x)return cur;cur = cur->next;}return NULL;//没找到
}

双向链表的销毁:

将动态申请的空间释放掉,并循环释放每一个结点,防止内存泄漏的风险

void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;LTNode* next = cur->next;while (cur != phead){LTNode* next = cur->next;//防止找不到下一个结点free(cur);cur = next;}free(phead);//释放头结点
}

结语:

纸短情长,不尽依依,谢谢观看!


http://www.ppmy.cn/server/175455.html

相关文章

Kubernetes学习笔记-移除Nacos迁移至K8s

项目服务的配置管理和服务注册发现由原先的Nacos全面迁移到Kubernetes上。 一、移除Nacos 移除Nacos组件依赖。 <dependency><groupId>com.alibaba.cloud</groupId><artifactId>spring-cloud-starter-alibaba-nacos-discovery</artifactId> <…

mac安装navicat及使用

0.删除旧的 sudo rm -Rf /Applications/Navicat\ Premium.app sudo rm -Rf /private/var/db/BootCaches/CB6F12B3-2C14-461E-B5A7-A8621B7FF130/app.com.prect.NavicatPremium.playlist sudo rm -Rf ~/Library/Caches/com.apple.helpd/SDMHelpData/Other/English/HelpSDMIndexF…

Rubick:基于 Electron 的开源插件化桌面效率工具箱

Rubick 是一款基于 Electron 构建的开源桌面工具箱&#xff0c;专为追求高效办公和个性化体验的用户设计。它通过自由集成丰富的插件&#xff0c;让用户能够根据自己的需求打造极致的桌面端效率工具。 软件命名由来Rubick 的名字来源于《DOTA2》中的英雄 Rubick&#xff08;拉…

深入解析java Socket通信中的粘包与拆包问题及解决方案(中)

推荐关联阅读&#xff1a;Java Socket通信基础及拆包粘包问题模拟&#xff08;上&#xff09; 一、粘包与拆包现象解析 1.1 问题本质 在TCP协议的网络通信中&#xff0c;发送端写入的数据单元与接收端读取的数据单元不一致的现象称为粘包&#xff08;合并数据包&#xff09;…

自动化测试-网页聊天室

项目介绍&#xff1a; 针对基于WebSocket协议的网页端即时通讯系统&#xff0c;主导设计并实施全流程自动化测试方案。通过构建模块化测试框架&#xff0c;完成对核心业务场景&#xff08;用户登录鉴权、消息同步、实时聊天等&#xff09;的自动化验证&#xff0c;最终达成测试…

AI大模型测试用例生成平台

AI测试用例生成平台 项目背景技术栈业务描述项目展示项目重难点 项目背景 针对传统接口测试用例设计高度依赖人工经验、重复工作量大、覆盖场景有限等行业痛点&#xff0c;基于大语言模型技术实现接口测试用例智能生成系统。 技术栈 LangChain框架GLM-4模型Prompt Engineeri…

如何用Deepseek制作流程图?

使用Deepseek制作流程图&#xff0c;本质上是让AI根据你的需求&#xff0c;生成相关流程图的代码&#xff0c;然后在流程图编辑器中渲染&#xff0c;类似于Python一样&#xff0c;ChatGPT可以生成代码&#xff0c;但仍需在IDE中执行。 你知道绘制流程图最高效的工具是什么吗&a…

@SpringBootApplication

SpringBootApplication拓展 一. SpringBootConfiguration注解 是SpringBoot的注解, 标识一个类为配置类, 与Configration功能一致 run方法初始化了SpringBootConfiguration注解 注解源码 Target(ElementType.TYPE)//类型 Retention(RetentionPolicy.RUNTIME)//生命周期 Docu…