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

[java基础]LinkedList源码粗析

news 来源：原创 2025/5/14 11:41:34

LinkedList 的数据结构

实现List、Deque 接口，基于 双向链表实现的列表。与基于数组的 ArrayList 不同，基于链表的LinkedList 允许在列表的任何位置快速地插入和删除元素。
Java中LinkedList实现了Deque，它提供了 add, offer, remove, poll, element, peek 等方法，因此可以视LinkedList为一个基于链表的 双向队列。
双向链表的高效删除、添加元素，相较低的查询效率LinkedList也具备。
LinkedList 的每个元素都包含三个部分：
  • 数据本身
  • 指向前一个元素的引用（前驱）
  • 指向后一个元素的引用（后继）
这种双向链接使得 LinkedList 可以很容易地向前或向后遍历，并且可以在 O(1) 时间内完成插入和删除操作。

LinkedList方法

get(int index)方法

调用node(int index)方法遍历链表返回指定index元素

add(E e)方法

使用add添加元素时，默认插入到尾部，所以不需要查找后更新|添加，实现复杂度是O（1）。
注意：LinkedList不需要扩容
由构造方法可以看出来，LinkedList是允许null值的，且null值数量不做限制

add(int index, E element)方法

找到原来的Index位置的元素，然后插入。 插入操作=创建一个新的节点+并将其连接到原index处节点前

remove()方法

这个方法是实现自Deque接口，具有队列性质，移除first节点

remove(int index)

这个是List的实现，遍历找出指定index的节点后然后移除

remove(Object o)方法

注意， 方法只会移除LinkedList链表中第一个匹配对象，如果返回false表示没有次对象。

LinkedList 的特点

  • 插入和删除操作快：由于双向链表的特性，可以在 O(1) 时间内完成插入和删除。
  • 不适合随机访问：相对于数组来说，链表的随机访问较慢，因为必须从头开始遍历链表直到找到所需的元素。
  • 内存消耗较大：每个元素除了存储自身的数据外，还需要额外的空间来保存前后节点的引用，因此比数组占用更多的内存。
  • 允许空值

优化点

remove(Object o)方法移除元素时，先进行空值 == null判断，然后item比较时使用 == null判断，这样比equals高效

LinkedList 相关的面试题

下面列出了一些与 LinkedList 相关的常见面试题：

1.解释什么是双向链表，并描述其优势。

- 双向链表是一种链表，其中每个节点包含对前一个节点和下一个节点的引用。这使得可以从前向后和从后向前遍历列表，也简化了插入和删除操作。

- 在 LinkedList 中，插入操作只需要修改相关节点的前后指针即可，因此时间复杂度为 O(1)。

2.LinkedList 和 ArrayList 之间的区别是什么？

- LinkedList 使用链表实现，适合频繁的插入和删除操作；ArrayList 使用数组实现，适合随机访问元素。

3.为什么 LinkedList 的 get(int index) 方法的时间复杂度是 O(n)?

- 因为 LinkedList 需要从头部或尾部开始遍历到指定索引的位置，最坏情况下可能需要遍历整个列表。

- LinkedList 提供了对 ListIterator 的支持，允许用户在迭代过程中添加、删除或修改元素。

4.如何检测 LinkedList 中是否存在环？（理论上标准的LinkedList不会出现环形链表）

- 常见的方法是使用 Floyd's Cycle-Finding Algorithm 或者称为龟兔赛跑算法，通过两个不同速度的指针来检测循环的存在。

5.如何反转一个 LinkedList？

- 反转 LinkedList 的一种方法是从头节点开始，逐个交换每个节点的前后指针，直到到达最后一个节点。

推荐资料

https://www.hello-algo.com/

相关文章：

[java基础]LinkedList源码粗析

LinkedList 的数据结构 实现List、Deque 接口，基于 双向链表实现的列表。与基于数组的 ArrayList 不同，基于链表的LinkedList 允许在列表的任何位置快速地插入和删除元素。 Java中LinkedList实现了Deque，它提供了 add, offer, remove, poll, …...

编程日记 2025/5/14 11:41:34

基于Spring Boot的海滨体育馆管理系统的设计与实现

风定落花生，歌声逐流水，大家好我是风歌，混迹在java圈的辛苦码农。今天要和大家聊的是一款基于springboot的海滨体育馆管理系统的设计与实现。项目源码以及部署相关请联系风歌，文末附上联系信息 。 项目简介： 宠物医院…...

编程日记 2025/5/14 11:38:20

易支付二次元网站源码及部署教程

易支付二次元网站源码及部署教程 引言 在当今数字化时代，二次元文化逐渐成为年轻人生活中不可或缺的一部分。为了满足这一庞大用户群体的需求，搭建一个二次元主题网站显得尤为重要。本文将为您详细介绍易支付二次元网站源码的特点及其部署教程&#xf…...

编程日记 2025/5/9 18:14:46

json序列化时，默认遇到中文会转换成unicode，如果想要保留中文怎么办？

在使用 Python 的 json 模块进行序列化时，默认情况下会将中文转换为 Unicode 编码。如果你希望在序列化时保留中文，可以通过设置 ensure_asciiFalse 来实现。 以下是示例代码： import jsondata {"name": "李浩瑞", &q…...

编程日记 2025/5/14 11:39:47

Perl语言的循环实现

Perl语言的循环实现 引言 Perl是一种强大的脚本语言，以其灵活的语法和强大的文本处理能力著称。无论是在系统管理、网络编程，还是在Web应用开发中，Perl都广泛应用于各种领域。循环是编程语言中一个极其重要的概念，它允许程序重复…...

编程日记 2025/5/12 10:25:28

IOMMU PT

什么是 IOMMU PT IOMMU PT（Input/Output Memory Management Unit - Pass-Through）是一种技术，主要用于虚拟化环境中，特别是在使用直接设备分配（也称为设备直通）的情况下。这项技术允许虚拟机直接访问物理硬…...

编程日记 2025/5/9 21:59:01

DNS协议漏洞利用实验_hust计算机网络安全实验

文章目录 计算机网络安全实验 DNS协议漏洞利用实验 docker使用 建立实验环境docker常用指令 一些注意事项设置本地 DNS 服务器 配置用户计算机设置本地DNS服务器在本地 DNS 服务器中建一个区域 修改主机文件（可略）netwox实施DNS的用户响应欺骗攻击netwo…...

编程日记 2025/5/10 8:45:56

深度学习中的卷积和反卷积（二）——反卷积的介绍

1 简介 反卷积（deconvolution）又称转置卷积，是卷积的拟操作，常用于GAN等模型中。反卷积是上采样的一种，上采样是指将特征图维度恢复到原始图的维度，这种增大维度的过程被称为上采样。上采样可以用插值或反…...

编程日记 2025/5/14 5:20:39

PyCharm 引用其他路径下的文件报错 ModuleNotFound 或报红

PyCharm 中引用其他路径下的文件提示 ModuleNotFound，将被引用目录添加到系统路径： # # 获取当前目录 dir_path os.path.dirname(os.path.realpath(__file__)) # # 获取上级目录 parent_dir_path os.path.abspath(os.path.join(dir_path, os.pardir))…...

编程日记 2025/4/28 9:52:31

【人工智能】Transformers之Pipeline（二）：自动语音识别（automatic-speech-recognition）

​​​​​​​ 目录 一、引言 二、自动语音识别（automatic-speech-recognition） 2.1 概述 2.2 技术原理 2.2.1 whisper模型 2.2.2 Wav2vec 2.0模型 2.3 pipeline参数 2.3.1 pipeline对象实例化参数​​​​​​​ 2.3.2 pipeline对象使用参数…...

编程日记 2025/5/8 17:04:04

Linux 工作队列

系列文章目录 Linux内核学习 Linux 知识（1） Linux 知识（2） Linux 工作队列 Linux 内核源代码情景分析（一） Linux 设备驱动程序（二） 文章目录 系列文章目录综述工作（work_…...

编程日记 2025/5/11 3:19:29

程序血缘分析技术在工商银行软件工程中的应用

当前，随着软件领域技术更新换代速度的日益加快，市场需求也变得更加多样化和个性化，业界普遍通过加速产品迭代来满足客户需求，但在此过程中也暴露出一些研发管理痛点问题，如服务和程序类资产信息分散于各个不同的应用和系统中，信息归集费时费力；设计、开发和测试人员无法…...

编程日记 2025/5/11 5:43:59

纯手工（不基于maven的pom.xml、Web容器）连接MySQL数据库的详细过程（Java Web学习笔记）

1 引言 最近读一些Java Web开发类的书籍时，发现书中的连接数据库的过程缺少了一些关键性的过程，这对初学者非常不友好。为此，本文将给出详细的连接MySQL数据库的过程，并且是纯手工，不依赖于pom.xml和Web容器&#xff…...

编程日记 2025/5/13 6:42:02

node-sass@4.14.1报错的最终解决方案分享

输入npm i全安装文件所需的依赖的时候，博主是使用sass去书写的，使用的是node-sass4.14.1和sass-loader7.3.1的版本的，安装的时候老是出现错误， node-sass4.14.1版本不再被支持的原因 node-sass 是一个基于 LibSass 的 Node.js 绑…...

编程日记 2025/5/7 7:34:06

腾讯云AI代码助手编程挑战赛-厨房助手之AI大厨

腾讯云AI代码助手编程挑战赛-厨房助手之AI大厨 作品简介 身处当今如火箭般迅猛发展的互联网时代，智能聊天助手已然化身成为提升用户体验的关键利器，全方位渗透至人们的数字生活。 紧紧跟随着这股汹涌澎湃的时代浪潮，我毅然投身于极具挑战性…...

编程日记 2025/5/9 21:42:41

【Linux系列】如何使用 nohup 命令在后台运行脚本

💝💝💝欢迎来到我的博客，很高兴能够在这里和您见面！希望您在这里可以感受到一份轻松愉快的氛围，不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...

编程日记 2025/5/12 3:54:47

Web渗透测试之XSS跨站脚本攻击 跨域是什么？同源机制又是什么？ cors以及Jsonp是什么 一篇文章给你说明白

目录 Cookie的Httponly属性和逃过方式 浏览器同源机制 cors跨域和jsonp跨域和跨域标签 Cors跨域 - 跨源 Jsonp 跨域 jsonp跨域原理： 说明: Cookie的Httponly属性和逃过方式 Xss攻击手段 最常用的目的获取cookie Cookie中设置了 httponlyTrue 方式js操作获…...

编程日记 2025/5/12 17:56:14

K-Means 聚类算法：用生活场景讲解机器学习的“分组”方法

一、K-Means 算法概述 K-Means 是一种经典的无监督学习聚类算法，目的是将数据集中 n 个样本划分成 K 个簇（cluster），每个样本根据其特征被归入与之最接近的簇。简单来说，这就像在超市购物时，顾客会被根据购…...

编程日记 2025/5/12 17:24:53

C语言与ASCII码应用之简单加密

加密是什么？什么是加密通话？用人话说就是一句有含义的话，经过一定的特殊规则把里面的每个字按照这个规则进行改变，但是这个规则只有你和你想让知道这条信息的人知道 今天我们来用ASCII码编写一个简单加密与解密的程序&#xff0c…...

编程日记 2025/5/12 22:23:13

python无需验证码免登录12306抢票 --selenium(2)

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档 [TOC](python无需验证码免登录12306抢票 --selenium(2)) 前言 提示：这里可以添加本文要记录的大概内容： 就在刚刚我抢的票：2025年1月8日…...

编程日记 2025/5/14 11:32:10

[论文阅读]Corpus Poisoning via Approximate Greedy Gradient Descent

Corpus Poisoning via Approximate Greedy Gradient Descent [2406.05087] Corpus Poisoning via Approximate Greedy Gradient Descent 基于近似贪婪梯度下降的语料库投毒 面向检索器的攻击 AGGD 通过从所有符元位置中选择排名最高的符元，而不是从单个随机采样…...

编程日记 2025/5/7 7:48:07

C++—9、如何在Microsoft Visual Studio中调试C++

本文通过实例操作来介绍 Visual Studio 调试器的功能。调试器在运行过程中可提供许多方法让你查看代码的情况。 你可以逐步浏览代码、查看变量中存储的值、设置对变量的监视以查看值何时改变、检查代码的执行路径、查看代码分支是否正在运行等等。本实例主要是设置断点及查看内…...

编程日记 2025/5/5 8:40:14

《深度剖析：开源与闭源模型，AI舞台上的不同角色》

在人工智能蓬勃发展的当下，模型的选择如同为一场战役挑选合适的武器，至关重要。开源模型与闭源模型作为AI领域的两大阵营，在性能和应用场景上展现出显著差异，深刻影响着开发者、企业以及整个行业的走向。 性能差异：实…...

编程日记 2025/5/13 17:14:04

开源 vGPU 方案 HAMi 解析

开源 vGPU 方案 HAMi 一、k8s 环境下 GPU 资源管理的现状与问题 （一）资源感知与绑定 在 k8s 中，资源与节点紧密绑定。对于 GPU 资源，我们依赖 NVIDIA 提供的 device-plugin 来进行感知，并将其上报到 kube-apiserver…...

编程日记 2025/5/4 7:03:49

Unity 大地图功能 离线瓦片地图

不使用第二个摄像机实现类似开放世界的大地图功能。 功能如下： 按下M键打开/关闭大地图功能 打开大地图时，默认玩家位置居中 大地图支持拖拽，可调节拖拽速度，支持XY轴翻转 支持大地图设置边缘偏移量 可设置是否启动拖拽边界 …...

编程日记 2025/5/12 22:10:47

【计算机网络】什么是网关（Gateway）？

网上冲浪多了，你可以听到过网关（Gateway）这个词，但是却不太清楚网关（Gateway）到底是干什么的、负责网络当中的什么任务，本篇文字将会为你介绍网关（Gateway）的作用&#x…...

编程日记 2025/5/10 13:08:27

AIOps 平台

AIOps（Artificial Intelligence for IT Operations）平台是一种结合人工智能（AI）技术和IT运营管理的解决方案，旨在通过自动化、智能化的手段优化企业IT系统的运行与管理。以下是AIOps平台的核心功能、优势以及常见的技术…...

编程日记 2025/5/9 18:17:58

使用 SQL 和表格数据进行问答和 RAG（1）—数据库准备

一. 从 .sql/csv/xlsx 文件创建 sqlite 数据库。 要从.sql文件准备 SQL DB，这里会将创建数据库的代码放到了，将文件复制到data/sql目录中，然后在终端中的项目文件夹中执行： pip install sqlite3现在创建一个名为sqldb的数据库&a…...

编程日记 2025/5/12 4:18:27

TCP与UDP协议

一、主要区别 ① 连接的建立和断开： TCP（Transform Control Protocol）通过三次握手来建立一个可靠的连接。这个过程确保了双方都能发送和接收数据。连接建立后，TCP提供稳定的数据传输服务。当通信结束时，TCP通过四次…...

编程日记 2025/5/12 17:13:29

【MySQL】MVCC详解, 图文并茂简单易懂

欢迎来到啊妮莫的学习小屋 祝读本文的朋友都天天开心呀 目录 MVCC简介快照读与当前读快照读当前读 隔离级别隐藏字段和Undo Log版本链✨MVCC原理--ReadView✨ReadView简介设计思路适用隔离级别重要内容 ReadView规则MVCC整体流程 不同隔离级别下的MVCC读已提交可重复读 总结 M…...

编程日记 2025/5/9 6:00:43

Cisco认证是Cisco公司建立的网络技术证书体系

思科认证体系是由Cisco公司建立的分为3个层次的网络技术证书体系，随着Cisco产品线的扩大和市场份额的不断提升，Cisco产品从当初仅有的 Cisco路由器和Cisco交换机发展到现在的6大方向：路由交换，网络设计，网络安全&#…...

编程日记 2025/5/10 22:49:44

Clojure语言的面向对象编程

Clojure语言的面向对象编程 引言 Clojure是一种现代的Lisp方言，它特别强调函数式编程，Immutable数据结构和强大的并发能力。然而，很多人可能会问：Clojure支持面向对象编程吗？虽然Clojure没有像Java或C那样的传统类和…...

编程日记 2025/5/13 17:45:18

React快速上手到项目实战总篇

React核心价值与前置知识 时刻保持对知识的渴望 家人们 开学!!! 核心价值 组件化（易开发易维护） 数据驱动视图 ：定义好数据和ui的显示规则 即UIf(state) 只关注业务数据修改，不在操作DOM 增加开发效率 使用vite创建Recat项目 …...

编程日记 2025/5/1 13:06:05

Dart语言的语法

Dart语言的魅力与应用 引言 随着互联网的发展和移动设备的普及，编程语言层出不穷，各种语言如雨后春笋般被创造出来。其中，Dart语言作为一种现代编程语言，凭借其简洁的语法、强大的功能以及良好的性能，受到了越来越多…...

编程日记 2025/5/11 17:32:38

C++——多态

目录 前言 1. 多态的概念 2. 多态的定义及其实现 2.1 多态的构成条件 2.1.1 实现多态的两个重要条件 2.1.2 虚函数 2.1.3 虚函数的重写/覆盖 2.1.4 多态场景的⼀个选择题 2.1.5 虚函数重写的⼀些其他问题 2.1.5.1 协变（了解） 2.1.5.2 析构函…...

编程日记 2025/4/30 20:23:09

什么是Transformer模型中的KV缓存：上下文新增那之前计算的KV还可用，在原有基础上对新增的进行计算就行

什么是Transformer模型中的KV缓存? 在Transformer模型中，KV缓存（Key-Value Cache）具有重要作用，以下是关于它的详细介绍： 概念含义 KV缓存主要是用于存储在模型推理过程中已经计算过的键（Key）和值（Value）信息。在Transformer架构里，比如在自注意力机制等计算环节…...

编程日记 2025/5/10 17:18:25

12.C语言中的struct详解：定义、赋值、指针、嵌套与位字段

目录 1.简介2.struct 的复制3.struct 指针4.struct 的嵌套5.位字段6.弹性数组成员 1.简介 本篇原文为：C语言中的struct详解：定义、赋值、指针、嵌套与位字段。 更多C进阶、rust、python、逆向等等教程，可点击此链接查看：酷程网 …...

编程日记 2025/5/13 12:13:40

洛谷 P3000 [USACO10DEC] Cow Calisthenics G

思路 题目要求断若干条边后形成的连通块中，最大的直径最小，很明显的二分。关键就在于如何写 c h e c k check check 函数了。 可以用 d f s dfs dfs 来判断要断哪条边。 一、 d [ u ] d[u] d[u] 定义 设 d [ u ] d[u] d[u] 为从 u u u 出发到子树…...

编程日记 2025/5/11 23:41:29

前端拿到zip中所有文件并下载为新的zip文件

问题原因：后端返回了一个zip格式文件供前端下载，然后下载后，形成了zip套zip的形式，当后端不愿处理时，前端不能坐以待毙 PS：当压缩包文件量过大，前端可能会出问题（脑测，未…...

编程日记 2025/5/10 7:00:08

JVM调优

jvm调优步骤：1发现问题、2。定位问题、3.解决问题 jdk自带的命令行调优工具： 1. jps 查看正在运行的 Java 进程 jps -v 查看进程启动时的JVM参数 options 参数： -q：仅仅显示 LVMID（local virtual machine id&#x…...

编程日记 2025/5/9 20:25:07

【前端】【HTML】入门基础知识

参考视频&#xff1a;【狂神说Java】HTML5完整教学通俗易懂_哔哩哔哩_bilibili 一、基本结构 二、基本标签 <h1>&#xff1a;一级标题&#xff0c;通常用于页面的主标题&#xff0c;字体较大且醒目。 <h2>&#xff1a;二级标题&#xff0c;用于副标题或主要章节标…...

编程日记 2025/5/7 4:13:53

Ubuntu桌面管理环境: GDM3，KDM，LightDM

介绍 Ubuntu是一个广受欢迎的Linux操作系统&#xff0c;拥有强大而多样化的桌面管理环境。其中三个常用的桌面管理环境是GDM3&#xff0c;KDM和LightDM。本篇博客将介绍这三个桌面管理环境的特点和功能。 GDM3 (GNOME Display Manager) GDM3是默认的桌面管理环境&#xff0c…...

编程日记 2025/5/9 4:40:12

每天你好20250110（距离春节19天！！！）

亲爱的朋友们&#xff0c;大家早上好&#xff01; &#x1f31e; 今晨乃 2025 年 1 月 10 日&#xff0c;星期五&#xff0c;农历乙巳[蛇]年十一月二十一日。祥蛇逸彩送祥&#xff0c;金乌喷薄耀世&#xff0c;晨晖破雾而来&#xff0c;恰似“赤日初升&#xff0c;其道大光”&…...

编程日记 2025/5/11 13:22:21

iOS 本地新项目上传git仓库，并使用sourceTree管理

此文记录的场景描述&#xff1a; iOS前期开发时&#xff0c;在本地创建项目&#xff0c;直至开发一段时间&#xff0c;初期编码及框架已完善后&#xff0c;才拿到git仓库的地址。此时需要将本地代码上传到git仓库。 上传至git仓库&#xff0c;可以使用终端&#xff0c;键入命令…...

编程日记 2025/5/10 5:40:56

计算机网络之---计算机网络的性能评估

计算机网络的性能评估是指通过各种标准和指标来衡量网络的工作效率和质量&#xff0c;进而对网络进行优化和改进的过程。评估的目标是确保网络能够满足预期的服务质量&#xff08;QoS&#xff09;和性能需求。常见的计算机网络性能评估指标包括带宽、延迟、吞吐量、丢包率等。 …...

编程日记 2025/5/9 18:16:26

对话｜企业如何构建更完善的容器供应链安全防护体系

对话&#xff5c;企业如何构建更完善的容器供应链安全防护体系 云布道师 随着云计算和 DevOps 的兴起&#xff0c;容器技术和自动化成为软件开发中的必要手段&#xff0c;软件供应链也进入了自动化及 CI/CD 阶段。然而&#xff0c;容器技术和自动化虽然提升了软件的更新速度&…...

编程日记 2025/5/10 0:19:06

【SpringSecurity】二、自定义页面前后端分离

文章目录 1、用户认证流程AuthenticationSuccessHandler AuthenticationFailureHandlerSecurityFilterChain配置用户认证信息 2、会话并发处理2.1、实现处理器接口2.2、SecurityFilterChain配置 1、用户认证流程 AuthenticationSuccessHandler AuthenticationFailureHandler …...

编程日记 2025/5/13 14:03:02

在 Vue 3 集成 e签宝电子合同签署功能

实现 Vue 3 e签宝电子合同签署功能&#xff0c;需要使用 e签宝提供的实际 SDK 或 API。 e签宝通常提供针对不同平台&#xff08;如 Web、Android、iOS&#xff09;的 SDK&#xff0c;而 Web 端一般通过 WebView 或直接使用嵌入式 iframe 来加载合同签署页面。 下面举个 &…...

编程日记 2025/5/10 1:19:30

基于华为ENSP的OSPF接口网络类型深入浅出（4）

本篇技术博文摘要 &#x1f31f; OSPF的接口在不同网络类型下的工作方式&#xff1b;不同网络类型下的报文通告方式深入浅出hub-spoke架构 引言 &#x1f4d8; 在这个快速发展的技术时代&#xff0c;与时俱进是每个IT人的必修课。我是肾透侧视攻城狮&#xff0c;一名什么都会一…...

编程日记 2025/5/14 8:45:32

西电-算法分析-研究生课程复习笔记

24年秋的应该是张老师最后一次用卷面考试&#xff0c;他说以后这节课的期末考试都是在OJ上刷题了张老师上课还挺有意思的&#xff0c;上完之后能学会独立地思考算法设计问题了。整节课都在强调规模压缩这个概念&#xff0c;考试也是考个人对这些的理解&#xff0c;还挺好玩的哈…...

编程日记 2025/5/13 17:26:23