【数据结构】 链表简介与单链表的实现
文章目录
- ArrayList的缺陷
- 链表
- 链表的概念及结构
- 链表的分类
- 单向或者双向
- 带头或者不带头
- 循环或者非循环
- 单链表的实现
- 创建单链表
- 遍历链表
- 得到单链表的长度
- 查找是否包含关键字
- 头插法
- 尾插法
- 任意位置插入
- 删除第一次出现关键字为key的节点
- 删除所有值为key的节点
- 回收链表
- 总结
ArrayList的缺陷
在【数据结构】 ArrayList简介与实战中我们已经熟悉了ArrayList的使用,并且进行了简单模拟实现。通过源码知道,ArrayList底层使用数组来存储元素
由于其底层是一段连续空间,当在ArrayList任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后搬移,时间复杂度为O(n),效率比较低,因此ArrayList不适合做任意位置插入和删除比较多的场景。 因此:java集合中又引入了LinkedList,即链表结构。
链表
链表的概念及结构
链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的
就如同火车中间通过链条链接的一个道理
链表的大概结构如下所示:
链表的每一节都含有相应的数据与下一节的地址,一般我们会记录起始节点,可以用来我们访问该链表,最后一个节点不含有下一节点的地址,置为null;
链表的分类
实际中链表的结构非常多样,以下情况组合起来就有8种链表结构:
单向或者双向
带头或者不带头
循环或者非循环
虽然有这么多的链表的结构,但是我们重点掌握两种:
- 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多
- 无头双向链表:在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。
单链表的实现
接下来我们来实现一个无头单向非循环链表实现,并实现一些相应的功能
创建单链表
博主在这里创建一个类为MyLinkedList类,我们将在这里面实现我们的无头单向非循环链表
创建单链表其实很简单,我们需要建立一个类,类里面放你需要放的数据元素,以及该类类型的元素,用于储存下一节点的地址
然后我们还需要一个变量来记录其实节点,在这里我们用一个内部类在MyLinkedList类进行表示,并在createLink方法里进行各个节点的创建并赋值,然后将这些节点链接起来
代码实现如下
public class MyLinkedList {class Node {public int val;public Node next;public Node(int val) {this.val = val;}}public Node head;// 代表当前链表的头节点的引用public void createLink() {Node node1 = new Node(11);Node node2 = new Node(22);Node node3 = new Node(33);Node node4 = new Node(44);node1.next = node2;node2.next = node3;node3.next = node4; /* */head = node1;}
}
遍历链表
写好的链表,我们来进行打印一下看看是否创建成功
我们的head为我们的头节点,也就是我们遍历的起点,但是由于该单链表是单向的,如果使用头节点进行遍历的话,会导致后面找不到头节点,所以我们这里重新创建一个变量进行遍历。
由于每一节点里的next里面都存储着我们下一节点的地址,所以当我们访问完当前节点的元素后,将当前节点的next赋给我们所创建的遍历变量即可;
由于最后一个节点里next里面为null,所以我们将它作为结束条件
代码实现如下
public void disPlay() {Node sur = head;while(sur != null) {System.out.print(sur.val+" ");sur = sur.next;}}
得到单链表的长度
进行遍历,并用一个数进行记录,最后进行返回就行
代码实现如下
public int size(){int count = 0;Node cur = head;while (cur != null) {count++;cur = cur.next;}return count;}
查找是否包含关键字
我们只需要对该链表进行遍历,然后一一比对就好,大致实现过程与遍历链表相同
代码实现如下
//查找是否包含关键字key是否在单链表当中public boolean contains(int key){Node cur = head;while (cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;}
头插法
将第一个节点赋给我们新添加的节点里面的next
并且将新添加的节点赋给head,作为新的头节点
代码实现如下
public void addFirst(int data){Node node = new Node(data);node.next = head;head = node;}
注意:一定要注意赋值的顺序
尾插法
我们首先对该链表进行遍历,当遍历到最后一个节点时
将最后一个节点里的next赋为我们新增的节点即可。
如果该链表为空,直接将该新增节点设为头节点就好
代码实现如下
public void addLast(int data){Node node = new Node(data);if(head == null) {head = node;return;}Node cur = head;while (cur.next != null) {cur = cur.next;}cur.next = node;}
任意位置插入
首先我们需要对需要插入的位置进行遍历,必须为合法,如果不合法,我们会抛出一个异常进行提醒,这里我们自定义了一个异常如下
public class ListIndexOutOfException extends RuntimeException{public ListIndexOutOfException() {}public ListIndexOutOfException(String message) {super(message);}
}
任意位置插入,我们可以分为种情况
- 插在开头
- 插在结尾
- 插在中间
前两种我们已经实现了,我们现在只需要实现插在中间就好
我们对该单链表进行编号,第一个节点为我们的0下标。我们需要遍历单链表,找到所需要插入下标的前一个节点
将该节点的next设为我们新增的节点,将新增节点里面的next设为下一节点
代码实现如下
//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data)throws ListIndexOutOfException{checkIndex(index);if(index == 0) {addFirst(data);return;}if(index == size()) {addLast(data);return;}Node cur = findIndexSubOne(index);Node node = new Node(data);node.next = cur.next;cur.next = node;}/*** 找到 index-1位置的节点的地址* @param index* @return*/private Node findIndexSubOne(int index) {Node cur = head;int count = 0;while (count != index-1) {cur = cur.next;count++;}return cur;}private void checkIndex(int index) throws ListIndexOutOfException{if(index < 0 || index > size()) {throw new ListIndexOutOfException("index位置不合法");}}
删除第一次出现关键字为key的节点
分为四种情况
- 一个节点都没有
- 删除数据在第一个
- 没有你要删除的数据
- 有你要删除的数据且不是第一个
第一种情况判断是否为空后直接返回就好
第二种情况直接将头节点置为下一节点,也就时head=head.next;
第三种情况遍历单链表后,返回就好
第四种情况,找到所需要删除数据的前一节点,将所需要删除数据的前一节点的next设为当前需要删除数据节点的next
代码实现如下
//删除第一次出现关键字为key的节点 O(N)public void remove(int key){if(head == null) {return ;//一个节点都没有}if(head.val == key) {head = head.next;return;}Node cur = searchPrev(key);if(cur == null) {return;}Node del = cur.next;//要删除的节点cur.next = del.next;}/*** 找到关键字key的前一个节点* @param key* @return*/private Node searchPrev(int key) {Node cur = head;while (cur.next != null) {if(cur.next.val == key) {return cur;}cur = cur.next;}return null;//没有你要删除的节点}
删除所有值为key的节点
我们依旧需要对该单链表进行判断,如果为空,就直接返回
由于我们需要删除很多个这样的节点,但是我们的单链表却是单向的,按照上面的写法,我们则需要遍历很多次单链表,大大的增加了复杂度,我们为了降低时间复杂度,使它降为O(N);
我们设两个遍历节点,进行遍历,一个在前为cur,一个在后prev
前面的cur负责进行遍历删除,后面的prev负责跟在cur后面记录cur的上一节点
当cur下一节点不是我们所要删除的元素时,这时候我们将prev变为我们当前节点的cur,而cur变为当前节点的next
当前的删除方法只能删除第一个节点以后的元素,所以我们还需要处理第一个元素是我们所需要删除的情况。
代码实现如下
//删除所有值为key的节点public void removeAllKey(int key){if(head == null) {return;}Node prev = head;Node 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;}}
回收链表
将头节点置为空就好。
代码实现如下
public void clear() {head = null;}
总结
关于《【数据结构】 链表简介与单链表的实现》就讲解到这儿,感谢大家的支持,欢迎各位留言交流以及批评指正,如果文章对您有帮助或者觉得作者写的还不错可以点一下关注,点赞,收藏支持一下!
相关文章:

【数据结构】 链表简介与单链表的实现
文章目录 ArrayList的缺陷链表链表的概念及结构链表的分类单向或者双向带头或者不带头循环或者非循环 单链表的实现创建单链表遍历链表得到单链表的长度查找是否包含关键字头插法尾插法任意位置插入删除第一次出现关键字为key的节点删除所有值为key的节点回收链表 总结 ArrayLi…...

【Leetcode】98. 验证二叉搜索树
一、题目 1、题目描述 给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下: 节点的左子树只包含 小于 当前节点的数。节点的右子树只包含 大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。示例1: 输入:root = …...

ViewFs And Federation On HDFS
序言 ViewFs 是在Federation的基础上提出的,用于通过一个HDFS路径来访问多个NameSpace,同时与ViewFs搭配的技术是client-side mount table(这个就是具体的规则配置信息可以放置在core.xml中,也可以放置在mountTable.xml中). 总的来说ViewFs的其实就是一个中间层,用于去连接不…...
每日一学——无线基础知识
无线局域网(Wireless Local Area Network,简称 WLAN)是一种使用无线通信技术连接多个无线终端设备的局域网。它通常基于无线电波传输数据,并使用无线接入点(Access Point,简称 AP)来连接无线设备…...

【腾讯云 Cloud Studio 实战训练营】在线 IDE 编写 canvas 转换黑白风格头像
关于 Cloud Studio Cloud Studio 是基于浏览器的集成式开发环境(IDE),为开发者提供了一个永不间断的云端工作站。用户在使用Cloud Studio 时无需安装,随时随地打开浏览器就能在线编程。 Cloud Studio 作为在线IDE,包含代码高亮、自动补全、Gi…...

【Hystrix技术指南】(7)故障切换的运作流程原理分析(含源码)
背景介绍 目前对于一些非核心操作,如增减库存后保存操作日志发送异步消息时(具体业务流程),一旦出现MQ服务异常时,会导致接口响应超时,因此可以考虑对非核心操作引入服务降级、服务隔离。 Hystrix说明 官方…...

Springboot 整合MQ实现延时队列入门
延时队列 添加依赖配置文件队列TTL代码架构图交换机、队列、绑定配置文件代码生产者代码消费者代码延时队列优化添加普通队列配置代码生产者发送消息是进行设置消息的ttl 通过MQ 插件实现延时队列代码架构图配置交换机生产者代码消费者代码测试发送 添加依赖 <!-- rabbitMQ …...

前端基础(Vue框架)
前言:前端开发框架——Vue框架学习。 准备工作:添加Vue devtools扩展工具 具体可查看下面的这篇博客 添加vue devtools扩展工具添加后F12不显示Vue图标_MRJJ_9的博客-CSDN博客 Vue官方学习文档 Vue.js - 渐进式 JavaScript 框架 | Vue.js 目录 MV…...

【实用插件】ArcGIS for AutoCAD插件分享下载
ArcGIS包含一系列功能,其中ArcGIS for AutoCAD一个免费的可下载的AutoCAD插件,它可简化将CAD和GIS数据整合在一起的过程提供互操作性。 ArcGIS for AutoCAD互操作性平台将连接AutoCAD和 ArcGIS,以增强使用地理环境设计CAD工程图时的用户体验…...

GaussDB数据库SQL系列-子查询
目录 一、前言 二、GaussDB SQL子查询表达式 1、EXISTS/NOT EXISTS 2、IN/NOT IN 3、ANY/SOME 4、ALL 三、GaussDB SQL子查询实验示例 1、创建实验表 2、EXISTS/NOT EXISTS示例 3、IN/NOT IN 示例 4、ANY/SOME 示例 5、ALL示例 四、注意事项及建议 五、小结 一、…...

Kafka 什么速度那么快
批量发送消息 Kafka 采用了批量发送消息的方式,通过将多条消息按照分区进行分组,然后每次发送一个消息集合,看似很平常的一个手段,其实它大大提升了 Kafka 的吞吐量。 消息压缩 消息压缩的目的是为了进一步减少网络传输带宽。而…...

环形链表笔记(自用)
环形链表 不管怎么样slow最多走半圈了, 快慢指针slow走一步,fast走两步最合适,因为假设fast和slow相差n每一次他们前进,就会相差n-1步,这样他们一定会相遇,如果是环形链表的话。 代码 /*** Definition for…...
js循环中发起请求数据不一致问题
项目场景: 在公司的一个项目中需要使用循环更改查询条件,然后查询子表数据,但是在查询过程中for下面的key变化了之后,查询中的key却并没有变化,导致查询的参数不一致,从未结果数据出错 for(let i 0;i<…...
工作流自动化:提升效率、节约成本的重要工具
在现代社会中,软件和技术的运用使得我们的日常活动变得更加简单和高效。然而,这些技术也有自身的特点和独特之处。尽管我们使用这些工具来简化工作,但有时仍需要一些人工干预,比如手动数据录入。在工作场所中,手动数据…...

仿牛客论坛项目day7|Kafka
一、阻塞队列 创建了一个生产者线程和一个消费者线程。生产者线程向队列中放入元素,消费者线程从队列中取出元素。我们可以看到,当队列为空时,消费者线程会被阻塞,直到生产者线程向队列中放入新的元素。 二、Kafka入门 发布、订阅…...
[SpringCloud] 组件性能优化技巧
Feign 配置优化hystrix配置 优化ribbon 优化Servlet 容器 优化Zuul配置 优化 文章目录 1.Servlet 容器 优化2.Feign 配置优化3.Zuul配置 优化4.hystrix配置 优化5.ribbon 优化 1.Servlet 容器 优化 默认情况下, Spring Boot 使用 Tomcat 来作为内嵌的 Servlet 容器, 可以将 We…...
okhttp下载文件 Java下载文件 javaokhttp下载文件 下载文件 java下载 okhttp下载 okhttp
okhttp下载文件 Java下载文件 javaokhttp下载文件 下载文件 java下载 okhttp下载 okhttp 1、引入Maven1.1、okhttp发起请求官网Demo 2、下载文件3、扩充,读写 txt文件内容3.1读写内容 示例 http客户端 用的是 okhttp,也可以用 UrlConnetcion或者apache …...
Oracle/PL/SQL奇技淫巧之Json转表
在Oracle中,有些时候我们需要在一个json文档中查数据 这个时候我们可以通过JSON_TABLE函数来把 json文档 提取成一张可以执行正常查询操作的表 先看JSON_TABLE函数的基础用法: JSON_TABLE(json_data, $.json_path COLUMNS (column_definitions))其中&a…...
每日一学——网络安全
网络安全设计、原则、审计等知识点的精讲如下: 网络安全设计与原则: 网络安全设计是指在系统或网络的设计过程中考虑到安全性,并采取相应的安全措施来保护系统或网络不受威胁。安全设计原则包括最小权限原则(Least Privilege Prin…...
python中的lstm:介绍和基本使用方法
python中的lstm:介绍和基本使用方法 未使用插件 LSTM(Long Short-Term Memory)是一种循环神经网络(RNN)的变体,专门用于处理序列数据。LSTM 可以记忆序列中的长期依赖关系,这使得它非常适合于各…...

龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...

【Oracle APEX开发小技巧12】
有如下需求: 有一个问题反馈页面,要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据,方便管理员及时处理反馈。 我的方法:直接将逻辑写在SQL中,这样可以直接在页面展示 完整代码: SELECTSF.FE…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享
文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的,根据Excel列的需求预估的工时直接打骨折,不要问我为什么,主要…...

如何在看板中有效管理突发紧急任务
在看板中有效管理突发紧急任务需要:设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP(Work-in-Progress)弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中,设立专门的紧急任务通道尤为重要,这能…...

高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成
厌倦手动写WordPress文章?AI自动生成,效率提升10倍! 支持多语言、自动配图、定时发布,让内容创作更轻松! AI内容生成 → 不想每天写文章?AI一键生成高质量内容!多语言支持 → 跨境电商必备&am…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...

dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...