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 仓…...
【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...
第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...
c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...
【7色560页】职场可视化逻辑图高级数据分析PPT模版
7种色调职场工作汇报PPT,橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版:职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...
动态 Web 开发技术入门篇
一、HTTP 协议核心 1.1 HTTP 基础 协议全称 :HyperText Transfer Protocol(超文本传输协议) 默认端口 :HTTP 使用 80 端口,HTTPS 使用 443 端口。 请求方法 : GET :用于获取资源,…...
基于IDIG-GAN的小样本电机轴承故障诊断
目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) 梯度归一化(Gradient Normalization) (2) 判别器梯度间隙正则化(Discriminator Gradient Gap Regularization) (3) 自注意力机制(Self-Attention) 3. 完整损失函数 二…...
【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制
使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下,限制某个 IP 的访问频率是非常重要的,可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案,使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...
