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

【数据结构与算法】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. 链表

链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中引用链接次序实现的

image-20231216144405243

注意:

  1. 从上图可看出,链表结构正在逻辑上是连续的,但是在物理上(内存)不一定连续。
  2. 现实中的节点一般都是从堆上申请出来的。
  3. 从堆上申请的空间,是按照一定的额策略来分配的,两次申请的空间可能连续,也可能不连续。

实际中链表的结构非常多样,以下情况组合起来就有8种链表结构:

  1. 单向或者双向

    image-20231218085346362

  2. 带头或者不带头

    image-20231218085406993

  3. 循环或者非循环

    image-20231218090427508

    虽然有这么多的链表结构,但是我们重点掌握两种:

    • 无头单向非循环链表:结构简单,一般不会单独用来存放数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。
    • 无头双向链表:在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;}
}

画图表示:

image-20231216155247814

3.1 打印链表

  1. 怎么从第一个节点走到第二个节点?

    答:head = head.next

  2. 什么时候算是把节点都遍历完成?

    答: 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 头插法

在链表的第一个位置插入元素。

思路:

  1. 插入元素的next指向head
  2. head指向插入元素

image-20231216163615979

代码实现:

    /*** 头插法* @param data*/@Overridepublic void addFirst(int data) {ListNode node = new ListNode(data); // 定义一个节点node.next = head;head = node;}

3.3 尾插法

在链表的最后个位置插入元素

思路:

  1. 判断链表中是否有元素。
  2. 如果没有元素,直接添加头结点即可。
  3. 如果有元素,将原链表最后一个元素next指向插入的元素。

image-20231216165016370

代码实现:

	/*** 尾插法* @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 任意位置插入元素

思路:

  1. 判断index是否合法(index < 0 或者 index 大于链表长度),如果不合法则抛出异常。
  2. 判断index 等于0或者index等于链表长度,则使用头插法或尾插法
  3. cur找到index - 1位置
  4. 插入元素的next指向curnext
  5. curnext指向插入的元素

image-20231216180417677

代码实现:

    /*** 在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 删除元素

思路:

  1. 判断链表是否为空,如果为空直接返回
  2. 判断删除元素是否为头节点,如果是则head指向headnext
  3. 定义指针找到要删除节点的前一个节点
  4. 前一个节点的next指向删除节点的next

image-20231216183736354

代码实现:

    /**** @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 删除链表中指定的所有元素

思路:

  1. 判断链表是否为空,如果是空直接返回
  2. 定义指针cur:可能要删除的节点
  3. 定义指针prev:可能要删除的节点的前驱
  4. 判断curval是不是要删除的元素,如果是prevnext指向curnextcur指向curnext;否则prev指向curcur指向curnext
  5. 判断头节点的val是否为的元素,如果是头节点指向头节点的neext

image-20231216210941437

代码实现:

    /*** 删除链表中所有的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.自主实现单链表的增删查改

&#x1f4da;博客主页&#xff1a;爱敲代码的小杨. ✨专栏&#xff1a;《Java SE语法》 ❤️感谢大家点赞&#x1f44d;&#x1f3fb;收藏⭐评论✍&#x1f3fb;&#xff0c;您的三连就是我持续更新的动力❤️ &#x1f64f;小杨水平有限&#xff0c;欢迎各位大佬指点&…...

Linux系统常用命令行指令

Linux系统是一种常用于开源项目开发的生产环境&#xff0c;因其免费、开源、安全、稳定的特点被广泛应用于手机、平板电脑、路由器、电视和电子游戏机等嵌入式系统中&#xff0c;能够更加简便地让用户知道系统是怎样工作的。前几日我安装好了Red Hat Enterprise Linux 9.0&…...

java SSM园林绿化管理系统myeclipse开发mysql数据库springMVC模式java编程计算机网页设计

一、源码特点 java SSM园林绿化管理系统是一套完善的web设计系统&#xff08;系统采用SSM框架进行设计开发&#xff0c;springspringMVCmybatis&#xff09;&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代 码和数据库&#xff0c;系统主要采…...

【issue-halcon例程学习】edges_color.hdev

例程功能 演示如何使用edges_color&#xff0c;展示只能从彩色图像中提取某些边缘的图像&#xff0c;说明edges_color和edges_image输出之间的差异。 代码如下 dev_update_off () read_image (Image, olympic_stadium) get_image_size (Image, Width, Height) dev_close_wind…...

设计模式—行为型模式之备忘录模式

设计模式—行为型模式之备忘录模式 备忘录&#xff08;Memento&#xff09;模式&#xff1a;在不破坏封装性的前提下&#xff0c;捕获一个对象的内部状态&#xff0c;并在该对象之外保存这个状态&#xff0c;以便以后当需要时能将该对象恢复到原先保存的状态。该模式又叫快照模…...

CMS如何调优

业务JVM频繁Full GC如何排查 原则是先止损&#xff0c;再排查。 FGC的原因是对象晋升失败或者并发模式失败&#xff0c;原因都是老年代放不下晋升的对象了。 1.可能是大对象导致的内存泄漏。快速排查方法&#xff1a;观察数据库网络IO是否和FGC时间点吻合&#xff0c;找到对应…...

在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 前提&#xff1a; 设置网址&#xff1a;https://github.com/settings/copilot&#xff0c;已设置为允许 或者&#xff1…...

L1-093 猜帽子游戏(Java)

宝宝们在一起玩一个猜帽子游戏。每人头上被扣了一顶帽子&#xff0c;有的是黑色的&#xff0c;有的是黄色的。每个人可以看到别人头上的帽子&#xff0c;但是看不到自己的。游戏开始后&#xff0c;每个人可以猜自己头上的帽子是什么颜色&#xff0c;或者可以弃权不猜。如果没有…...

JVM篇--JVM调优高频面试题

1 说一下 JVM 调优的工具&#xff1f; JDK 自带了很多监控工具&#xff0c;都位于 JDK 的 bin 目录下&#xff0c;其中最常用的是jconsole 和 jvisualvm 这两款视图监控工具。 jconsole&#xff1a;用于对 JVM 中的内存、线程和类等进行监控&#xff1b; jvisualvm&#xff1a…...

微软 AD 介绍 | 安全建议 | 防护

介绍&#xff1a; 什么是Active Directory&#xff08;AD&#xff09;&#xff1f; Active Directory 是由 微软开发的目录服务&#xff0c;用于存储和管理网络中的资源&#xff0c;如计算机、用户、组和其他网络对象。允许组织管理员轻松地管理和验证网络中的用户和计算机。 …...

React16源码: React中的reconcileChildren的源码实现

reconcileChildren 1 &#xff09;概述 在更新了一个节点之后&#xff0c;拿到它的props.children要根据这个children里面的 ReactElement 来去创建子树的所有的 fiber 对象要根据 props.children 来生成 fiber 子树&#xff0c;然后判断 fiber 对象它是否是可以复用的 因为我…...

幻兽帕鲁Docker服务端搭建

幻兽帕鲁Docker服务端搭建 各种命令 https://bbs.saraba1st.com/2b/thread-2168983-1-1.html 存档恢复 这里直接看这个工程的readme就行&#xff1a;https://github.com/yoko-murasame/palworld-host-save-fix 其他参考&#xff1a;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&#xff08;Cortex-M33&#xff09;上时&#xff0c;遇到了hardfault 问题&#xff0c;最后使用了Cortex…...

docker 部署及命令

一、容器概述 1、为什么要用到容器&#xff1f; ①容器可以屏蔽底层操作系统的差异性&#xff0c;让业务应用不管在哪里都是使用容器的环境运行&#xff0c;从而保证开发测试环境与生产环境的一致性 ②容器部署起来非常便捷和迅速&#xff0c;缩短开发测试部署的周期时间 2…...

API接口安全总结

接口分类 HTTP接口 RPC接口&#xff08;客户端和服务器端的连接 例如游戏登陆&#xff09;非web协议&#xff0c;PRC 远程过程调用 Remote Procedure Call&#xff0c;其就是一个节点请求另外一个节点提供的服务。当两个物理分离的子系统需要建立逻辑上的关联时&#xff0c;R…...

性能优化-HVX 指令介绍

「发表于知乎专栏《移动端算法优化》」 本文主要介绍了 HVX 指令相关的知识&#xff0c;包括 HVX 寄存器相关内容&#xff0c;指令的背景依赖&#xff0c;部分常用 intrinsic HVX 指令。具体指令的详细内容及使用还需阅读 HVX 的指令文档&#xff0c;以及细致的实践操作。 &…...

web安全思维导图(白帽子)

web安全思维导图(白帽子) 客户端脚本安全 服务端应用安全 白帽子讲web安全 安全运营体系建设...

美,英,法,德、意大利和西班牙的geojson,以及区域json

美&#xff0c;英&#xff0c;法&#xff0c;德、意大利和西班牙的geojson文件 json地址 https://pan.baidu.com/s/1nio1bV_j-jAEVqgEHXWsNw?pwdqwer#list/path/GEOJSON 感谢大佬提供的 大佬连接 大佬的知乎原地址 国内geojson获取工具地址 http://da![在这里插入图片描述](h…...

JavaEE-微服务-Vuex

Vuex 2.1 什么是Vuex Vuex 是一个专为 Vue.js 应用程序开发的状态管理模式。 Vuex在组件之间共享数据。 2.2 使用 vue cli 构建项目 2.3 入门案例 2.3.1 定义数据 export default new Vuex.Store({state: { // 状态区域&#xff08;定义变量区域&#xff09;user: ,toke…...

在Windows虚拟机中挂载IP代理的流程

在虚拟机中挂载IP代理的步骤通常依赖于所使用的虚拟机软件&#xff08;如VMware、VirtualBox等&#xff09;以及代理服务器类型&#xff08;HTTP/HTTPS/SOCKS&#xff09;。以下是一个通用流程&#xff1a; 在Windows虚拟机中设置网络代理以使用代理IP&#xff1a; 1. SOCKS或H…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...

「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案

在移动互联网营销竞争白热化的当下&#xff0c;推客小程序系统凭借其裂变传播、精准营销等特性&#xff0c;成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径&#xff0c;助力开发者打造具有市场竞争力的营销工具。​ 一、系统核心功能架构&…...

Ubuntu系统复制(U盘-电脑硬盘)

所需环境 电脑自带硬盘&#xff1a;1块 (1T) U盘1&#xff1a;Ubuntu系统引导盘&#xff08;用于“U盘2”复制到“电脑自带硬盘”&#xff09; U盘2&#xff1a;Ubuntu系统盘&#xff08;1T&#xff0c;用于被复制&#xff09; &#xff01;&#xff01;&#xff01;建议“电脑…...

在golang中如何将已安装的依赖降级处理,比如:将 go-ansible/v2@v2.2.0 更换为 go-ansible/@v1.1.7

在 Go 项目中降级 go-ansible 从 v2.2.0 到 v1.1.7 具体步骤&#xff1a; 第一步&#xff1a; 修改 go.mod 文件 // 原 v2 版本声明 require github.com/apenella/go-ansible/v2 v2.2.0 替换为&#xff1a; // 改为 v…...

游戏开发中常见的战斗数值英文缩写对照表

游戏开发中常见的战斗数值英文缩写对照表 基础属性&#xff08;Basic Attributes&#xff09; 缩写英文全称中文释义常见使用场景HPHit Points / Health Points生命值角色生存状态MPMana Points / Magic Points魔法值技能释放资源SPStamina Points体力值动作消耗资源APAction…...