LinkedList 源码分析
LinkedList 是一个基于双向链表实现的集合类。

LinkedList 插入和删除元素的时间复杂度
- 头部插入/删除:只需要修改头结点的指针即可完成插入/删除操作,因此时间复杂度为 O(1)。
- 尾部插入/删除:只需要修改尾结点的指针即可完成插入/删除操作,因此时间复杂度为 O(1)。
- 指定位置插入/删除:需要先移动到指定位置,再修改指定节点的指针完成插入/删除,因此需要移动平均 n/2 个元素,时间复杂度为 O(n)。
LinkedList 实现了以下接口:
- List : 表明它是一个列表,支持添加、删除、查找等操作,并且可以通过下标进行访问。
- Deque :继承自 Queue 接口,具有双端队列的特性,支持从两端插入和删除元素,方便实现栈和队列等数据结构。
- Cloneable :表明它具有拷贝能力,可以进行深拷贝或浅拷贝操作。
- Serializable : 表明它可以进行序列化操作,也就是可以将对象转换为字节流进行持久化存储或网络传输,非常方便。

每个节点的定义
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;}
}
插入元素
// 在链表尾部插入元素
public boolean add(E e) {linkLast(e);return true;
}// 在链表指定位置插入元素
public void add(int index, E element) {// 下标越界检查checkPositionIndex(index);// 判断 index 是不是链表尾部位置if (index == size)// 如果是就直接调用 linkLast 方法将元素节点插入链表尾部即可linkLast(element);else// 如果不是则调用 linkBefore 方法将其插入指定元素之前linkBefore(element, node(index));
}// 将元素节点插入到链表尾部
void linkLast(E e) {// 将最后一个元素赋值(引用传递)给节点 lfinal Node<E> l = last;// 创建节点,并指定节点前驱为链表尾节点 last,后继引用为空final Node<E> newNode = new Node<>(l, e, null);// 将 last 引用指向新节点last = newNode;// 判断尾节点是否为空// 如果 l 是null 意味着这是第一次添加元素if (l == null)// 如果是第一次添加,将first赋值为新节点,此时链表只有一个元素first = newNode;else// 如果不是第一次添加,将新节点赋值给l(添加前的最后一个元素)的nextl.next = newNode;size++;modCount++;
}// 在指定元素之前插入元素
void linkBefore(E e, Node<E> succ) {// assert succ != null;断言 succ不为 null// 定义一个节点元素保存 succ 的 prev 引用,也就是它的前一节点信息final Node<E> pred = succ.prev;// 初始化节点,并指明前驱和后继节点final Node<E> newNode = new Node<>(pred, e, succ);// 将 succ 节点前驱引用 prev 指向新节点succ.prev = newNode;// 判断尾节点是否为空,为空表示当前链表还没有节点if (pred == null)first = newNode;else// succ 节点前驱的后继引用指向新节点pred.next = newNode;size++;modCount++;
}
获取元素
// 获取链表的第一个元素
public E getFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return f.item;
}// 获取链表的最后一个元素
public E getLast() {final Node<E> l = last;if (l == null)throw new NoSuchElementException();return l.item;
}// 获取链表指定位置的元素
public E get(int index) {// 下标越界检查,如果越界就抛异常checkElementIndex(index);// 返回链表中对应下标的元素return node(index).item;
}// 返回指定下标的非空节点
Node<E> node(int index) {// 断言下标未越界// assert isElementIndex(index);// 如果index小于size的二分之一 从前开始查找(向后查找) 反之向前查找if (index < (size >> 1)) {Node<E> x = first;// 遍历,循环向后查找,直至 i == indexfor (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;}
}
get(int index) 或 remove(int index) 等方法内部都调用了node(int index)方法来获取对应的节点。
从这个方法的源码可以看出,该方法通过比较索引值与链表 size 的一半大小来确定从链表头还是尾开始遍历。如果索引值小于 size 的一半,就从链表头开始遍历,反之从链表尾开始遍历。这样可以在较短的时间内找到目标节点,充分利用了双向链表的特性来提高效率
删除元素
// 删除并返回链表的第一个元素
public E removeFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return unlinkFirst(f);
}// 删除并返回链表的最后一个元素
public E removeLast() {final Node<E> l = last;if (l == null)throw new NoSuchElementException();return unlinkLast(l);
}// 删除链表中首次出现的指定元素,如果不存在该元素则返回 fals
public boolean remove(Object o) {// 如果指定元素为 null,遍历链表找到第一个为 null 的元素进行删除if (o == null) {for (Node<E> x = first; x != null; x = x.next) {if (x.item == null) {unlink(x);return true;}}} else {// 如果不为 null ,遍历链表找到要删除的节点for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item)) {unlink(x);return true;}}}return false;
}// 删除链表指定位置的元素
public E remove(int index) {// 下标越界检查,如果越界就抛异常checkElementIndex(index);return unlink(node(index));
}E unlink(Node<E> x) {// 断言 x 不为 null// assert x != null;// 获取当前节点(也就是待删除节点)的元素final E element = x.item;// 获取当前节点的下一个节点final Node<E> next = x.next;// 获取当前节点的前一个节点final Node<E> prev = x.prev;// 如果前一个节点为空,则说明当前节点是头节点if (prev == null) {// 直接让链表头指向当前节点的下一个节点first = next;} else { // 如果前一个节点不为空// 将前一个节点的 next 指针指向当前节点的下一个节点prev.next = next;// 将当前节点的 prev 指针置为 null,,方便 GC 回收x.prev = null;}// 如果下一个节点为空,则说明当前节点是尾节点if (next == null) {// 直接让链表尾指向当前节点的前一个节点last = prev;} else { // 如果下一个节点不为空// 将下一个节点的 prev 指针指向当前节点的前一个节点next.prev = prev;// 将当前节点的 next 指针置为 null,方便 GC 回收x.next = null;}// 将当前节点元素置为 null,方便 GC 回收x.item = null;size--;modCount++;return element;
}
unlink图解

遍历链表
推荐使用for-each 循环来遍历 LinkedList 中的元素, for-each 循环最终会转换成迭代器形式。
作者声明
如有问题,欢迎指正!
相关文章:
LinkedList 源码分析
LinkedList 是一个基于双向链表实现的集合类。 LinkedList 插入和删除元素的时间复杂度 头部插入/删除:只需要修改头结点的指针即可完成插入/删除操作,因此时间复杂度为 O(1)。尾部插入/删除:只需要修改尾结点的指针即可完成插入/删除操作…...
跑步锻炼(蓝桥杯)
跑步锻练 题目描述 本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。 小蓝每天都锻炼身体。 正常情况下,小蓝每天跑 1 千米。如果某天是周一或者月初(1 日),为了激励自己&#x…...
【SLAM】视觉SLAM简介
【SLAM】视觉SLAM简介 task04 主要了解了SLAM的主流框架,清楚VSALM中间接法与直接法的主要区别在什么地方,其各自的优势是什么,了解前端与后端的关系是什么 1.什么是SLAM 2.VSALM中间接法与直接法的主要区别在什么地方,其各自的…...
Visual Studio2019报错
1- Visual Studio2019报错 错误 MSB8036 找不到 Windows SDK 版本 10.0.19041.0的解决方法 小伙伴们在更新到Visual Studio2019后编译项目时可能遇到过这个错误:“ 错误 MSB8036 找不到 Windows SDK 版本 10.0.19041.0的解决方法”,但是我们明明安装了该…...
ffplay源码解析-PacketQueue队列
包队列架构位置 对应结构体源码 MyAVPacketList typedef struct MyAVPacketList {AVPacket pkt; //解封装后的数据struct MyAVPacketList *next; //下一个节点int serial; //播放序列 } MyAVPacketList;PacketQueue typedef struct PacketQueue {MyAVPacketList …...
Flowable主要API介绍
1. ProcessEngine 负责与各个服务进行交互和管理流程的整个生命周期。 方法描述getName()close()startExecutors()启动所有流程引擎中的执行器。执行器用于处理流程实例的执行,在引擎启动时,执行器会自动运行并处理待办任务和定时任务。getRepositorySe…...
TensorFlow与pytorch特定版本虚拟环境的安装
TensorFlow与Python的版本对应,注意,一定要选择对应的版本,否则会让你非常痛苦,折腾很久搞不清楚原因。 建议使用国内镜像源安装 没有GPU后缀的就表示是CPU版本的,不加版本就是最新 pip install tensorflow -i https:…...
【SpringMVC】拦截器JSR303的使用
【SpringMVC】拦截器&JSR303的使用 1.1 什么是JSR3031.2 为什么使用JSR3031.3 常用注解1.4 Validated与Valid区别1.5 JSR快速入门1.5.2 配置校验规则# 1.5.3 入门案例二、拦截器2.1 什么是拦截器2.2 拦截器与过滤器2.3 应用场景2.4 拦截器快速入门2.5.拦截器链2.6登录案列权…...
Java - LambdaQueryWrapper 的常用方法
1、查看项目中是否导入mybatisPlus的jar包 2、servie 层和实现类要集成mybatisPlus service 继承IService<> 实现类中要继承IService的实现类ServiceImpl<mapper,实体类> 3、如果想要mapper中的一些方法,mapper 要继承BaseMapper<实体类> 4、在实…...
Selenium常见问题解析
1、元素定位失败: 在使用Selenium自动化测试时,最常见的问题之一是无法正确地定位元素,这可能导致后续操作失败。解决方法包括使用不同的定位方式(如xpath、CSS selector、id等),等待页面加载完全后再进行…...
【npm】npm私有库的使用-绑定
注册npm账户 输入基本信息 验证 收一次性验证码 登录 本地绑定 全局绑定了其他的私有库 若要在专门发包的项目中,发包到自己的私有库,需要在项目文件夹中创建一个.npmrc文件 创建文件 可以直接在项目目录下输入touch .npmrc创建文件 文件内容 regi…...
spring seccurity OAuth 2.0授权服务器工作流程
一、客户端配置:在configure(ClientDetailsServiceConfigurer clients)方法中,配置了一个客户端,包括客户端标识符、客户端秘密、授权类型、授权范围和令牌有效期等信息。这个客户端表示某个应用程序或服务,它将向授权服务器请求访…...
【Tensorflow 2.12 电影推荐系统之排序模型】
Tensorflow 2.12 电影推荐系统之排序模型 学习笔记导入相关模块准备数据加载数据数据预处理获取词汇表构建模型定义评分排序模型定义损失函数以及模型评估指标定义完整的评分排序模型训练和评估创建排序模型实例缓存数据训练评估预测导出和加载模型结尾学习笔记 Tensorflow 2.1…...
ROS2-IRON Ubuntu-22.0 源码下载失败解决方法 vcs import --input
ROS2 一.ROS2 IRON环境搭建1.设置系统字符集为UTF-82.将RO2 apt 库添加到系统中3.添加ROS2 GPG key4.添加ROS 2 的软件源安装开发工具 二.下载ROS2sh源代码编译 一.ROS2 IRON环境搭建 虚拟机系统:Ubuntu22.04 虚拟机:VMware-player-full-16.2.5-2090451…...
百度SEO优化技巧大揭秘(百度SEO优化策略,提升网站排名)
百度SEO优化策略介绍 作为全球最大的中文搜索引擎,百度的优化是各大网站的重中之重。首先,网站内容是关键,要确保内容原创、有价值、符合用户需求。其次,合理设置页面标题、关键词、描述等元素。还要注意网站结构,合理…...
JavaScript:二进制数组【笔记】
二进制数组【ArrayBuffer对象、Type的Array视图和DataView视图】JavaScript操作二进制数据的一个接口。 这些接口原本是和WebGL有关【WebGL是浏览器与显卡之间的通信接口】,为了满足JavaScript与显卡之间大量、实时数据交换,那么JavaScript和显卡之间的…...
华为云认证考试包含哪些内容?
华为云计算认证考试包含哪些内容?华为云计算认证涵盖了hcia、HCIP、HCIE三个级别的认证。HCIA云计算方向只要考一门笔试,考试覆盖基础通识知识、虚拟化FusionCompute、桌面云FusionAccess、云计算发展趋势共四大模块知识点,包括云计算概述、服…...
进程程序替换
✅<1>主页::我的代码爱吃辣 📃<2>知识讲解:Linux——进程替换 ☂️<3>开发环境:Centos7 💬<4>前言:我们创建子进程的目的是什么?想让子进程帮我们执行特定的…...
理解HTTPS/TLS/SSL(二)可视化TLS握手过程并解密加密数据
文章目录 WireShark抓包TLS握手过程Client HelloServer HelloEncryped Extenstions, Certificate, Certificate VerifyChange Ciper Spec, FinshedTLS 1.2和TLS 1.3的区别能不能在进一步? 解密WireShark中抓到的TLS包参考资料 上一篇文章已经在本地使用了生成自签名…...
一文详解TCP三次握手四次挥手
文章目录 TCP的三次握手和四次挥手三次握手四次挥手 TCP的三次握手和四次挥手 基本概念 SYN(Synchronize Sequence Numbers,同步序列数字):用于建立连接的同步信号。 SYN 序列号的作用是用于标识每个数据包中的字节流的起始位置。…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...
CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...
C++ 基础特性深度解析
目录 引言 一、命名空间(namespace) C 中的命名空间 与 C 语言的对比 二、缺省参数 C 中的缺省参数 与 C 语言的对比 三、引用(reference) C 中的引用 与 C 语言的对比 四、inline(内联函数…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...
laravel8+vue3.0+element-plus搭建方法
创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...
初学 pytest 记录
安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...
