Java数据结构---链表
目录
一、链表的概念和结构
1、概念
2、结构
二、链表的分类
三、链表的实现
1、创建节点类
2、定义表头
3、创建链表
4、打印链表
5、链表长度
6、看链表中是否包含key
7、在index位置插入val(0下标为第一个位置)
8、删除第一个关键字key
9、删除链表中所有key元素
10、清空链表
11、完整代码
一、链表的概念和结构
1、概念
链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
2、结构
链表分为多个节点,每个节点可以由下图表示:

其中,value为这个节点所存储的数据的值,next为下一个节点的地址。以5个节点的链表为例,它们的数据值分别为12,23,34,45,56:
其中,第五个节点由于没有后继节点,所以next域存储的是空指针null。
二、链表的分类
链表的结构多种多样,按以下情况分类:
1. 单向或者双向
2. 带头或者不带头
3. 循环或者非循环
共可分出8种类型。
三、链表的实现
本篇文章我们主要用代码实现无头单向非循环链表。
1、创建节点类
static class ListNode{//ListNode为一个节点public int val;public ListNode next;public ListNode(int val) {//构造函数this.val = val;}
}
2、定义表头
//定义表头public ListNode head;
3、创建链表
方法一:直接进行val的赋值和对next的初始化
public void createList(){ListNode node1=new ListNode(12);ListNode node2=new ListNode(26);ListNode node3=new ListNode(30);ListNode node4=new ListNode(45);ListNode node5=new ListNode(56);node1.next=node2;node2.next=node3;node3.next=node4;node4.next=node5;this.head=node1;}
方法二:头插法
//头插法public void addFirst(int data){ListNode node=new ListNode(data);if(head==null){head=node;return;}node.next=head;head=node;}
头插法是指在头节点的位置插入一个新节点。
//尾插法public void addLast(int data){ListNode node=new ListNode(data);if(head==null){head=node;return;}ListNode cur=head;while(cur.next!=null){cur=cur.next;}cur.next=node;}
尾插法是指在尾节点的位置插入一个新节点。
4、打印链表
//打印链表public void show(){ListNode cur=head;while(cur!=null){System.out.print(cur.val+" ");cur=cur.next;}System.out.println();}
注意:为了使head在打印的过程中不受影响,我们可以重新定义一个cur,把head赋值给cur,这样head既不受影响,又可以继续下面的操作,两全其美。具体代码为:ListNode cur=head;,以下同理。
5、链表长度
//链表长度public int size(){ListNode cur=head;int count=0;while(cur!=null){count++;cur=cur.next;}return count;}
6、看链表中是否包含key
//看链表中是否包含keypublic boolean contains(int key){ListNode cur=head;while(cur!=null){if(cur.val==key){return true;}cur=cur.next;}return false;}
7、在index位置插入val(0下标为第一个位置)
//插入链表public void addIndex(int index,int val){if(index<0||index>size()){return;}if(index==0){addFirst(val);}else if(index==size()){addLast(val);}else{ListNode node=new ListNode(val);ListNode cur=findPindex(index);node.next=cur.next;cur.next=node;}}//找出index前一个节点private ListNode findPindex(int index){int i=1;ListNode cur=head;while(i<=index-1){cur=cur.next;i++;}return cur;}
因为在插入之前需找出index的前一个节点,所以我们又创建了一个私有方法findPindex。
8、删除第一个关键字key
//删除第一个出现的关键字keypublic void remove(int key){if(head==null){return;}if(head.val==key){head=head.next;}ListNode cur=findPkey(key);if(cur==null){return;}ListNode dve=cur.next;cur.next=dve.next;}//找出key前一个节点private ListNode findPkey(int key){ListNode cur=head;while(cur.next!=null){if(cur.next.val==key){return cur;}cur=cur.next;}return null;}
因为在删除之前需找出key的前一个节点,所以我们又创建了一个私有方法findPkey。
9、删除链表中所有key元素
//删除链表中的所有key元素public void removeAllKey(int key){if(head==null){return;}ListNode cur=head.next;ListNode prev=head;while(cur!=null){if(cur.val==key){prev.next=cur.next;cur=cur.next;}else{prev=cur;cur=cur.next;}}if(head.val==key){head=head.next;}}
10、清空链表
public void clear(){ListNode cur=head;while(cur!=null){ListNode curN=cur.next;cur.next=null;cur=curN;}head=null;}
11、完整代码
public class MySingleList {static class ListNode{public int val;public ListNode next;public ListNode(int val) {this.val = val;}}//定义表头public ListNode head;//创建链表public void createList(){ListNode node1=new ListNode(12);ListNode node2=new ListNode(26);ListNode node3=new ListNode(30);ListNode node4=new ListNode(45);ListNode node5=new ListNode(56);node1.next=node2;node2.next=node3;node3.next=node4;node4.next=node5;this.head=node1;}//打印链表public void show(){ListNode cur=head;while(cur!=null){System.out.print(cur.val+" ");cur=cur.next;}System.out.println();}//链表长度public int size(){ListNode cur=head;int count=0;while(cur!=null){count++;cur=cur.next;}return count;}//看链表中是否包含keypublic boolean contains(int key){ListNode cur=head;while(cur!=null){if(cur.val==key){return true;}cur=cur.next;}return false;}//头插法public void addFirst(int data){ListNode node=new ListNode(data);if(head==null){head=node;return;}node.next=head;head=node;}//尾插法public void addLast(int data){ListNode node=new ListNode(data);if(head==null){head=node;return;}ListNode cur=head;while(cur.next!=null){cur=cur.next;}cur.next=node;}//插入链表public void addIndex(int index,int val){if(index<0||index>size()){return;}if(index==0){addFirst(val);}else if(index==size()){addLast(val);}else{ListNode node=new ListNode(val);ListNode cur=findPindex(index);node.next=cur.next;cur.next=node;}}//找出index前一个节点private ListNode findPindex(int index){int i=1;ListNode cur=head;while(i<=index-1){cur=cur.next;i++;}return cur;}//删除第一个出现的关键字keypublic void remove(int key){if(head==null){return;}if(head.val==key){head=head.next;}ListNode cur=findPkey(key);if(cur==null){return;}ListNode dve=cur.next;cur.next=dve.next;}//找出key前一个节点private ListNode findPkey(int key){ListNode cur=head;while(cur.next!=null){if(cur.next.val==key){return cur;}cur=cur.next;}return null;}//删除链表中的所有key元素public void removeAllKey(int key){if(head==null){return;}ListNode cur=head.next;ListNode prev=head;while(cur!=null){if(cur.val==key){prev.next=cur.next;cur=cur.next;}else{prev=cur;cur=cur.next;}}if(head.val==key){head=head.next;}}public void clear(){ListNode cur=head;while(cur!=null){ListNode curN=cur.next;cur.next=null;cur=curN;}head=null;}
}
以上便是本篇文章的全部内容,感谢大家的支持!下期见~~~
相关文章:
Java数据结构---链表
目录 一、链表的概念和结构 1、概念 2、结构 二、链表的分类 三、链表的实现 1、创建节点类 2、定义表头 3、创建链表 4、打印链表 5、链表长度 6、看链表中是否包含key 7、在index位置插入val(0下标为第一个位置) 8、删除第一个关键字key …...
mongodb是怎么分库分表的
在构建高性能的数据库架构时,MongoDB的分库分表策略扮演着至关重要的角色,它通过一系列精细的步骤确保了数据的高效分布与访问。以下是对这一过程的详尽阐述,旨在提供一个清晰且优化过的理解框架。 确定分片键(Shard Key…...
C++自研游戏引擎-碰撞检测组件-八叉树AABB检测算法实现
八叉树碰撞检测是一种在三维空间中高效处理物体碰撞检测的算法,其原理可以类比为一个管理三维空间物体的智能系统。这个示例包含两个部分:八叉树部分用于宏观检测,AABB用于微观检测。AABB可以更换为均值或节点检测来提高检测精度。 八叉树的…...
spring boot对接clerk 实现用户信息获取
在现代Web应用中,用户身份验证和管理是一个关键的功能。Clerk是一个提供身份验证和用户管理的服务,可以帮助开发者快速集成这些功能。在本文中,我们将介绍如何使用Spring Boot对接Clerk,以实现用户信息的获取。 1.介绍 Clerk提供…...
一种动态地址的查询
背景 当我们注入一个进程,通过函数地址进行call时经常会遇到这样的一个问题。对方程序每周四会自动更新。更新后之前的函数地址就变化了,然后需要重新找地址。所以,我就使用了一个动态查询的方式。 第一步:先为需要call的函数生…...
周雨彤:用角色与生活,诠释审美的艺术
提到内娱审美优秀且持续在线的女演员,周雨彤绝对是其中最有代表性的一个。 独树一帜的表演美学 作为新生代演员中的实力派代表,周雨彤凭借细腻的表演和对角色的深度共情,在荧幕上留下了多个令人难忘的“出圈”形象。在《我在他乡挺好的》中…...
使用jks给空apk包签名
1、在平台官方下载空的apk包(上传应用时有提醒下载) 2、找到jdk目录,比如C:\Program Files\Java\jdk1.8\bin,并把下载的空包apk和jks文件放到bin下 3、以管理员身份运行cmd,如果不是管理员会签名失败 4、用cd定位到…...
500. 键盘行 771. 宝石与石头 简单 find接口的使用
500. 键盘行1 给你一个字符串数组 words ,只返回可以使用在 美式键盘 同一行的字母打印出来的单词。键盘如下图所示。 请注意,字符串 不区分大小写,相同字母的大小写形式都被视为在同一行。 美式键盘 中: 第一行由字符 "qwer…...
仙剑世界手游新手攻略 仙剑世界能用云手机玩吗
欢迎来到《仙剑世界》手游的仙侠世界!作为新手玩家,以下是一些详细的攻略和建议,帮助你快速上手并享受游戏的乐趣。 一、新手职业推荐 1.轩辕:这是一个偏辅助的职业,可以给队友提供输出加成等增益效果,不过…...
[题解]2024CCPC重庆站-小 C 的神秘图形
Sources:K - 小 C 的神秘图形Abstract:给定正整数 n ( 1 ≤ n ≤ 1 0 5 ) n(1\le n\le 10^5) n(1≤n≤105),三进制字符串 n 1 , n 2 ( ∣ n 1 ∣ ∣ n 2 ∣ n ) n_1,n_2(|n_1||n_2|n) n1,n2(∣n1∣∣n2∣n),按如下方法…...
NPS内网穿透SSH使用手册
1、说明 nps-一款轻量级、高性能、功能强大的内网穿透代理服务器 github地址:https://github.com/ehang-io/nps 官网文档地址:https://ehang-io.github.io/nps/#/?idnps 2、服务端 下载地址:https://github.com/ehang-io/nps/releases 下…...
大幂计算和大阶乘计算【C语言】
大幂计算: #include<stdio.h> long long int c[1000000]{0}; int main() {long long a,b,x1;c[0]1;printf("请输入底数:");scanf("%lld",&a);printf("请输入指数:");scanf("%lld",&b…...
【Linux】详谈 进程控制
目录 一、进程是什么 二、task_struct 三、查看进程 四、创建进程 4.1 fork函数的认识 4.2 2. fork函数的返回值 五、进程终止 5.1. 进程退出的场景 5.2. 进程常见的退出方法 5.2.1 从main返回 5.2.1.1 错误码 5.2.2 exit函数 5.2.3 _exit函数 5.2.4 缓冲区问题补…...
Linux top 命令
作用 top 是一个实时系统监控工具,用于查看系统的资源使用情况和进程状态。 示例 以下是一些常用的 top 命令示例: top :动态显示结果,每 3 秒刷新一次。 top -d 2:动态显示结果,每 2 秒刷新一次。 top …...
Leetcode 424-替换后的最长重复字符
给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符,并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。 在执行上述操作后,返回 包含相同字母的最长子字符串的长度。 题解 可以先做LCR 167/Leetcode 03再做本题 滑动窗口&…...
《StyleDiffusion:通过扩散模型实现可控的解耦风格迁移》学习笔记
paper:2308.07863 目录 摘要 1、介绍 2、相关工作 2.1 神经风格迁移(NST) 2.2 解耦表示学习(DRL) 2.3 扩散模型(Diffusion Models) 3、方法 3.1 风格移除模块 3.2 风格转移模块 3.3 …...
Django 创建表时 “__str__ ”方法的使用
在 Django 模型中,__str__ 方法是一个 Python 特殊方法(也称为“魔术方法”),用于定义对象的字符串表示形式。它的作用是控制当对象被转换为字符串时,应该返回什么样的内容。 示例: 我在初学ModelForm时尝…...
图像处理之CSC
CSC 是 Color Space Conversion(色彩空间转换)的缩写,它涉及图像处理中的亮度、饱和度、对比度和色度等参数的调整。这些参数是图像处理中的核心概念,通常用于描述和操作图像的颜色信息。 以下是亮度、饱和度、对比度和色度与 CS…...
C语言数组之二维数组
C语言 主要内容 数组 二维数组 数组 二维数组 定义 二维数组本质上是一个行列式的组合,也就是说二维数组由行和列两部分组成,属于多维数组。二维数组数据是通过行列进行解读。二维数组可被视为一个特殊的一维数组,相当于二维数组又是一…...
PyTorch 源码学习:阅读经验 代码结构
分享自己在学习 PyTorch 源码时阅读过的资料。本文重点关注阅读 PyTorch 源码的经验和 PyTorch 的代码结构。因为 PyTorch 不同版本的源码实现有所不同,所以笔者在整理资料时尽可能按版本号升序,版本号见标题前[]。最新版本的源码实现还请查看 PyTorch 仓…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...
【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
Android Wi-Fi 连接失败日志分析
1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分: 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析: CTR…...
Mac软件卸载指南,简单易懂!
刚和Adobe分手,它却总在Library里给你写"回忆录"?卸载的Final Cut Pro像电子幽灵般阴魂不散?总是会有残留文件,别慌!这份Mac软件卸载指南,将用最硬核的方式教你"数字分手术"࿰…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...
MySQL的pymysql操作
本章是MySQL的最后一章,MySQL到此完结,下一站Hadoop!!! 这章很简单,完整代码在最后,详细讲解之前python课程里面也有,感兴趣的可以往前找一下 一、查询操作 我们需要打开pycharm …...
人工智能 - 在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型
在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型。这些平台各有侧重,适用场景差异显著。下面我将从核心功能定位、典型应用场景、真实体验痛点、选型决策关键点进行拆解,并提供具体场景下的推荐方案。 一、核心功能定位速览 平台核心定位技术栈亮…...
QT开发技术【ffmpeg + QAudioOutput】音乐播放器
一、 介绍 使用ffmpeg 4.2.2 在数字化浪潮席卷全球的当下,音视频内容犹如璀璨繁星,点亮了人们的生活与工作。从短视频平台上令人捧腹的搞笑视频,到在线课堂中知识渊博的专家授课,再到影视平台上扣人心弦的高清大片,音…...
