当前位置: 首页 > news >正文

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&#xff08;0下标为第一个位置&#xff09; 8、删除第一个关键字key …...

mongodb是怎么分库分表的

在构建高性能的数据库架构时&#xff0c;MongoDB的分库分表策略扮演着至关重要的角色&#xff0c;它通过一系列精细的步骤确保了数据的高效分布与访问。以下是对这一过程的详尽阐述&#xff0c;旨在提供一个清晰且优化过的理解框架。 确定分片键&#xff08;Shard Key&#xf…...

C++自研游戏引擎-碰撞检测组件-八叉树AABB检测算法实现

八叉树碰撞检测是一种在三维空间中高效处理物体碰撞检测的算法&#xff0c;其原理可以类比为一个管理三维空间物体的智能系统。这个示例包含两个部分&#xff1a;八叉树部分用于宏观检测&#xff0c;AABB用于微观检测。AABB可以更换为均值或节点检测来提高检测精度。 八叉树的…...

spring boot对接clerk 实现用户信息获取

在现代Web应用中&#xff0c;用户身份验证和管理是一个关键的功能。Clerk是一个提供身份验证和用户管理的服务&#xff0c;可以帮助开发者快速集成这些功能。在本文中&#xff0c;我们将介绍如何使用Spring Boot对接Clerk&#xff0c;以实现用户信息的获取。 1.介绍 Clerk提供…...

一种动态地址的查询

背景 当我们注入一个进程&#xff0c;通过函数地址进行call时经常会遇到这样的一个问题。对方程序每周四会自动更新。更新后之前的函数地址就变化了&#xff0c;然后需要重新找地址。所以&#xff0c;我就使用了一个动态查询的方式。 第一步&#xff1a;先为需要call的函数生…...

周雨彤:用角色与生活,诠释审美的艺术

提到内娱审美优秀且持续在线的女演员&#xff0c;周雨彤绝对是其中最有代表性的一个。 独树一帜的表演美学 作为新生代演员中的实力派代表&#xff0c;周雨彤凭借细腻的表演和对角色的深度共情&#xff0c;在荧幕上留下了多个令人难忘的“出圈”形象。在《我在他乡挺好的》中…...

使用jks给空apk包签名

1、在平台官方下载空的apk包&#xff08;上传应用时有提醒下载&#xff09; 2、找到jdk目录&#xff0c;比如C:\Program Files\Java\jdk1.8\bin&#xff0c;并把下载的空包apk和jks文件放到bin下 3、以管理员身份运行cmd&#xff0c;如果不是管理员会签名失败 4、用cd定位到…...

500. 键盘行 771. 宝石与石头 简单 find接口的使用

500. 键盘行1 给你一个字符串数组 words &#xff0c;只返回可以使用在 美式键盘 同一行的字母打印出来的单词。键盘如下图所示。 请注意&#xff0c;字符串 不区分大小写&#xff0c;相同字母的大小写形式都被视为在同一行。 美式键盘 中&#xff1a; 第一行由字符 "qwer…...

仙剑世界手游新手攻略 仙剑世界能用云手机玩吗

欢迎来到《仙剑世界》手游的仙侠世界&#xff01;作为新手玩家&#xff0c;以下是一些详细的攻略和建议&#xff0c;帮助你快速上手并享受游戏的乐趣。 一、新手职业推荐 1.轩辕&#xff1a;这是一个偏辅助的职业&#xff0c;可以给队友提供输出加成等增益效果&#xff0c;不过…...

[题解]2024CCPC重庆站-小 C 的神秘图形

Sources&#xff1a;K - 小 C 的神秘图形Abstract&#xff1a;给定正整数 n ( 1 ≤ n ≤ 1 0 5 ) n(1\le n\le 10^5) n(1≤n≤105)&#xff0c;三进制字符串 n 1 , n 2 ( ∣ n 1 ∣ ∣ n 2 ∣ n ) n_1,n_2(|n_1||n_2|n) n1​,n2​(∣n1​∣∣n2​∣n)&#xff0c;按如下方法…...

NPS内网穿透SSH使用手册

1、说明 nps-一款轻量级、高性能、功能强大的内网穿透代理服务器 github地址&#xff1a;https://github.com/ehang-io/nps 官网文档地址&#xff1a;https://ehang-io.github.io/nps/#/?idnps 2、服务端 下载地址&#xff1a;https://github.com/ehang-io/nps/releases 下…...

大幂计算和大阶乘计算【C语言】

大幂计算&#xff1a; #include<stdio.h> long long int c[1000000]{0}; int main() {long long a,b,x1;c[0]1;printf("请输入底数&#xff1a;");scanf("%lld",&a);printf("请输入指数&#xff1a;");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 是一个实时系统监控工具&#xff0c;用于查看系统的资源使用情况和进程状态。 示例 以下是一些常用的 top 命令示例&#xff1a; top &#xff1a;动态显示结果&#xff0c;每 3 秒刷新一次。 top -d 2&#xff1a;动态显示结果&#xff0c;每 2 秒刷新一次。 top …...

Leetcode 424-替换后的最长重复字符

给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符&#xff0c;并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。 在执行上述操作后&#xff0c;返回 包含相同字母的最长子字符串的长度。 题解 可以先做LCR 167/Leetcode 03再做本题 滑动窗口&…...

《StyleDiffusion:通过扩散模型实现可控的解耦风格迁移》学习笔记

paper&#xff1a;2308.07863 目录 摘要 1、介绍 2、相关工作 2.1 神经风格迁移&#xff08;NST&#xff09; 2.2 解耦表示学习&#xff08;DRL&#xff09; 2.3 扩散模型&#xff08;Diffusion Models&#xff09; 3、方法 3.1 风格移除模块 3.2 风格转移模块 3.3 …...

Django 创建表时 “__str__ ”方法的使用

在 Django 模型中&#xff0c;__str__ 方法是一个 Python 特殊方法&#xff08;也称为“魔术方法”&#xff09;&#xff0c;用于定义对象的字符串表示形式。它的作用是控制当对象被转换为字符串时&#xff0c;应该返回什么样的内容。 示例&#xff1a; 我在初学ModelForm时尝…...

图像处理之CSC

CSC 是 Color Space Conversion&#xff08;色彩空间转换&#xff09;的缩写&#xff0c;它涉及图像处理中的亮度、饱和度、对比度和色度等参数的调整。这些参数是图像处理中的核心概念&#xff0c;通常用于描述和操作图像的颜色信息。 以下是亮度、饱和度、对比度和色度与 CS…...

C语言数组之二维数组

C语言 主要内容 数组 二维数组 数组 二维数组 定义 二维数组本质上是一个行列式的组合&#xff0c;也就是说二维数组由行和列两部分组成&#xff0c;属于多维数组。二维数组数据是通过行列进行解读。二维数组可被视为一个特殊的一维数组&#xff0c;相当于二维数组又是一…...

PyTorch 源码学习:阅读经验 代码结构

分享自己在学习 PyTorch 源码时阅读过的资料。本文重点关注阅读 PyTorch 源码的经验和 PyTorch 的代码结构。因为 PyTorch 不同版本的源码实现有所不同&#xff0c;所以笔者在整理资料时尽可能按版本号升序&#xff0c;版本号见标题前[]。最新版本的源码实现还请查看 PyTorch 仓…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...

LLaMA-Factory 微调 Qwen2-VL 进行人脸情感识别(二)

在上一篇文章中,我们详细介绍了如何使用LLaMA-Factory框架对Qwen2-VL大模型进行微调,以实现人脸情感识别的功能。本篇文章将聚焦于微调完成后,如何调用这个模型进行人脸情感识别的具体代码实现,包括详细的步骤和注释。 模型调用步骤 环境准备:确保安装了必要的Python库。…...

xmind转换为markdown

文章目录 解锁思维导图新姿势&#xff1a;将XMind转为结构化Markdown 一、认识Xmind结构二、核心转换流程详解1.解压XMind文件&#xff08;ZIP处理&#xff09;2.解析JSON数据结构3&#xff1a;递归转换树形结构4&#xff1a;Markdown层级生成逻辑 三、完整代码 解锁思维导图新…...