《Java数据结构》--单链表详解

news/2024/7/22 0:26:26/文章来源:https://blog.csdn.net/hyldzbg/article/details/139246813

一.单链表的概念

1.概念

单链表是一种物理存储结构是非连续,非线性的但是在逻辑结构上是连续且线性的,链表是通过一个个结点来实现的,使每个相邻结点之间存在一定关系来将所有结点串起来,在物理存储上像是一条链子。

2.链表的原理

刚刚有说链表是通过结点之间的关系串起整个链表,那么具体是什么关系呢?🤔往下看:

单链表的每个结点分成两部分分别是储存数值域(val)和下一个结点的地址域(next),每个结点都储存这下一个结点的地址,这样是不是就可通过上一个结点找到下一个结点了一次类推就把整个链表连起来了。

接下来我们通过画图来具现化这个链表:

二.单链表的实现

1.单链表的创建

既然每一个结点都是一个引用类型,那么我们就可以定义一个内部类来创建结点。然后我们需要定义一个头节点,这个结点是整个链表的第一个结点,我们可以通过头节点来访问到链表中的每一个节点。链表不像顺序表可以随机下标访问,他只能通过都节点一点点遍历找到目标结点。

//node.next就可以找到下一个结点🥰

2.打印链表

我们要打印链表,首先肯定要遍历链表,刚刚说要通过头节点来找到后面节点,那是不是直接一直head = head.next就行?这样可以完成遍历可是头节点变成了最后一个结点,还怎么找到链表的头呢,所有我们定义一个中间变量 cur = head,然后让cur代替 head向后遍历。

3.尾插

首先创建一个新结点,通过cur遍历到最后一个结点,让最后一个结点连上新节点(cur.next = node)

//记得不要忘记判断链表是否为空哦!!!

4.头插

创建一个新节点,让新节点的下一个为head(node1.next = head)然后把新结点当作头结点

5.指定位置插入

通过cur遍历到指定位置然后插入新节点就行,不过该怎么插呢直接让cur的下一个等于新结点吗?这样的化就找不到后面的结点了,所以这里让新节点的next等于cur的next,然后再让cur的next,等于新结点。这里我画一个图来帮助你理解:

//记得判空哦!!

//如果要插入的位置是头部或者尾部直接头插或者尾插就行

6.获取链表长度

记录遍历了多少个结点就行

7.头删

将头结点置为下一个

8.尾删

遍历到倒数第二个位置然后将他的next置为null

//记得判空,如果链表只有一个结点那么我们可以直接调用刚刚的头删方法

9.指定位置删

先找到要删除的结点的前一个结点,然后直接让这个结点直接指向要删除的结点的后一个结点

//要先判断位置是否合法,和之前一样如果是头部或尾部直接头删尾删就行

10.删除指定数据val

一一遍历链表直到找到val为止(判断条件不能是cur.val != null,不然会越界)

//因为无法判断到头结点位置所有要单独判断

11.删除所有val

遍历数组找到所有val然后删除

//注意,这里必须要在遍历完了之后再判断头结点,否则如果头结点是val的话,进行头删第二个结点就会遍历不到;

12.清空链表

这个应该不用我多说了吗,嘿嘿!!😉

13.修改指定位置的数据val

到这里我想你应该已经对链表比较熟悉了吧,试着自己去实现一下把!🙉😋

三.和顺序表的对比

顺序表的优缺点:

优点:存储空间连续方便下标随机储存

缺点:头插或者中间插入数据要挪动后面数据,效率低下

链表优缺点:

优点:随用随分配内存,易于插入和删除

缺点:遍历困难,不易查找复杂度为o(N)

我们可以看到顺序表和链表的优缺点似乎是互补的

到这里链表就已经聊完了,小编这里只是实现了一个单链表,还有双链表,带头链表,循环链表等感兴趣的话可以自己去了解一下,核心思想都差不多

如果想要练习一些题,欢迎关注博主的刷题博客哦!最后如果有不懂的或者其他间接欢迎在下方评论或私信博主,谢谢你的阅读,也希望可以支持一下博主!!🥰🥰

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1053676.aspx

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

相关文章

【数据分析】Numpy和Pandas库基本用法及实例--基于Japyter notebook实现

各位大佬好 ,这里是阿川的博客 , 祝您变得更强 个人主页:在线OJ的阿川 大佬的支持和鼓励,将是我成长路上最大的动力 阿川水平有限,如有错误,欢迎大佬指正 承接上篇的博客 数据分析—技术栈和开发环境搭…

工作纪实50-Idea下载项目乱码

下载了公司的一份项目代码,发现是gbk格式的,但是我的日常习惯又是utf-8,下载项目以后全是乱码,一脸懵 借用网友的一张图,如果是一个一个文件这么搞,真的是费劲,好几百个文件! 步骤…

React@16.x(11)ref

目录 1,介绍1.1,得到的结果 2,参数类型2.1,字符串(不再推荐)2.2,对象2.3,函数函数调用时机 3,注意点 1,介绍 reference 引用。和 vue 中的 refs 类似&#x…

rk3568_mutex

文章目录 前言1、什么是mutex?1.1mutex互斥体API函数二、实验2.1实验目的2.2源码2.3结果图前言 本文记录的是rk3568开发板基础上做的mutex实验 1、什么是mutex? mutex是互斥体,它是比信号量semaphore更加专业的机制。 在我们编写Linux驱动的时候遇到需要互斥的地方建议使用…

TypeScript系列之-- 数组和元组类型

数组的定义&#xff1a; 第一种&#xff0c;可以在元素类型后面接上[] let list: number[] [1, 2, 3]; 第二种方式是使用数组泛型&#xff0c;Array<元素类型> let list: Array<number> [1, 2, 3]; 如果数组想每一项放入不同数据怎么办&#xff1f;用元组类型…

UE5 双手握剑的实现(逆向运动学IK)

UE5 双手握剑的实现 IK 前言 什么是IK&#xff1f; UE官方给我们提供了很多对于IK处理的节点&#xff0c;比如ABRIK、Two Bone IK、Full Body IK 、CCD IK等&#xff0c;但是看到这&#xff0c;很多人就好奇了&#xff0c;什么是IK&#xff1f; 首先我们来看看虚幻小白人的骨…

leetcode-主持人调度(二)-110

题目要求 思路 1.先将开始时间和结束时间拆分放到两个数组中进行排序 2.如果开始的时间小于结束时间&#xff0c;说明目前没有空闲的人&#xff0c;需要增加人&#xff0c;如果大于等于&#xff0c;说明有人刚结束了主持&#xff0c;可以进行新的主持了&#xff0c;变更到下一…

Java实现对PDF、纵向、横向页面添加自定义水印功能

Java实现对PDF、纵向、横向页面添加自定义水印 效果图 -- 纵向 页面PDF使用到JAR Maven依赖版本效果图 -- 横向页面PDF 效果图 – 纵向 页面PDF 代码如下&#xff1a; 使用到JAR Maven依赖版本 <dependency><groupId>org.apache.pdfbox</groupId><artifa…

2024.05.28学习记录

1. 小林coding 计网复习 2.代码随想录刷题. 图论.和复习数组.链表 3.rosebush完成select组件

BLE蓝牙模块在车联网中的智能开锁、数据监控应用

随着科技的不断发展&#xff0c;车联网已经成为了汽车行业的一个热门话题。在这个领域中&#xff0c;BLE蓝牙模块发挥着重要的作用&#xff0c;特别是在智能开锁和数据监控方面的应用。本文将详细介绍BLE蓝牙模块在这两个方面的应用及其优势。   一、智能开锁   1.车辆远程…

安卓开发--安卓使用Echatrs绘制折线图

安卓开发--安卓使用Echatrs绘制折线图 前期资料安卓使用Echarts绘制折线图1.1 下载 Echarts 安卓资源1.2 新建assets文件1.3 新建布局文件1.4 在布局文件中布局WebView1.5 在活动文件中调用 最终效果 前期资料 Echarts 官网样式预览: https://echarts.apache.org/examples/zh/…

MySQL中视图是什么,有什么作用

目录 一、视图的简介 1.1 什么是视图&#xff1f; 1.2 为什么使用视图&#xff1f; 1.3 视图有哪些规则与限制&#xff1f; 1.4 视图能否更新&#xff1f; 二、视图的创建 三、视图的作用 3.1 用视图简化复杂的联结 3.2 用视图格式化检索出的数据 3.3 用视图过滤数据…

实现echarts多图联动效果

实现echarts多图联动效果 文章目录 实现echarts多图联动效果业务场景实现关键api代码示例&#xff08;vue&#xff09; 业务场景 提示&#xff1a;主要是记录一下多个echarts联动效果实现方案 这本来就是echarts本身自带的api&#xff0c;并没有多高级&#xff0c;奈何寻找的过…

关于MySQL特殊储存引擎的介绍

目录 ——什么是储存引擎&#xff1f; ——关于表的储存引擎查询和建表语句 ---查询建表引擎语句 ---查询当前数据库支持的储存引擎 ---指定建表的储存引擎 ——关于特殊储存引擎的介绍 ---INNODB 特点&#xff1a; 关于INNDB的文件&#xff1a; 逻辑储存结构 ---MyI…

利用cherry pick巧妙地将某次提交单独合并到其他分支

0. 引言 最近在进行系统的多版本并行开发&#xff0c;涉及一些共有基础功能提交时就遇到了麻烦&#xff0c;一份代码需要向多个版本分支进行同步&#xff0c;以保证多版本都能有更新该基础功能。 多次对比提交的方式显然会带来巨大的工作量。但实际上我们可以通过git的cherry…

ES 查询踩坑-全字段匹配

需求&#xff1a;name字段需要全匹配查询 name的映射 普通的must查询 GET power_engin/_search {"from": 0,"size": 10,"query": {"bool": {"must": [{"term": {"name": {"value": "尼…

Java时间类--JDK8

为什么JDK8会又新增时间相关类呢&#xff1f; ① JDK7的时间对象如果需要比较大小的话&#xff0c;必须都先转换成毫秒值&#xff1b;JDK8则不需要&#xff0c;可以直接比较。 ② JDK7的时间对象可以修改&#xff0c;在多线程环境下就会导致数据不安全&#xff1b;JDK8不能修改…

如何找到docker的run(启动命令)

使用python三方库进行 需要安装python解释器 安装runlike安装包 pip3 install runlike 运行命令 runlike -p <container_name> # 后面可以是容器名和容器id&#xff0c;-p参数是显示自动换行实验 使用docker启动一个jenkins 启动命令为 docker run -d \ -p 9002:80…

7个靠谱的副业赚钱方法,宝妈,上班族,学生党可以做的兼职副业

你是否也曾面临过这样的困境&#xff1a;生活费紧张&#xff0c;想要找份兼职来补贴家用或是满足自己的小心愿&#xff1f;别担心&#xff0c;今天我将带领你踏入这个丰富多彩的兼职世界&#xff0c;助你轻松达成月入过千的小目标&#xff01; 在我漫长的兼职探索旅程中&#…

预训练模型语义相似性计算(十一) - M3E和BGE

M3E m3e由MokaAI 训练&#xff0c;开源和评测。 m3e的详细介绍可以看官方的github介绍。本文简要摘录其中一些点&#xff0c;以便后续的应用。 1.千万级 (2200w) 的中文句对数据(开源)。 2.支持同质相似句计算(s2s)和异质检索(s2p)&#xff0c;后续支持代码检索。 3.m3e基座模…