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

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 插入和删除元素的时间复杂度 头部插入/删除&#xff1a;只需要修改头结点的指针即可完成插入/删除操作&#xff0c;因此时间复杂度为 O(1)。尾部插入/删除&#xff1a;只需要修改尾结点的指针即可完成插入/删除操作…...

跑步锻炼(蓝桥杯)

跑步锻练 题目描述 本题为填空题&#xff0c;只需要算出结果后&#xff0c;在代码中使用输出语句将所填结果输出即可。 小蓝每天都锻炼身体。 正常情况下&#xff0c;小蓝每天跑 1 千米。如果某天是周一或者月初&#xff08;1 日&#xff09;&#xff0c;为了激励自己&#x…...

【SLAM】视觉SLAM简介

【SLAM】视觉SLAM简介 task04 主要了解了SLAM的主流框架&#xff0c;清楚VSALM中间接法与直接法的主要区别在什么地方&#xff0c;其各自的优势是什么&#xff0c;了解前端与后端的关系是什么 1.什么是SLAM 2.VSALM中间接法与直接法的主要区别在什么地方&#xff0c;其各自的…...

Visual Studio2019报错

1- Visual Studio2019报错 错误 MSB8036 找不到 Windows SDK 版本 10.0.19041.0的解决方法 小伙伴们在更新到Visual Studio2019后编译项目时可能遇到过这个错误&#xff1a;“ 错误 MSB8036 找不到 Windows SDK 版本 10.0.19041.0的解决方法”&#xff0c;但是我们明明安装了该…...

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()启动所有流程引擎中的执行器。执行器用于处理流程实例的执行&#xff0c;在引擎启动时&#xff0c;执行器会自动运行并处理待办任务和定时任务。getRepositorySe…...

TensorFlow与pytorch特定版本虚拟环境的安装

TensorFlow与Python的版本对应&#xff0c;注意&#xff0c;一定要选择对应的版本&#xff0c;否则会让你非常痛苦&#xff0c;折腾很久搞不清楚原因。 建议使用国内镜像源安装 没有GPU后缀的就表示是CPU版本的&#xff0c;不加版本就是最新 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中的一些方法&#xff0c;mapper 要继承BaseMapper<实体类> 4、在实…...

Selenium常见问题解析

1、元素定位失败&#xff1a; 在使用Selenium自动化测试时&#xff0c;最常见的问题之一是无法正确地定位元素&#xff0c;这可能导致后续操作失败。解决方法包括使用不同的定位方式&#xff08;如xpath、CSS selector、id等&#xff09;&#xff0c;等待页面加载完全后再进行…...

【npm】npm私有库的使用-绑定

注册npm账户 输入基本信息 验证 收一次性验证码 登录 本地绑定 全局绑定了其他的私有库 若要在专门发包的项目中&#xff0c;发包到自己的私有库&#xff0c;需要在项目文件夹中创建一个.npmrc文件 创建文件 可以直接在项目目录下输入touch .npmrc创建文件 文件内容 regi…...

spring seccurity OAuth 2.0授权服务器工作流程

一、客户端配置&#xff1a;在configure(ClientDetailsServiceConfigurer clients)方法中&#xff0c;配置了一个客户端&#xff0c;包括客户端标识符、客户端秘密、授权类型、授权范围和令牌有效期等信息。这个客户端表示某个应用程序或服务&#xff0c;它将向授权服务器请求访…...

【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环境搭建 虚拟机系统&#xff1a;Ubuntu22.04 虚拟机&#xff1a;VMware-player-full-16.2.5-2090451…...

百度SEO优化技巧大揭秘(百度SEO优化策略,提升网站排名)

百度SEO优化策略介绍 作为全球最大的中文搜索引擎&#xff0c;百度的优化是各大网站的重中之重。首先&#xff0c;网站内容是关键&#xff0c;要确保内容原创、有价值、符合用户需求。其次&#xff0c;合理设置页面标题、关键词、描述等元素。还要注意网站结构&#xff0c;合理…...

JavaScript:二进制数组【笔记】

二进制数组【ArrayBuffer对象、Type的Array视图和DataView视图】JavaScript操作二进制数据的一个接口。 这些接口原本是和WebGL有关【WebGL是浏览器与显卡之间的通信接口】&#xff0c;为了满足JavaScript与显卡之间大量、实时数据交换&#xff0c;那么JavaScript和显卡之间的…...

华为云认证考试包含哪些内容?

华为云计算认证考试包含哪些内容&#xff1f;华为云计算认证涵盖了hcia、HCIP、HCIE三个级别的认证。HCIA云计算方向只要考一门笔试&#xff0c;考试覆盖基础通识知识、虚拟化FusionCompute、桌面云FusionAccess、云计算发展趋势共四大模块知识点&#xff0c;包括云计算概述、服…...

进程程序替换

✅<1>主页&#xff1a;&#xff1a;我的代码爱吃辣 &#x1f4c3;<2>知识讲解&#xff1a;Linux——进程替换 ☂️<3>开发环境&#xff1a;Centos7 &#x1f4ac;<4>前言&#xff1a;我们创建子进程的目的是什么&#xff1f;想让子进程帮我们执行特定的…...

理解HTTPS/TLS/SSL(二)可视化TLS握手过程并解密加密数据

文章目录 WireShark抓包TLS握手过程Client HelloServer HelloEncryped Extenstions, Certificate, Certificate VerifyChange Ciper Spec, FinshedTLS 1.2和TLS 1.3的区别能不能在进一步&#xff1f; 解密WireShark中抓到的TLS包参考资料 上一篇文章已经在本地使用了生成自签名…...

一文详解TCP三次握手四次挥手

文章目录 TCP的三次握手和四次挥手三次握手四次挥手 TCP的三次握手和四次挥手 基本概念 SYN&#xff08;Synchronize Sequence Numbers&#xff0c;同步序列数字&#xff09;&#xff1a;用于建立连接的同步信号。 SYN 序列号的作用是用于标识每个数据包中的字节流的起始位置。…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

MinIO Docker 部署:仅开放一个端口

MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...

【Linux系统】Linux环境变量:系统配置的隐形指挥官

。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量&#xff1a;setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...

tomcat指定使用的jdk版本

说明 有时候需要对tomcat配置指定的jdk版本号&#xff0c;此时&#xff0c;我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...

零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程

STM32F1 本教程使用零知标准板&#xff08;STM32F103RBT6&#xff09;通过I2C驱动ICM20948九轴传感器&#xff0c;实现姿态解算&#xff0c;并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化&#xff0c;适合嵌入式及物联网开发者。在基础驱动上新增…...

从实验室到产业:IndexTTS 在六大核心场景的落地实践

一、内容创作&#xff1a;重构数字内容生产范式 在短视频创作领域&#xff0c;IndexTTS 的语音克隆技术彻底改变了配音流程。B 站 UP 主通过 5 秒参考音频即可克隆出郭老师音色&#xff0c;生成的 “各位吴彦祖们大家好” 语音相似度达 97%&#xff0c;单条视频播放量突破百万…...

goreplay

1.github地址 https://github.com/buger/goreplay 2.简单介绍 GoReplay 是一个开源的网络监控工具&#xff0c;可以记录用户的实时流量并将其用于镜像、负载测试、监控和详细分析。 3.出现背景 随着应用程序的增长&#xff0c;测试它所需的工作量也会呈指数级增长。GoRepl…...