让双向链表不在云里雾里

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

目录

创建双向链表:

申请结点:

双向链表初始化:

双向链表插入结点:

双向链表删除结点:

双向链表的打印:

双向链表的查找:

双向链表的销毁:

结语:


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

创建双向链表:

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

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.rhkb.cn/news/34402.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

基于SpringBoot的Mybatis和纯MyBatis项目搭建的区别

【由于之前学习MyBatis的时候是跟着视频敲的纯MyBatis项目&#xff0c;以至于在突然看到别人在SpringBoot项目里搭建MyBatis方式的时候很懵比…特此文字形式记录一下区别&#xff08;应该还有好多种其他方式是我不知道的&#xff0c;主要应该就是要知道关键的流程步骤&#xff…

UE4-UE5虚幻引擎,前置学习一--Console日志输出经常崩溃,有什么好的解决办法

有些差异 这么牛逼的引擎&#xff0c;居然有这种入门级别的问题&#xff0c;一触发清理&#xff0c;大概率(80%)会崩溃 无论虚幻5还是UE4都有这个问题&#xff0c;挺烦人的 实在忍不了了&#xff0c;这次&#xff0c;今天 就想问问有什么好的处理方法么&#xff1f;&#x…

学习 springboot -Bean 管理(注册条件)

前言 上一篇 博客 :学习springboot-Bean管理&#xff08;Bean 注册&#xff0c;Bean 扫描&#xff09;-CSDN博客我们了解了 bean 注册需要使用到 Bean 和Import 将第三方jar 包的对象 注入到ioc 容器 如下图所示 通过图片&#xff0c;可以看到Country 对象和Province 对象已…

【云原生技术】编排与容器的技术演进之路

一、编排与容器的技术演进之路 1.1 DockerClient 此时 K8s 只是编排领域的一个选择&#xff0c;而 Docker 此时一家独大&#xff0c;所以 K8s 的客户端只 是作为 Docker 的客户端来调用 Docker 引擎来完成服务。 1.2 RUNC&Shim OCI催生 runcrunc&#xff0c;剥离 Docke…

安卓投屏到mac操作

1. 安装 brew install scrcpy2. 打开手机usb调试 3. 安装 brew install android-platform-tools 4. 重启终端&#xff0c;运行命令 adb devices scrcpy 参考&#xff1a;https://zhuanlan.zhihu.com/p/682491037https://zhuanlan.zhihu.com/p/682491037

c#知识点补充

1.静态类无法被继承 2.线程join方法的使用 作用就是让多个线程&#xff0c;按顺序执行 3.线程里lock的作用 保证每次只执行一次 4.线程池的使用

3分钟复现 Manus 超强开源项目 OpenManus

文章目录 前言什么是 OpenManus构建方式环境准备克隆代码仓库安装依赖配置 LLM API运行 OpenManus 效果演示总结个人简介 前言 近期人工智能领域迎来了一位备受瞩目的新星——Manus。Manus 能够独立执行复杂的现实任务&#xff0c;无需人工干预。由于限制原因大部分人无法体验…

电路原理(电容 集成电路NE555)

电容 1.特性&#xff1a;充放电&#xff0c;隔直流&#xff0c;通交流 2.电容是通过聚集正负电荷来存储电能的 3.电容充放电过程可等效为导通回路 4.多电容并联可以把容量叠加&#xff0c;但是多电容串联就不会&#xff0c;只会叠加电容的耐压值。 6.电容充放电时相当于通路&a…

【redis】hash基本命令和内部编码

文章目录 表示形式命令HSET 和 HGET HEXISTSHDELHKEYSHVALSHGETALLHMGETHLENHSETNXHINCRBYHINCRBYFLOAT命令小结内部编码 表示形式 Redis 自身已经是键值对结构了 Redis 自身的键值对就是通过哈希的方式来组织的 把 key 这一层组织完成之后&#xff0c;到了 value 这一层&…

学习路之TP6 --重写vendor目录下的文件(新建命令)

[TOC](学习路之TP6 --重写vendor目录下的文件(新建命令)) 一、新建命令文件 php think make:command CustomWorker二、修改 复制vendor\topthink\think-worker\src\command\Server.php 内容到app\command\CustomWorker.php 修改继承类&#xff1a;class CustomWorker exten…

Python----数据可视化(Pyecharts三:绘图二:涟漪散点图,K线图,漏斗图,雷达图,词云图,地图,柱状图折线图组合,时间线轮廓图)

1、涟漪特效散点图 from pyecharts.globals import SymbolType from pyecharts.charts import EffectScatter from pyecharts.faker import Faker from pyecharts import options as opts from pyecharts.globals import ThemeType # 绘制图表 es (EffectScatter(init_optsop…

Linux内核网络层分析

网络访问层仍受到传输介质的性质以及相关适配器的设备驱动程序的影响很大。网络层与网络适配器的硬件性质几乎完全分离。为什么说几乎&#xff1f;因为该层不仅负责发送和接收数据&#xff0c;还负责在彼此不直接连接的系统之间转发和路由分组。查找最佳路由并选择适当的网络设…

OpenHarmony子系统开发 - Rust编译构建指导

OpenHarmony子系统开发 - Rust编译构建指导 一、Rust模块配置规则和指导 概述 Rust是一门静态强类型语言&#xff0c;具有更安全的内存管理、更好的运行性能、原生支持多线程开发等优势。Rust官方也使用Cargo工具来专门为Rust代码创建工程和构建编译。 OpenHarmony为了集成C…

分享一个免费的CKA认证学习资料

关于CKA考试 CKA&#xff08;Certified Kubernetes Administrator&#xff09;是CNCF基金会&#xff08;Cloud Native Computing Foundation&#xff09;官方推出的Kubernetes管理员认证计划&#xff0c;用于证明持有人有履行Kubernetes管理的知识&#xff0c;技能等相关的能力…

MySQL的一些八股文

1.什么是BufferPool&#xff1f; Buffer Pool基本概念 Buffer Pool&#xff1a;缓冲池&#xff0c;简称BP。其作用是用来缓存表数据与索引数据&#xff0c;减少磁盘IO操作&#xff0c;提升效率。 Buffer Pool由缓存数据页(Page) 和 对缓存数据页进行描述的控制块 组成, 控制…

卷积神经网络(笔记02)

一、简述在卷积神经网络中池化层的作用&#xff0c;并解释其为何能帮助提高模型性能 。 池化层的作用 1. 降低数据维度 池化操作通过对输入特征图进行下采样&#xff0c;减少特征图的空间尺寸。常见的池化方式有最大池化&#xff08;Max Pooling&#xff09;和平均池化&…

面试系列|蚂蚁金服技术面【1】

哈喽&#xff0c;大家好&#xff01;今天分享一下蚂蚁金服的 Java 后端开发岗位真实社招面经&#xff0c;复盘面试过程中踩过的坑&#xff0c;整理面试过程中提到的知识点&#xff0c;希望能给正在准备面试的你一些参考和启发&#xff0c;希望对你有帮助&#xff0c;愿你能够获…

带环链表的相关知识点

带环链表的相关知识点 1.判断是否有环2.寻找入环节点补充&#xff1a;相交链表 如果链表中有某个节点,可以通过连续跟踪next指针再次到达,则链表中存在环。为了表示给定链表中的环&#xff0c;评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置&#xff08;索引从 0 开…

初探 Threejs 物理引擎CANNON,解锁 3D 动态魅力

简介 Cannon.js 是一个基于 JavaScript 的物理引擎&#xff0c;它可以在浏览器中模拟物理效果。它支持碰撞检测、刚体动力学、约束等物理效果&#xff0c;可以用于创建逼真的物理场景和交互。 参考文档 官方示例 原理 Cannon.js 使用了欧拉角来表示物体的旋转&#xff0c;…

【小沐学Web3D】three.js 加载三维模型(React)

文章目录 1、简介1.1 three.js1.2 react.js 2、three.js React结语 1、简介 1.1 three.js Three.js 是一款 webGL&#xff08;3D绘图标准&#xff09;引擎&#xff0c;可以运行于所有支持 webGL 的浏览器。Three.js 封装了 webGL 底层的 API &#xff0c;为我们提供了高级的…