JDK源码解析:LinkedList
1、背景
我们咨询一下腾讯混元大模型,什么是“LinkedList”。
以下是混元大模型的回答:
LinkedList 是 Java 集合框架中的一种数据结构,它实现了 List 和 Deque 接口。LinkedList 是一个双向链表,这意味着每个元素都包含对前一个和后一个元素的引用。
这种数据结构允许在列表的两端进行高效的插入和删除操作。
LinkedList 的主要特点:
动态大小:与数组不同,
LinkedList
的大小可以动态增长或缩小。高效的插入和删除:在
LinkedList
的开头、结尾或中间插入或删除元素时,不需要移动其他元素,因此这些操作通常比在ArrayList
中执行得更快。内存效率:由于不需要连续的内存空间来存储元素,
LinkedList
在内存使用上可能比ArrayList
更有效。访问速度:与
ArrayList
相比,LinkedList
的随机访问速度较慢,因为需要从头部或尾部开始遍历链表才能找到特定位置的元素。线程不安全:
LinkedList
不是线程安全的。如果多个线程同时修改LinkedList
,可能会导致数据不一致。在多线程环境中,可以使用Collections.synchronizedList()
方法将LinkedList
包装成线程安全的列表,或者使用CopyOnWriteArrayList
(尽管它更适合读多写少的场景)。
2、源码分析
2.1类定义
public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{}
源码分析:
LinkedList
继承了AbstractSequentialListAbstractSequentialList
是 Java 集合框架中的一个抽象类,它实现了List
接口并提供了一个顺序访问列表元素的迭代器。AbstractSequentialList
为那些希望以顺序方式访问其元素的列表提供了一个通用的基础实现。
LinkedList
实现了List接口:具备线性表的操作,如:size、isEmpty、contains、containsAll
add、addAll、removeAll、retainAll、clear、subList
LinkedList
实现了Deque接口:具备双向链表的操作,如:addFirst、removeFirst、pollFirst、getFirst、peekFirst
addLast、removeLast、pollLast、getLast、peekLast
2.2基本属性
transient int size = 0;/*** Pointer to first node.*/
transient Node<E> first;/*** Pointer to last node.*/
transient Node<E> last;/** 修改次数 */
protected transient int modCount = 0;
源码分析:
LinkedList
内置了两个指针,包括头结点first和末尾指针lastLinkedList
也设置了size,标识有效元素数量(不包括头结点和末尾指针)LinkedList
设置了modCount,标识修改操作次数,modCount
字段用于跟踪列表的结构修改次数,以确保在迭代过程中发生并发修改时能够快速失败,会直接触发异常ConcurrentModificationException
2.3 基本操作:增删改查
(1)增加元素
通过阅读源码,LinkedList
有7种添加元素方法,
add(E e)
:在列表的末尾添加一个元素(默认在列表的末尾添加,即尾插法)add(int index, E element)
:在指定位置插入一个元素。addFirst(E e)
:在列表的开头添加一个元素。addLast(E e)
:在列表的末尾添加一个元素(与add(E e)
相同)。push(E e)
:在列表的开头添加一个元素(与addFirst(E e)
相同)。addAll
的两个重载方法:则是批量插入元素
解析 add(E e)
方法源码
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++;
}Node(Node<E> prev, E element, Node<E> next) {this.item = element;this.next = next;this.prev = prev;
}
源码分析:
linkLast(e):尾插法
新建Node节点:前继指针指向last,当前数据为e,后继指针为null
容量size+1,修改次数+1
(2)删除元素
解析remove()方法源码
源码分析:
public E remove() {return removeFirst();
}public E removeFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return unlinkFirst(f);
}private E unlinkFirst(Node<E> f) {// assert f == first && f != null;final E element = f.item;// 【1】final Node<E> next = f.next;// 【2】f.item = null;// 【3】f.next = null; // help GC// 【4】first = next;// 【5】if (next == null)last = null;else// 【6】next.prev = null;// 【7】size--;modCount++;// 【8】return element;
}
源码解析:
中间变量:next局部变量 承载被删节点的next指针(下个元素地址)
设置被删节点的item数值为null
设置被删节点的next指针为null
设置first指针为next局部变量 (下个元素地址)
如果next局部变量为null,说明没有元素了,顺带设置last为null
否则设置next局部变量 的前继指针为null,因为此后next局部变量 的元素为头结点了
容量-1,操作次数+1
返回被删数据
(3)修改元素
更新set()方法源码
public E set(int index, E element) {// 【1】checkElementIndex(index);// 【2】Node<E> x = node(index);// 【3】E oldVal = x.item;// 【4】x.item = element;// 【5】return oldVal;
}Node<E> node(int index) {// assert isElementIndex(index);// 【2.1】右移位运算,size/2if (index < (size >> 1)) {// 【2.2】Node<E> x = first;// 【2.3】从头部进行遍历for (int i = 0; i < index; i++)// 【2.4】x = x.next;// 【2.5】return x;} else {// 【2.6】从尾部进行遍历Node<E> x = last;for (int i = size - 1; i > index; i--)// 【2.7】x = x.prev;// 【2.8】return x;}
}private void checkElementIndex(int index) {if (!isElementIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}private boolean isElementIndex(int index) {return index >= 0 && index < size;
}
源码分析:
检查元素是否合法,不合法抛出异常IndexOutOfBoundsException
通过遍历链表,得到元素地址
计算要更新的索引下标,离first更近,还是离last更近
离first更近,从头部开始遍历,for循环遍历,得到前一个元素的next指向的元素地址
离last更近,从尾部开始遍历,for循环遍历,得到后一个元素的prev指向的元素地址
获取更新前数值
更新新数值
返回更新前数值
(4)获取元素
获取某个索引下标get()方法源码
public E get(int index) {// 【1】checkElementIndex(index);// 【2】return node(index).item;
}private void checkElementIndex(int index) {if (!isElementIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}Node<E> node(int index) {// assert isElementIndex(index);// 【2.1】右移位运算,size/2if (index < (size >> 1)) {// 【2.2】Node<E> x = first;// 【2.3】从头部进行遍历for (int i = 0; i < index; i++)// 【2.4】x = x.next;// 【2.5】return x;} else {// 【2.6】从尾部进行遍历Node<E> x = last;for (int i = size - 1; i > index; i--)// 【2.7】x = x.prev;// 【2.8】return x;}
}
源码解析:
(会发现,其实获取元素的逻辑,就是修改元素的前置操作)
检查元素是否合法,不合法抛出异常IndexOutOfBoundsException
通过遍历链表,得到元素地址
计算要更新的索引下标,离first更近,还是离last更近
离first更近,从头部开始遍历,for循环遍历,得到前一个元素的next指向的元素地址
离last更近,从尾部开始遍历,for循环遍历,得到后一个元素的prev指向的元素地址
3、总结
LinkedList 是一个双向链表,这意味着每个元素都包含对前一个和后一个元素的引用。这种数据结构允许在列表的两端进行高效的插入和删除操作。
3.1 ArrayList和LinkedList比较
ArrayList底层基于动态数组实现,LinkedList底层基于链表实现
对于随机访问(get/set方法),ArrayList通过index直接定位到数组对应位置的节点,而LinkedList需要从头结点或尾节点开始遍历,直到寻找到目标节点,因此在效率上ArrayList优于LinkedList
对于插入和删除(add/remove方法),ArrayList需要移动目标节点后面的节点(使用System.arraycopy方法移动节点),而LinkedList只需修改目标节点前后节点的next或prev属性即可,因此在效率上LinkedList优于ArrayList。
相关文章:
JDK源码解析:LinkedList
1、背景 我们咨询一下腾讯混元大模型,什么是“LinkedList”。 以下是混元大模型的回答: LinkedList 是 Java 集合框架中的一种数据结构,它实现了 List 和 Deque 接口。LinkedList 是一个双向链表,这意味着每个元素都包含对前一个和…...
drawio的问题
drawio的问题 先给出drawio的链接https://app.diagrams.net/ 我在用overleaf写论文的过程中,发现了一个问题,就是使用drawio画好图之后,只能保存以下几个选项: 但是不管是什么类型,在overleaf上面图片都不显示。如果…...
零基础学习Redis(3) -- Redis常用命令
Redis是一个 客户端-服务器 结构的程序,Redis客户端和服务器可以在同一台主机上,也可以在不同主机上,客户端和服务器之间通过网络进行通信。服务器端负责存储和管理数据。客户端则可以通过命名对服务端的数据进行操作。 Redis客户端有多种&a…...
响应式Web设计:纯HTML和CSS的实现技巧-1
响应式Web设计(Responsive Web Design, RWD)是一种旨在确保网站在不同设备和屏幕尺寸下都能良好运行的网页设计策略。通过纯HTML和CSS实现响应式设计,主要依赖于媒体查询(Media Queries)、灵活的布局、可伸缩的图片和字…...
FrereRTOS事件组
文章目录 一、事件组概念与操作1、事件组的概念2、事件组的操作 二、事件组函数1、创建2、删除3、设置事件4、等待事件5、同步点 三、示例:广播四、示例:等待一个任意事件五、示例: 等待多个事件都发生 学校组织秋游,组长在等待: …...
【经典算法】BFS_最短路问题
目录 1. 最短路问题介绍2. 算法原理和代码实现(含题目链接)1926.迷宫中离入口最近的出口433.最小基因变化127.单词接龙675.为高尔夫比赛砍树 3. 算法总结 1. 最短路问题介绍 最短路径问题是图论中的一类十分重要的问题。本篇文章只介绍边权为1(或边权相同)的最简单的最短路径问…...
【题目/训练】:双指针
引言 我们已经在这篇博客【算法/学习】双指针-CSDN博客里面讲了双指针、二分等的相关知识。 现在我们来做一些训练吧 经典例题 1. 移动零 思路: 使用 0 当做这个中间点,把不等于 0(注意题目没说不能有负数)的放到中间点的左边,等于 0 的…...
LLVM - 编译器后端-指令选择
一:概述 任何后端的核心都是指令选择。LLVM 实现了几种方法;在本篇文章中,我们将通过选择有向无环图(DAG)和全局指令选择来实现指令选择。 在本篇文章中,我们将学习以下主题: • 定义调…...
ES+FileBeat+Kibana日志采集搭建体验
1.环境准备 需要linux操作系统,并安装了docker环境 此处使用虚拟机演示。(虚拟机和docker看参考我之前写的文章) VirtualBox安装Oracle Linux 7.9全流程-CSDN博客 VirtualBox上的Oracle Linux虚拟机安装Docker全流程-CSDN博客 简单演示搭建ES…...
Dockerfile常用指令详解
Dockerfile 是一个用于定义 Docker 镜像构建过程的脚本文件,其中包含了一系列指令,用于指定如何构建和配置镜像。以下是一些常用的 Dockerfile 指令及其示例用法: 1. FROM 指定基础镜像,Dockerfile 必须以该指令开始。 示例&am…...
【vue】浏览器兼容相关
Vue.js 是一个流行的前端 JavaScript 框架,它支持构建单页应用和复杂的用户界面。Vue.js 的核心库本身对浏览器的支持情况如下: Vue.js 2.x 最低支持版本:IE9 及以上版本。特性支持:ES5。兼容性:Vue 2.x 在发布时就考…...
【区块链+金融服务】基于区块链的区域股权金融综合服务平台 | FISCO BCOS应用案例
区域性股权市场是我国资本市场的重要组成部分,是多层次资本市场体系的基石。区块链技术与区域性股权市场 分散特征天然匹配,从新型金融基础设施层面为场外参与各方提供公共的可信服务,以技术手段完善市场基础条 件,弥补区域性短板…...
string字符串和json对象相互转换问题
//响应体String responseStr EntityUtils.toString(response.getEntity());log.debug("下单响应码:{},响应体:{}",statusCode,responseStr);if(statusCode HttpStatus.OK.value()){JSONObject jsonObject JSONObject.parseObject(responseStr);if(jsonObject.cont…...
【生成式人工智能-十一一个不修改模型就能加速语言模型生成的方法】
一个加速语言模型生成的方法 现在语言模型的一个弊端speculative decoding预言家预测的问题 speculative decoding 模块的实现方法NAT Non-autoregressive模型压缩使用搜索引擎 一些更复杂些的speculative decoding 实现方式 speculative decoding 是一个适用于目前生成模型的加…...
Rust 错误处理
Rust 错误处理 Rust 是一种系统编程语言,以其内存安全、高并发和实用性而著称。在 Rust 中,错误处理是一个核心概念,它通过提供 Result 和 Option 类型来鼓励开发者显式地处理可能出现的错误,而不是依赖异常机制。本文将深入探讨 Rust 中的错误处理机制,包括 Result 和 O…...
程序与进程 linux系统
程序与进程 程序 ( program ): 通常为 binary program ,放置在储存媒体中(如硬盘、光盘、软盘、磁带等), 为实体文件的型态存在;二进制文件,比如静态 /bin/date…...
使用MongoDB构建AI:Story Tools Studio将生成式AI引入Myth Maker AI游戏
Story Tools Studio利用先进的生成式AI技术,打造沉浸式、个性化、无穷尽的情景体验。 Story Tools Studio创始人兼首席执行官Roy Altman表示:“我们的旗舰游戏Myth Maker AI采用的是我们自主研发的、以AI为驱动的专家指导型故事生成器MUSE,它…...
鸿蒙UIAbility组件概述(二)
鸿蒙UIAbility组件概述 UIAbility组件基本用法指定UIAbility的启动页面获取UIAbility的上下文信息 UIAbility组件与UI的数据同步使用EventHub进行数据通信使用AppStorage/LocalStorage进行数据同步 UIAbility组件间交互(设备内)启动应用内的UIAbility启动…...
Oracle(70)如何优化SQL查询?
优化SQL查询是数据库管理的重要部分,旨在提高查询性能,减少响应时间和资源消耗。以下是一些常见的SQL查询优化技术,结合代码示例详细说明。 1. 使用索引 索引是优化查询性能的最常见方法之一。索引可以显著减少数据检索的时间。 示例 假设…...
深度剖析:Jenkins构建任务无法中断的原因及解决方案
个人名片 🎓作者简介:java领域优质创作者 🌐个人主页:码农阿豪 📞工作室:新空间代码工作室(提供各种软件服务) 💌个人邮箱:[2435024119qq.com] 📱…...
【YOLO】常用脚本
目录 VOC转YOLO划分训练集、测试集与验证集 VOC转YOLO import os import xml.etree.ElementTree as ETdef convert(size, box):dw 1. / size[0]dh 1. / size[1]x (box[0] box[1]) / 2.0y (box[2] box[3]) / 2.0w box[1] - box[0]h box[3] - box[2]x x * dww w * dwy…...
Springboot IOC DI理解及实现+JUnit的引入+参数配置
一、JavaConfig 我们通常使用 Spring 都会使用 XML 配置,随着功能以及业务逻辑的日益复杂,应用伴随着大量的 XML 配置文件以及复杂的 bean 依赖关系,使用起来很不方便。 在 Spring 3.0 开始,Spring 官方就已经开始推荐使用 Java…...
CeresPCL 最小二乘插值(曲线拟合)
一、简介 在多项式插值时,当数据点个数较多时,插值会导致多项式曲线阶数过高,带来不稳定因素。因此我们可以通过固定幂基函数的最高次数 m(m < n),来对我们要拟合的曲线进行降阶。之前的函数形式就可以变为: 既然是最小二乘问题,那么就仍然可以使用Ceres来进行求解。 …...
【TCP/IP】自定义应用层协议,常见端口号
互联网中,主流的是 TCP/IP 五层协议 5G/4G 上网,是有自己的协议栈,要比 TCP/IP 更复杂(能够把 TCP/IP 的一部分内容给包含进去了) 应用层 可以代表我们所编写的应用程序,只要应用程序里面用到了网络通信…...
Frida 的下载和安装
首先要安装好 python 环境 安装 frida 和 工具包 pip install frida frida-tools 查看版本: frida --version 16.4.8 然后到 github 上下载对应 server ( 和frida 的版本一致 16.4.8) Releases frida/frida (github.com) 查看手机或…...
后端开发刷题 | 链表内指定区间反转【链表篇】
描述 将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转,要求时间复杂度 O(n)O(n),空间复杂度 O(1)O(1)。 例如: 给出的链表为 1→2→3→4→5→NULL1→2→3→4→5→NULL, m2,n4 返回 1→4→3→2→5→NULL 数据范围: 链表…...
【NVMe系列-提问页与文章总结页面】
NVMe系列-提问页与文章总结页面 问题汇总NVMe协议是什么?PRP 与 PRP List是做什么的? 已写文章汇总 问题汇总 NVMe协议是什么? PRP 与 PRP List是做什么的? 已写文章汇总...
用生成器函数生成表单各字段
生成器函数生成表单字段是非常合适的用法,避免你要用纯javascript做后台时频繁的制作表单,而不能重复利用 //这里是javascript部分,formfiled.js //生成器函数对字段的处理,让各字段name\className\label\value\placeholder赋值到input的属性…...
【xilinx】O-RAN 无线电接口 - Vivado 2020.1 及更新工具版本的发行说明
描述 记录包含 O-RAN 无线电接口 LogiCORE IP 的发行说明和已知问题,包括以下内容: 一般信息已知和已解决的问题 解决方案 一般信息 可以在以下三个位置找到支持的设备: O-RAN 无线电接口 IP 产品指南(需要访问O-RAN 安全站点&…...
结营考试- 算法进阶营地 - DAY11
结营考试 - 算法进阶营地 - DAY11 测评链接; A - 打卡题 考点:枚举; 分析 枚举 a _①_ b _②_ c d,中两个运算符的 3 3 3 种可能性,尝试寻找一种符合要求的答案。 参考代码 #include <bits/stdc.h> usi…...
设计模式: 访问者模式
文章目录 一、介绍二、模式结构三、优缺点1、优点2、缺点 四、应用场景 一、介绍 Visitor 模式(访问者模式)是一种行为设计模式,它允许在不修改对象结构的前提下,增加作用于一组对象上新的操作。就增加新的操作而言,V…...
selenium底层原理详解
目录 1、selenium版本的演变 1.1、Selenium 1.x(Selenium RC时代) 1.2、Selenium 2.x(WebDriver整合时代) 1.3、Selenium 3.x 2、selenium原理说明 3、源码说明 3.1、启动webdriver服务建立连接 3.2、发送操作 1、seleni…...
【Solidity】继承
继承 Solidity 中使用 is 关键字实现继承: contract Father {function getNumber() public pure returns (uint) {return 10;}function getNumber2() public pure virtual returns (uint) {return 20;} }contract Son is Father {}现在 Son 就可以调用 Father 的 …...
docker 安装mino服务,启动报错: Fatal glibc error: CPU does not support x86-64-v2
背景 docker 安装mino服务,启动报错: Fatal glibc error: CPU does not support x86-64-v2 原因 Docker 镜像中的 glibc 版本要求 CPU 支持 x86-64-v2 指令集,而你的硬件不支持。 解决办法 降低minio对应的镜像版本 经过验证:qu…...
地图相册系统的设计与实现
摘 要 随着信息技术和网络技术的飞速发展,人类已进入全新信息化时代,传统管理技术已无法高效,便捷地管理信息。为了迎合时代需求,优化管理效率,各种各样的管理系统应运而生,各行各业相继进入信息管理时代&a…...
使用vh和rem实现元素响应式布局
示例代码 height: calc(100vh 30rem) vh(Viewport Height):vh是一个相对单位,代表浏览器窗口高度的百分比,例如20vh就是浏览器窗口高度的20%。 rem(root em):rem是通过html根元素…...
螺旋矩阵 II(LeetCode)
题目 给你一个正整数 n ,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。 解题 def generateMatrix(n):matrix [[0] * n for _ in range(n)]top, bottom 0, n - 1left, right 0, n - 1num 1while top <…...
如何快速掌握一款MCU
了解MCU特点 rom ,ramgpiotimerpower 明确哪些资源是项目开发需要的 认真理解相关资料模块 开始编程 编写特别的验证程序(项目不紧)按照自己的理解编写(老司机,时间紧张) 掌握MCU基本功能 定时器 固…...
XSS-DOM
文章目录 源码SVG标签Dom-Clobbringtostring 源码 <script>const data decodeURIComponent(location.hash.substr(1));;const root document.createElement(div);root.innerHTML data;// 这里模拟了XSS过滤的过程,方法是移除所有属性,sanitize…...
uniapp去掉页面导航条
在pages.json文件中,globalStyle中添加 ”app-plus“:{"titleNView":false }...
MySQL数据库专栏(三)数据库服务维护操作
1、界面维护,打开服务窗口找到MySQL服务,右键单击可对服务进行启动、停止、重启等操作。 选择属性,还可以设置启动类型为自动、手动、禁用。 2、指令维护 卸载服务:sc delete [服务名称] 例如:sc delete MySQL 启动服…...
【QT】基于UDP/TCP/串口 的Ymodom通讯协议客户端
【QT】基于UDP/TCP/串口的Ymodom通讯协议客户端 前言Ymodom实现QT实现开源库的二次开发-1开源库的二次开发-2 串口方式实现TCP方式实现UDP方式实现补充:文件读取补充:QT 封装成EXE 前言 Qt 运行环境 Desktop_Qt_5_11_2_MSVC2015_64bit ,基于…...
超详细!!!electron-vite-vue开发桌面应用之引入UI组件库element-plus(四)
云风网 云风笔记 云风知识库 一、安装element-plus以及图标库依赖 npm install element-plus --save npm install element-plus/icons-vue npm i -D unplugin-icons二、vite按需引入插件 npm install -D unplugin-vue-components unplugin-auto-importunplugin-vue-componen…...
【排序篇】实现快速排序的三种方法
🌈个人主页:Yui_ 🌈Linux专栏:Linux 🌈C语言笔记专栏:C语言笔记 🌈数据结构专栏:数据结构 文章目录 1 交换排序1.1 冒泡排序1.2 快速排序1.2.1 hoare版本1.2.2 挖坑法1.2.3 前后指针…...
Java 标识符(详解)
文章目录 一、简介二、命名规则三、命名规范 一、简介 在 Java 中,用于给变量、类、方法等命名的符号组合,我们称之为Java标识符,它就像是给这些编程元素贴上的独特标签,以便在程序中能够准确地引用和操作它们。 二、命名规则 标…...
2024年,有哪些优质的计算机书籍推荐?
在2024年,计算机领域的新书层出不穷,涵盖了从基础理论到前沿技术的多个方面。以下是今年出版的几本备受关注的计算机新书。 1. AI与机器学习类 1、深度学习详解 1.李宏毅老师亲笔推荐,杨小康、周明、叶杰平、邱锡鹏鼎力推荐! 2.数百万次播…...
Python基础知识点--总结
1. 注释 注释用于提高代码的可读性,在代码中添加说明文字,使代码更容易理解。 单行注释:使用 # 符号开头,注释内容在符号之后的行内。多行注释:使用三引号( 或 """)包裹注释内…...
高效记录与笔记整理的策略:工具选择、结构设计与复习方法
✨✨ 欢迎大家来访Srlua的博文(づ ̄3 ̄)づ╭❤~✨✨ 🌟🌟 欢迎各位亲爱的读者,感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua小谢,在这里我会分享我的知识和经验。&am…...
Request重复读的问题
换了新工作都有时间写文章,每天也是加班到很晚,也不是工作内容多,主要是还是效率低,要考虑多干的很心累。 一、关于request重复读的问题,从源码的角度来分析 为什么他不能重复读 跳转 再看源码前可能需要一些基础的…...
Linux学习第60天:Linux驱动开发的一些总结
今天是Linux驱动开发的最后一个章节,题目中标明是60天完成的,其实在实际学习及笔记的整理中不止是60天。中间有过断更,有时断更的时间还是挺长的。这是在整个Linux驱动开发学习中最不满意的地方。 题目为Linux学习,其实这个题目有…...