当前位置: 首页 > 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 序列号的作用是用于标识每个数据包中的字节流的起始位置。…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

【git】把本地更改提交远程新分支feature_g

创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...