链表的概念+MySingleList的实现
文章目录
- 链表
- 一、 链表的概念
- 1.概念
- 2. 结构
- 二、MySingleList的实现
- 1 .定义内部类
- 2 .创建链表
- 3. 遍历链表并打印
- 4.查找单链表中是否包含关键字key
- 5.得到链表的长度
- 6.头插法
- 7. 尾插法
- 8.任意位置插入
- 8.删除结点
- 清空
链表
顺序存储:顺序表/ArrayList
- 优点:给定下标的时候,查找速度快 o(1)
- 缺点:插入和删除时要移动元素o(n) 、每次扩容会浪费资源
由于ArrayList的缺点,我们引入链式存储:链表
一、 链表的概念
1.概念
- 链表在物理层面是非连续的存储结构,在逻辑上是连续的,通过引用链接次序来实现它的逻辑顺序
- 链表由一个个结点组成,结点从堆上申请
- 一个结点起码包含两个域,val域存储数组、next域存储下一个结点的地址
2. 结构
链表由多种结构:由头、无头、单向、双向、循环、非循环
排列组合后有八种,重点了解无头单向非循环链表和无头双向链表
二、MySingleList的实现
无头单向非循环链表的实现
1 .定义内部类
public class MySingleList {//链表是由一个一个的结点所组成的,可以把Node定义成一个内部类static class Node {public int val;//存储的数据public Node next;//存储下一个结点的地址public Node(int val) {//先不设置next,创建一个新的结点时,还不知道下一个结点是什么this.val = val;}}
}
链表是由一个个的结点所组成的,可以把Node定义成一个内部类
- 定义一个val变量存储数据
- 定义一个Node类型的next变量存储下一个结点的地址
public Node head;//代表当前链表的头结点的引用
head 代表当前链表的头结点的引用
- 因为现在写的是不带头结点的单链表,通过一个变量head,来引用当前链表的头结点
- head引用哪个结点,哪个就是当前链表的头结点
2 .创建链表
public void creatList(){//创建一个链表Node node1 = new Node(12);Node node2 = new Node(86);Node node3 = new Node(33);Node node4 = new Node(45);node1.next =node2;node2.next =node3;node3.next =node4;head=node1;//创建头结点}
创建各个结点,给定val值,每个结点的next依次引用下一个结点的地址
确定头结点,head引用node1所引用的地址
3. 遍历链表并打印
public void disPlay() {//不要改变headNode cur = head;//定义一个cur,让cur移动,head不动//链表遍历完,head==null//遍历到尾部,不打印最后一个,head.next==nullwhile (cur!=null){System.out.print(cur.val+" ");cur = cur.next;}System.out.println();}
1.通过cur来代替head,保证head不会发生改变
2.循环的判断依据是cur!=null,这样能遍历完整
cur.next!=null会少打印最后一个
4.查找单链表中是否包含关键字key
public boolean contains(int key) {Node cur = head;while (cur != null) {//当cur为空时,遍历完if (cur.val == key) {return true;}cur = cur.next;//cur向后移动}return false;}
5.得到链表的长度
public int size(){int count = 0;Node cur = head;while (cur!=null) {//遍历一遍链表 o(n)count++;cur=cur.next;}return count ;}
遍历数组,直到cur为null跳出循环,说明已经走完整个链表,返回记录的次数
6.头插法
public void addFirst(int data){Node node = new Node(data);//新建一个结点node.next=head;head = node;}
1.创建新的结点
2.将新结点的next域存放原本头结点的地址值
3.让新结点成为新的头结点
这样就完成了头插法的实现
7. 尾插法
public void addList(int data) {Node node = new Node(data);if (head == null) {//判断头结点为空的情况head = node;//让新建的结点成为头节点return;//}Node cur = head;//让cur代替headwhile (cur.next != null) {cur = cur.next;}//当cur的next为null时,找到了最后一个结点//找到最后一个结点后,插入node结点cur.next = node;}
1.创建一个新结点
2.判断头结点是否为空
3.遍历链表找到当前最后一个结点
4.将新结点插到末尾
链表的插入只是修改指向
8.任意位置插入
public void addIndex(int index, int data) throws IndexOutOfException {checkIndex(index);//先检查index的值是否合法if (index == 0) {//如果index=0,调用头插法addFirst(data);return;}if (index == size()) {//如果index的值为链表长度,调用尾插法addList(data);return;}Node cur = findIndexSubOne(index);//找到index的前一个元素Node node = new Node(data);node.next = cur.next;cur.next = node;}private void checkIndex(int index) {if (index < 0 || index > size()) {throw new IndexOutOfException("index位置不合法");}}//走index-1步,返回当前索引的地址private Node findIndexSubOne(int index) {Node cur = head;int count = 0;while (count != index - 1) {cur = cur.next;count++;}return cur;}
1.调用checkIndex方法先检查index的值是否合法,不合法抛出异常
2.判断索引,如果是0,调用头插法,如果等于链表长,调用尾插法
3.调用findIndexSubOne方法,找到index的前一个节点,返回地址值
4.创建一个新结点,使新结点的next域的值等于前一个结点next域的值
5.再让前一个结点的next域,引用新结点的地址值。
8.删除结点
删除第一次出现关键字为key的结点
public void remove(int key) {if (head == null) {//判断是否是空节点return; //一个结点都没有}if (head.val == key) {//如果当前头结点的元素等于要删除的元素head = head.next;//头结点向后移动return;}Node cur = searchPrev(key);//找到key的前驱结点if (cur == null) {//没有要删除的keyreturn;}Node del = cur.next;//要删除的结点cur.next = del.next;//or cur.next = cur.next.next;}private Node searchPrev(int key) {//找到key的前一个结点Node cur = head;while (cur.next != null) { //cur.next==null,说明cur已经走到最后一个结点if (cur.next.val == key) {//如果cur下一个结点的值等于keyreturn cur;//找到key的前一个结点}cur = cur.next;}return null;//没有你要删除的结点}
1.先定义searchPrev方法,遍历链表,如果cur的下一个结点的值=key,cur就为key的前驱结点
2.判断:如果头结点为空,链表中没有元素,直接返回
3.如果头结点的值,就是要删除的元素,头结点后移,直接返回
4.都不是,进入searchPrev方法,返回前驱结点cur;
5.如果返回的cur==null,说明遍历完链表,没有要删除的元素
6.要删除的结点del就是cur的下一个结点
7.让cur结点的next域引用del的下一个结点的地址;
完成删除
删除所有值为key的节点
public void removeAllKey(int key) {if (head == null) {//如果头结点为空,直接返回return ;}Node prev = head;Node cur = head.next;while (cur != null) {if (cur.val == key) {prev.next = cur.next;//cur = cur.next;} else {prev = cur;//cur = cur.next;}cur = cur.next;}if (head.val == key) {//最后处理头结点//如果头结点的值等于key,头结点后移head = head.next;}}
1.判断头结点是否为空
2.设置prev为头结点,cur为下一个结点(头结点key的情况最后考虑)
3.遍历链表,直到cur==null为止
4.如果cur的值等于key,prev的next域引用cur下一个结点的地址,cur后移一位
5.否则,prev移动到cur,cur后移一位
6.最后处理头结点,如果头结点刚好等于key,将头结点后移一位。
清空
public void clear(){//清空,让链表中所有的结点都不被引用head =null;}
清空,让链表中所有的结点都不被引用,head置为空
点击移步博客主页,欢迎光临~
相关文章:

链表的概念+MySingleList的实现
文章目录 链表一、 链表的概念1.概念2. 结构 二、MySingleList的实现1 .定义内部类2 .创建链表3. 遍历链表并打印4.查找单链表中是否包含关键字key5.得到链表的长度6.头插法7. 尾插法8.任意位置插入8.删除结点清空 链表 顺序存储:顺序表/ArrayList 优点࿱…...

小黑子—Maven基础
Maven基础 一 小黑子的Maven学习1. Mavn的介绍2. Maven基础概念2.1 仓库2.2 坐标2.3 仓库配置 3. 手动写一个maven项目3.1 Maven项目构建命令3.2 插件创建工程 4. IDEA下的maven项目5. 依赖管理5.1 依赖配置5.2 依赖传递5.3 可选依赖(不透明)5.4 排除依赖…...

【Netty专题】【网络编程】从OSI、TCP/IP网络模型开始到BIO、NIO(Netty前置知识)
目录 前言前置知识一、计算机网络体系结构二、TCP/IP协议族2.1 简介*2.2 TCP/IP网络传输中的数据2.3 地址和端口号2.4 小总结 三、TCP/UDP特性3.1 TCP特性TCP 3次握手TCP 4次挥手TCP头部结构体 3.2 UDP特性 四、总结 课程内容一、网络通信编程基础知识1.1 什么是Socket1.2 长连…...

扬帆起航:许战海方法论日文版正式发布
近日,中国头部战略咨询机构‘许战海咨询’最新研究成果《中国汽车行业新能源转型战略》行业白皮书日文版,即将在日本发布。同时发布的日文版核心方法论白皮书还有《主品牌进化战略》、《第二招牌增长战略》、《链主品牌:制造业的竞争之王》等…...

Docker 安装zookeeper
一、安装单机版 1、拉取镜像 docker pull zookeeper2、创建挂载目录 mkdir -p /mydata/zookeeper/{conf,data,logs}3、新建配置文件 cd /mydata/zookeeper/conf vi zoo.cfgdataDir/data dataLogDir/logs tickTime2000 initLimit10 syncLimit5 clientPort21814、单机主机启…...

项目管理与SSM框架(二)| Spring
Spring简介 Spring是一个开源框架,为简化企业级开发而生。它以IOC(控制反转)和AOP(面向切面)为思想内核,提供了控制层 SpringMVC、数据层SpringData、服务层事务管理等众多技术,并可以整合众多…...

Ubuntu系统忘记Root用户密码-无法登录系统-更改Root密码-Ubuntu系统维护
一、背景 很多时候,我们总会设计复杂的密码,但是大多数时候,我们反而会先忘记我们的密码,导致密码不仅仅阻挡其他用户进入系统,同时也阻碍我们进入系统。 本文将介绍在忘记密码的情况下,如何进入系统并更改…...
webSocket 有哪些安全问题?
WebSocket在实现实时通信和双向数据传输方面非常有用,但也存在一些安全问题需要注意。以下是一些与WebSocket相关的安全问题: 1:跨站脚本攻击(XSS): WebSocket在消息传递过程中可能传输恶意脚本ÿ…...

ArcGis打开影像显示全黑解决方法
我们加载图像,显示如下: 解决方法: 问题分析:Gamma值高于1影像亮化,低于1影像暗化。栅格影像导入进来呈现黑色,可能是因为影像的“Gamma校正”设置出现问题,影响了影像的拉伸度、亮度、对比度等…...

雷达基础导论及MATLAB仿真
文章目录 前言一、雷达基础导论二、Matlab 仿真1、SNR 相对检测距离的仿真①、Matlab 源码②、仿真1)、不同 RCS,SNR 相对检测距离仿真2)、不同雷达峰值功率,SNR 相对检测距离仿真 2、脉冲宽度相对所要求的 SNR 仿真①、Matlab 源…...

设计模式再探——适配器模式
目录 一、背景介绍二、思路&方案三、过程1.适配器模式简介2.适配器模式的类图3.适配器模式代码4.适配器模式,类适配器模式和对象的对比5.适配器模式终极奥秘 四、总结五、升华 一、背景介绍 最近公司在对业务模型做构建的时候,涉及到和三方系统的对…...

【无标题】光伏逆变器的IEC62109测试,逆变器IEC62109测试项目
光伏逆变器的IEC62109测试,逆变器IEC62109测试项目 逆变器又称电源调整器,根据逆变器在光伏发电系统中的用途可分为独立型电源用和并网用二种。根据波形调制方式又可分为方波逆变器、阶梯波逆变器、正弦波逆变器和组合式三相逆变器。对于用于并网系统的…...

Windows用VM虚拟机安装MacOS Ventura 13.6系统全流程教程(附资源)
安装成果: 所需容量:至少40GB的硬盘空间,推荐80GB以上。 所需资源 VMware虚拟机激活密钥:VMware Workstation Pro 17.0.2MacOS Ventura 13.6的ISO镜像MacOS的解锁工具卡顿优化工具:beamoff 有人反馈说需要能用的ISO镜…...
PHP7和PHP8的新特性
PHP 7 新特性: 改进的性能:最显著的变化就是性能提升,据官方报告,PHP 7 的速度是 PHP 5.6 的两倍。 标量类型声明:PHP 7 添加了 int, float, string 和 bool 四种标量类型声明,这使得函数可以通过预定义参…...

mysql按照日期分组统计数据(date_formatstr_to_date)
学习链接 mysql按照日期分组统计数据 博主-山茶花开时的 【Mysql专栏学习】 mysql按照日期分组统计数据 Mysql的date_format函数想必大家都使用过吧,一般用于日期时间转化,如下所示 # 可以得出 2023-01-01 08:30:50 select DATE_FORMAT(2023-01-01…...
【C++程序员必修第一课】C++基础课程-07:switch 分支选择
1 本课主要内容: 为什么需要有 switch 多分支选择?应用场景在哪里?switch 多分支选择的应用讲解:case, break,default 2 主要知识点: 为什么需要有 switch 多分支选择 思考一个问题,数学老师需要统计班上同…...
initramfs介绍
initramfs介绍 什么是initramfs? initramfs(Initial RAM Filesystem)是一种临时文件系统,它在Linux系统启动过程中被加载到内存中。它包含了必要的驱动程序、工具和配置文件,用于在内核启动后挂载真实的根文件系统之…...
数据结构与算法:二分查找(心得)
前言 前些天我做了一道题目,题目中要求使用二分查找,我便按照我心中的二分查找,信心满满的提交上去了。结果发现无限循环,后面我便去查阅了资料 二分查找的条件 用于查找的内容需要是有序的查找的数量只能是一个 二分查找的二种方…...

项目管理之分析项目特点的方法
在管理项目时,了解项目的目标和实现方法可以帮助我们更好地规划和执行项目。根据项目的目标和实现方法的不同,可以将项目分为四种类型:地、水、火和气。 对于工程项目,采用基于活动任务的计划管理方法,使用活动网络图…...

MyBatisPlus(二十一)乐观锁
使用场景 用于当有多个用户同时修改同一条数据的时候,只允许有一个修改成功。 实现原理 使用一个字段,用于记录数据的版本。 当修改数据时,会去检测当前版本是否是正在修改的版本,同时修改成功后会把 版本号 1。 实现方式 配…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...

springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...

九天毕昇深度学习平台 | 如何安装库?
pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子: 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...
动态 Web 开发技术入门篇
一、HTTP 协议核心 1.1 HTTP 基础 协议全称 :HyperText Transfer Protocol(超文本传输协议) 默认端口 :HTTP 使用 80 端口,HTTPS 使用 443 端口。 请求方法 : GET :用于获取资源,…...

[ACTF2020 新生赛]Include 1(php://filter伪协议)
题目 做法 启动靶机,点进去 点进去 查看URL,有 ?fileflag.php说明存在文件包含,原理是php://filter 协议 当它与包含函数结合时,php://filter流会被当作php文件执行。 用php://filter加编码,能让PHP把文件内容…...