LinkedList数据结构链表
LinkedList在Java中是一个实现了List和Deque接口的双向链表。它允许我们在列表的两端添加或删除元素,同时也支持在列表中间插入或移除元素。在分析LinkedList之前,需要理解链表这种数据结构:
- 链表:链表是一种动态数据结构,由一系列节点组成,每个节点包含数据部分和指向列表中下一个节点的引用。
- 双向链表:每个节点都有两个链接,一个指向前一个节点,另一个指向后一个节点。
LinkedList 的数据结构
在LinkedList中,每个元素都是一个节点,每个节点包含三个部分:存储的数据项、指向前一个节点的引用和指向后一个节点的引用。
private static class Node<E> {E item; // 存储的数据Node<E> next; // 指向后一个节点的引用Node<E> prev; // 指向前一个节点的引用Node(Node<E> prev, E element, Node<E> next) {this.item = element;this.next = next;this.prev = prev;}
}
LinkedList 的核心方法
LinkedList实现了List接口,所以它具有诸如add, remove, get, set等方法,同时也实现了Deque接口,这意味着它也具有offer, poll, push, pop等方法。
源码解析(简化版)
以下是LinkedList中一些关键方法的简化版源码:
public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable {transient int size = 0;transient Node<E> first;transient Node<E> last;public LinkedList() {}public boolean add(E e) {linkLast(e);return true;}void linkLast(E e) {final Node<E> l = last;final Node<E> newNode = new Node<>(l, e, null);last = newNode;if (l == null)first = newNode;elsel.next = newNode;size++;modCount++;}public E remove() {return unlinkFirst(first);}private E unlinkFirst(Node<E> f) {final E element = f.item;final Node<E> next = f.next;f.item = null;f.next = null; first = next;if (next == null)last = null;elsenext.prev = null;size--;modCount++;return element;}public E get(int index) {checkElementIndex(index);return node(index).item;}Node<E> node(int index) {if (index < (size >> 1)) {Node<E> x = first;for (int i = 0; i < index; i++)x = x.next;return x;} else {Node<E> x = last;for (int i = size - 1; i > index; i--)x = x.prev;return x;}}// 省略其他细节实现
}
代码演示
下面是LinkedList的一个简单使用示例:
import java.util.LinkedList;public class Main {public static void main(String[] args) {LinkedList<String> friends = new LinkedList<>();// 添加元素friends.add("Alice");friends.add("Bob");friends.add("Charlie");// 打印所有元素System.out.println("Initial LinkedList: " + friends);// 删除第一个元素friends.remove();// 打印删除元素后的列表System.out.println("After removal: " + friends);// 获取特定位置的元素String friend = friends.get(1);System.out.println("Second friend: " + friend);}
}
细节分析
使用LinkedList时,有几个细节需要注意:
- 动态扩展:由于
LinkedList是基于节点的,因此它可以动态地添加或删除节点而不需要像数组那样重新分配整个数据结构。 - 随机访问效率低:获取特定索引的元素时,
LinkedList必须从头开始(或从尾开始,取决于哪边更近)遍历节点。因此,随机访问的效率远低于数组。 - 插入和删除效率高:在任何位置插入或删除元素时,
LinkedList只需要改变几个引用,这使得插入和删除操作非常快速。 - 内存开销:与数组相比,
LinkedList的每个元素都需要额外的内存空间来存储前后节点的引用。
通过以上解析,我们可以深入理解LinkedList的工作原理和设计。这有助于开发者在需要适合的数据结构时作出明智的选择。对于需要频繁插入和删除操作的场景,LinkedList可能是一个不错的选择。然而,如果需要快速通过索引访问元素,那么ArrayList可能是更好的选择。
相关文章:
LinkedList数据结构链表
LinkedList在Java中是一个实现了List和Deque接口的双向链表。它允许我们在列表的两端添加或删除元素,同时也支持在列表中间插入或移除元素。在分析LinkedList之前,需要理解链表这种数据结构: 链表:链表是一种动态数据结构&#x…...
[计算机网络]---序列化和反序列化
前言 作者:小蜗牛向前冲 名言:我可以接受失败,但我不能接受放弃 如果觉的博主的文章还不错的话,还请点赞,收藏,关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正 目录 一、再谈协议…...
[前端开发] 常见的 HTML CSS JavaScript 事件
代码示例指路 常见的 HTML、CSS、JavaScript 事件代码示例 常见的 HTML CSS JavaScript 事件 事件HTML 事件鼠标事件键盘事件表单事件 JavaScript 事件对象事件代理(事件委托) 事件 在 Web 开发中,事件是用户与网页交互的重要方式之一。通过…...
H5/CSS 笔试面试考题(71-80)
简述哪种输入类型用于定义周和年控件(无时区)( ) A:date B:week C:year 面试通过率:67.0% 推荐指数: ★★★★★ 试题难度: 初级 试题类型: 选择题 答案:b 简述下列哪个元素表示外部资源?该元素可以被视为图像、嵌套的浏览上下文或插件要处理的资源。它包括各种属性…...
【Node.js】path 模块进行路径处理
Node.js 执行 JS 代码时,代码中的路径都是以终端所在文件夹出发查找相对路径,而不是以我们认为的从代码本身出发,会遇到问题,所以在 Node.js 要执行的代码中,访问其他文件,建议使用绝对路径 实例࿱…...
react+ts【项目实战一】配置项目/路由/redux
文章目录 1、项目搭建1、创建项目1.2 配置项目1.2.1 更换icon1.2.2 更换项目名称1.2.1 配置项目别名 1.3 代码规范1.3.1 集成editorconfig配置1.3.2 使用prettier工具 1.4 项目结构1.5 对css进行重置1.6 注入router1.7 定义TS组件的规范1.8 创建代码片段1.9 二级路由和懒加载1.…...
英文论文(sci)解读复现【NO.20】TPH-YOLOv5++:增强捕获无人机的目标检测跨层不对称变压器的场景
此前出了目标检测算法改进专栏,但是对于应用于什么场景,需要什么改进方法对应与自己的应用场景有效果,并且多少改进点能发什么水平的文章,为解决大家的困惑,此系列文章旨在给大家解读发表高水平学术期刊中的 SCI论文&a…...
第十五章 以编程方式使用 SQL 网关 - %SQLGatewayConnection 方法和属性
文章目录 第十五章 以编程方式使用 SQL 网关 - %SQLGatewayConnection 方法和属性FetchRows()GatewayStatus propertyGatewayStatusGet()GetConnection()GetGTWVersion()GetLastSQLCode() 第十五章 以编程方式使用 SQL 网关 - %SQLGatewayConnection 方法和属性 FetchRows() …...
【QTableView】
QTableView是Qt框架中用于显示表格形式数据的部件,通常用于显示数据库查询结果、数据集以及其他类似的结构化数据。 以下是一个使用QTableView的简单示例,假设我们有一个数据库表存储了学生的信息,我们可以使用QSqlTableModel将数据库表关联到QTableView上,并显示出来: …...
VS-Code-C#配置
C#开发环境配置 查看更多学习笔记:GitHub:LoveEmiliaForever 1. 安装 .NET SDK 官方下载网址按照安装程序指引安装即可 2. VS Code 安装插件 插件名:C#发布者是Microsoft 该插件是基础语法插件 插件名:C# Dev Kit发布者是Mic…...
第七篇【传奇开心果系列】Python微项目技术点案例示例:数据可视化界面图形化经典案例
传奇开心果微博系列 系列微博目录Python微项目技术点案例示例系列 微博目录一、微项目开发背景和项目目标:二、雏形示例代码三、扩展思路介绍四、数据输入示例代码五、数据分析示例代码六、排名统计示例代码七、数据导入导出示例代码八、主题定制示例代码九、数据过…...
LeetCode 第33天 | 1005. K 次取反后最大化的数组和 135. 分发糖果 134. 加油站
1005. K 次取反后最大化的数组和 按照绝对值大小降序排序,然后将负值变正,如果所有负值都正了,但是还有k余量且为奇数,那就将绝对值最小值(最后一个元素)取反,否则直接结束。 class Solution {…...
PointMixer论文阅读笔记
MLP-mixer是最近很流行的一种网络结构,比起Transformer和CNN的节构笨重,MLP-mixer不仅节构简单,而且在图像识别方面表现优异。但是MLP-mixer在点云识别方面表现欠佳,PointMixer就是在保留了MLP-mixer优点的同时,还可以…...
[word] word分割线在哪里设置 #其他#经验分享
word分割线在哪里设置 在工作中有些技巧,可以快速提高工作效率,解决大部分工作,今天给大家分享word分割线在哪里设置的小技能,希望可以帮助到你。 1、快速输入分割线 输入三个【_】按下回车就是一条长直线,同样分别…...
C++ 音视频原理
本篇文章我们来描述一下音视频原理 音视频录制原理: 下面是对这张思维导图的介绍 摄像头部分: 麦克风采集声音 摄像头采集画面 摄像头采集回来的数据可以用RGB也可以用YUV来表示 图像帧帧率 一秒能处理多少张图像 图像处理 :调亮度 图像帧队列 :意思是将数据取…...
C# 只允许开启一个exe程序
C# 只允许开启一个exe程序 第一种方法 电脑只能启动一次再次点击显示当前exe程序 using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Runtime.InteropServices; using System.Threading.Tasks; using System.Win…...
【Java程序员面试专栏 分布式中间件】Redis 核心面试指引
关于Redis部分的核心知识进行一网打尽,包括Redis的基本概念,基本架构,工作流程,存储机制等,通过一篇文章串联面试重点,并且帮助加强日常基础知识的理解,全局思维导图如下所示 基础概念 明确redis的特性、应用场景和数据结构 什么是Redis,Redis有哪些应用场景 Redi…...
2024年【高处安装、维护、拆除】模拟考试题库及高处安装、维护、拆除实操考试视频
题库来源:安全生产模拟考试一点通公众号小程序 高处安装、维护、拆除模拟考试题库是安全生产模拟考试一点通生成的,高处安装、维护、拆除证模拟考试题库是根据高处安装、维护、拆除最新版教材汇编出高处安装、维护、拆除仿真模拟考试。2024年【高处安装…...
【QT+QGIS跨平台编译】之三十七:【Shapelib+Qt跨平台编译】(一套代码、一套框架,跨平台编译)
文章目录 一、Shapelib介绍二、Shapelib下载三、文件分析四、pro文件五、编译实践一、Shapelib介绍 Shapelib是一个开源的C库,用于读取、写入和操作ESRI Shapefile格式的地理矢量数据。 ESRI Shapefile是一种常见的地理信息系统(GIS)文件格式,用于存储地理矢量数据,包括…...
【机器学习基础】决策树(Decision Tree)
🚀个人主页:为梦而生~ 关注我一起学习吧! 💡专栏:机器学习 欢迎订阅!后面的内容会越来越有意思~ ⭐特别提醒:针对机器学习,特别开始专栏:机器学习python实战 欢迎订阅&am…...
.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...
【2025年】解决Burpsuite抓不到https包的问题
环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)
目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关࿰…...
安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)
船舶制造装配管理现状:装配工作依赖人工经验,装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书,但在实际执行中,工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...
回溯算法学习
一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...
深度学习水论文:mamba+图像增强
🧀当前视觉领域对高效长序列建模需求激增,对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模,以及动态计算优势,在图像质量提升和细节恢复方面有难以替代的作用。 🧀因此短时间内,就有不…...
【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制
使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下,限制某个 IP 的访问频率是非常重要的,可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案,使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...
6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙
Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...
