【数据结构与算法】4.自主实现单链表的增删查改

📚博客主页:爱敲代码的小杨.
✨专栏:《Java SE语法》
❤️感谢大家点赞👍🏻收藏⭐评论✍🏻,您的三连就是我持续更新的动力❤️
🙏小杨水平有限,欢迎各位大佬指点,相互学习进步!

文章目录
- 1. 前言
- 2. 链表
- 3. 单链表的实现
- 3.1 打印链表
- 3.2 头插法
- 3.3 尾插法
- 3.4 任意位置插入元素
- 3.5 查找元素
- 3.6 链表节点个数
- 3.7 删除元素
- 3.8 删除链表中指定的所有元素
- 3.9 清空链表
- 4. 代码
1. 前言
在上一篇《顺序表》中,我们已经熟悉了 ArrayList 的使用并且进行了简单的模拟实现。ArrayList底层使用数组来存储元素,由于其底层是一段连续的空间,当ArrayList 任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后移动,时间复杂度为O(n),效率比较低,因此ArrayList 不适合做任意位置插入和删除比较多的场景。因此:Java集合这种又引入了 LinkedList,即链表结构。
2. 链表
链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中引用链接次序实现的。

注意:
- 从上图可看出,链表结构正在逻辑上是连续的,但是在物理上(内存)不一定连续。
- 现实中的节点一般都是从堆上申请出来的。
- 从堆上申请的空间,是按照一定的额策略来分配的,两次申请的空间可能连续,也可能不连续。
实际中链表的结构非常多样,以下情况组合起来就有8种链表结构:
-
单向或者双向

-
带头或者不带头

-
循环或者非循环

虽然有这么多的链表结构,但是我们重点掌握两种:
- 无头单向非循环链表:结构简单,一般不会单独用来存放数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。
- 无头双向链表:在Java的集合类中
LinkedList底层实现就是无头双向循环链表
3. 单链表的实现
创建一个链表
public class MySingleList {// 节点static class ListNode {public int val; // 数值域 - 存放当前节点的值public ListNode next; // next域 指向下一个节点public ListNode(int val) {this.val = val;}}// 链表的属性 链表的头节点public ListNode head; // nullpublic void createList() {ListNode node1 = new ListNode(1);ListNode node2 = new ListNode(2);ListNode node3 = new ListNode(3);ListNode node4 = new ListNode(4);node1.next = node2;node2.next = node3;node3.next = node4;this.head = node1;}
}
画图表示:

3.1 打印链表
-
怎么从第一个节点走到第二个节点?
答:
head = head.next -
什么时候算是把节点都遍历完成?
答:
head == null
代码实现:
/**** 打印链表*/@Overridepublic void display() {ListNode cur = head;while (cur != null) {System.out.print(cur.val + " ");cur = cur.next;// 让cur这个节点 可以从一个节点走到下一个节点}System.out.println();}
3.2 头插法
在链表的第一个位置插入元素。
思路:
- 插入元素的
next指向head head指向插入元素

代码实现:
/*** 头插法* @param data*/@Overridepublic void addFirst(int data) {ListNode node = new ListNode(data); // 定义一个节点node.next = head;head = node;}
3.3 尾插法
在链表的最后个位置插入元素
思路:
- 判断链表中是否有元素。
- 如果没有元素,直接添加头结点即可。
- 如果有元素,将原链表最后一个元素
next指向插入的元素。

代码实现:
/*** 尾插法* @param data*/@Overridepublic void addLast(int data) {ListNode node = new ListNode(data); // 定义一个节点if (head == null) { // 链表一个元素都没有head = node;} else {ListNode cur = head;while (cur.next != null) {cur = cur.next;}cur.next = node;}}
3.4 任意位置插入元素
思路:
- 判断
index是否合法(index < 0 或者 index 大于链表长度),如果不合法则抛出异常。 - 判断
index等于0或者index等于链表长度,则使用头插法或尾插法 cur找到index - 1位置- 插入元素的
next指向cur的next cur的next指向插入的元素

代码实现:
/*** 在index位置 插入data* @param index* @param data*/@Overridepublic void addIndex(int index, int data) throws IndexException{if (index < 0 || index > size()) {throw new IndexException("index不合法:" + index);}ListNode node = new ListNode(data); // 定义一个节点if (head == null) {head = node;return;}if (index == 0) {addFirst(data);return;}if (index == size()) {addLast(data);return;}ListNode cur = searchPrevIndex(index);node.next = cur.next;cur.next = node;}/*** 找到index-1的位置* @param index* @return*/private ListNode searchPrevIndex(int index) {ListNode cur = head;int count = 0;while (count != index - 1) {cur = cur.next;count++;}return cur;}
异常类:
public class IndexException extends RuntimeException{public IndexException() {}public IndexException(String msg) {super(msg);}
}
3.5 查找元素
代码实现:
/**** 求当前链表 是否存在key* @param key* @return*/@Overridepublic boolean contains(int key) {ListNode cur = head;while (cur != null) {if (cur.val == key) {return true;}cur = cur.next;}return false;}
3.6 链表节点个数
代码实现:
/*** 求当前链表 有多少个节点* @return*/@Overridepublic int size() {ListNode cur = head;int count = 0;while (cur != null) {count++;cur = cur.next;}return count;}
3.7 删除元素
思路:
- 判断链表是否为空,如果为空直接返回
- 判断删除元素是否为头节点,如果是则
head指向head的next - 定义指针找到要删除节点的前一个节点
- 前一个节点的
next指向删除节点的next

代码实现:
/**** @param key*/@Overridepublic void remove(int key) {if (head == null) {return;}if (head.val == key) {head = head.next;return;}ListNode cur = findPrevKey(key);if (cur == null) {return;// 链表里要没有删除的数字}ListNode del = cur.next;cur.next = del.next;}/*** 找到删除节点的前一个节点* @param key* @return*/private ListNode findPrevKey(int key) {ListNode cur = head;while (cur.next != null) {if (cur.next.val == key) {return cur;} else {cur = cur.next;}}return null;}
3.8 删除链表中指定的所有元素
思路:
- 判断链表是否为空,如果是空直接返回
- 定义指针
cur:可能要删除的节点 - 定义指针
prev:可能要删除的节点的前驱 - 判断
cur的val是不是要删除的元素,如果是prev的next指向cur的next,cur指向cur的next;否则prev指向cur,cur指向cur的next - 判断头节点的
val是否为的元素,如果是头节点指向头节点的neext

代码实现:
/*** 删除链表中所有的key* @param key*/@Overridepublic void removeAllKey(int key) {if (head == null) {return;}ListNode prev = head; // 表示当前可能要删除的节点ListNode cur = head.next; // 可能要删除节点的前驱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;}}
3.9 清空链表
当一个对象,没有被引用的时候,就会被回收掉
/*** 清空链表*/@Overridepublic void clear() {head = null;}
4. 代码
代码链接🔗

相关文章:
【数据结构与算法】4.自主实现单链表的增删查改
📚博客主页:爱敲代码的小杨. ✨专栏:《Java SE语法》 ❤️感谢大家点赞👍🏻收藏⭐评论✍🏻,您的三连就是我持续更新的动力❤️ 🙏小杨水平有限,欢迎各位大佬指点&…...
Linux系统常用命令行指令
Linux系统是一种常用于开源项目开发的生产环境,因其免费、开源、安全、稳定的特点被广泛应用于手机、平板电脑、路由器、电视和电子游戏机等嵌入式系统中,能够更加简便地让用户知道系统是怎样工作的。前几日我安装好了Red Hat Enterprise Linux 9.0&…...
java SSM园林绿化管理系统myeclipse开发mysql数据库springMVC模式java编程计算机网页设计
一、源码特点 java SSM园林绿化管理系统是一套完善的web设计系统(系统采用SSM框架进行设计开发,springspringMVCmybatis),对理解JSP java编程开发语言有帮助,系统具有完整的源代 码和数据库,系统主要采…...
【issue-halcon例程学习】edges_color.hdev
例程功能 演示如何使用edges_color,展示只能从彩色图像中提取某些边缘的图像,说明edges_color和edges_image输出之间的差异。 代码如下 dev_update_off () read_image (Image, olympic_stadium) get_image_size (Image, Width, Height) dev_close_wind…...
设计模式—行为型模式之备忘录模式
设计模式—行为型模式之备忘录模式 备忘录(Memento)模式:在不破坏封装性的前提下,捕获一个对象的内部状态,并在该对象之外保存这个状态,以便以后当需要时能将该对象恢复到原先保存的状态。该模式又叫快照模…...
CMS如何调优
业务JVM频繁Full GC如何排查 原则是先止损,再排查。 FGC的原因是对象晋升失败或者并发模式失败,原因都是老年代放不下晋升的对象了。 1.可能是大对象导致的内存泄漏。快速排查方法:观察数据库网络IO是否和FGC时间点吻合,找到对应…...
在PyCharm中安装GitHub Copilot插件,login之后报出如下错误:
Sign in failed. Reason: Request signInInitiate failed with message: connect ECONNABORTED 20.205.243.166:443, request id: 7, error code: -32603 前提: 设置网址:https://github.com/settings/copilot,已设置为允许 或者࿱…...
L1-093 猜帽子游戏(Java)
宝宝们在一起玩一个猜帽子游戏。每人头上被扣了一顶帽子,有的是黑色的,有的是黄色的。每个人可以看到别人头上的帽子,但是看不到自己的。游戏开始后,每个人可以猜自己头上的帽子是什么颜色,或者可以弃权不猜。如果没有…...
JVM篇--JVM调优高频面试题
1 说一下 JVM 调优的工具? JDK 自带了很多监控工具,都位于 JDK 的 bin 目录下,其中最常用的是jconsole 和 jvisualvm 这两款视图监控工具。 jconsole:用于对 JVM 中的内存、线程和类等进行监控; jvisualvm:…...
微软 AD 介绍 | 安全建议 | 防护
介绍: 什么是Active Directory(AD)? Active Directory 是由 微软开发的目录服务,用于存储和管理网络中的资源,如计算机、用户、组和其他网络对象。允许组织管理员轻松地管理和验证网络中的用户和计算机。 …...
React16源码: React中的reconcileChildren的源码实现
reconcileChildren 1 )概述 在更新了一个节点之后,拿到它的props.children要根据这个children里面的 ReactElement 来去创建子树的所有的 fiber 对象要根据 props.children 来生成 fiber 子树,然后判断 fiber 对象它是否是可以复用的 因为我…...
幻兽帕鲁Docker服务端搭建
幻兽帕鲁Docker服务端搭建 各种命令 https://bbs.saraba1st.com/2b/thread-2168983-1-1.html 存档恢复 这里直接看这个工程的readme就行:https://github.com/yoko-murasame/palworld-host-save-fix 其他参考:https://forum.gamer.com.tw/C.php?bsn7…...
【ARM Cortex-M 系列 1.1 -- Cortex-M33 与 M4 差异 详细介绍】
请阅读【嵌入式开发学习必备专栏 之 Cortex-Mx 专栏】 文章目录 背景Cortex-M33 与 M4 差异Cortex-M33Cortex-M4关系和差异举例说明 背景 在移植 RT-Thread 到 瑞萨RA4M2(Cortex-M33)上时,遇到了hardfault 问题,最后使用了Cortex…...
docker 部署及命令
一、容器概述 1、为什么要用到容器? ①容器可以屏蔽底层操作系统的差异性,让业务应用不管在哪里都是使用容器的环境运行,从而保证开发测试环境与生产环境的一致性 ②容器部署起来非常便捷和迅速,缩短开发测试部署的周期时间 2…...
API接口安全总结
接口分类 HTTP接口 RPC接口(客户端和服务器端的连接 例如游戏登陆)非web协议,PRC 远程过程调用 Remote Procedure Call,其就是一个节点请求另外一个节点提供的服务。当两个物理分离的子系统需要建立逻辑上的关联时,R…...
性能优化-HVX 指令介绍
「发表于知乎专栏《移动端算法优化》」 本文主要介绍了 HVX 指令相关的知识,包括 HVX 寄存器相关内容,指令的背景依赖,部分常用 intrinsic HVX 指令。具体指令的详细内容及使用还需阅读 HVX 的指令文档,以及细致的实践操作。 &…...
web安全思维导图(白帽子)
web安全思维导图(白帽子) 客户端脚本安全 服务端应用安全 白帽子讲web安全 安全运营体系建设...
美,英,法,德、意大利和西班牙的geojson,以及区域json
美,英,法,德、意大利和西班牙的geojson文件 json地址 https://pan.baidu.com/s/1nio1bV_j-jAEVqgEHXWsNw?pwdqwer#list/path/GEOJSON 感谢大佬提供的 大佬连接 大佬的知乎原地址 国内geojson获取工具地址 http://dauser: ,toke…...
在Windows虚拟机中挂载IP代理的流程
在虚拟机中挂载IP代理的步骤通常依赖于所使用的虚拟机软件(如VMware、VirtualBox等)以及代理服务器类型(HTTP/HTTPS/SOCKS)。以下是一个通用流程: 在Windows虚拟机中设置网络代理以使用代理IP: 1. SOCKS或H…...
突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果: 块级元素(如 <div>)会占满父容器…...
#Uniapp篇:chrome调试unapp适配
chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器:Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...
【7色560页】职场可视化逻辑图高级数据分析PPT模版
7种色调职场工作汇报PPT,橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版:职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...
Redis:现代应用开发的高效内存数据存储利器
一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发,其初衷是为了满足他自己的一个项目需求,即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源,Redis凭借其简单易用、…...
