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

Java 中 LinkedList 的底层源码

        在 Java 的集合框架中,LinkedList是一个独特且常用的成员。它基于双向链表实现,与数组结构的集合类如ArrayList有着显著差异。深入探究LinkedList的底层源码,有助于我们更好地理解其工作原理和性能特点,以便在实际开发中做出更合适的选择。

        这里如何具体在idea里查看底层源码的教程在我ArrayList那篇文章有,基本大差不差,具体步骤我就不再演示了,我直接把所有底层源码总结下来供大家参考。

咱们可以根据这个代码逻辑自己推一下,捋清楚了思路就好理解多了。

一、基本结构与成员变量

LinkedList的底层核心是一个双向链表,其内部通过节点来存储数据。以下是LinkedList源码中关键的成员变量定义:

// 头节点
transient Node<E> first;
// 尾节点
transient Node<E> last;
// 元素数量
transient int size = 0;
// 底层双向链表节点的内部类
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;}
}

firstlast分别指向双向链表的头节点和尾节点,通过它们可以方便地对链表进行遍历和操作。size变量用于记录链表中元素的个数。Node内部类则定义了链表节点的结构,每个节点不仅存储了元素值item,还持有指向前驱节点prev和后继节点next的引用,这使得双向链表能够灵活地在两个方向上进行遍历和元素的插入、删除等操作。

二、构造函数剖析

无参构造函数

public LinkedList() {
}

无参构造函数非常简洁,它只是创建了一个空的LinkedList对象。此时,firstlast都为nullsize为 0,链表中没有任何元素。

带集合参数的构造函数

public LinkedList(Collection<? extends E> c) {this();addAll(c);
}

该构造函数先调用无参构造函数创建一个空链表,然后通过addAll方法将传入集合中的所有元素添加到新创建的LinkedList中。这为我们在初始化LinkedList时提供了一种便捷的方式,可以直接将其他集合中的元素导入进来。

三、元素添加操作

在链表尾部添加元素

add(E e)方法用于在链表尾部添加一个元素,它是LinkedList中最常用的添加元素的方式之一。

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++;
}

add(E e)方法内部调用了linkLast方法。linkLast方法首先记录原链表的尾节点l,然后创建一个新的节点newNode,使其前驱指向原尾节点l,后继为null。接着更新last指向新节点,如果原尾节点为空,说明链表之前是空的,此时first也指向新节点;否则将原尾节点的后继指向新节点。最后,更新元素数量size和修改次数modCount。这个过程使得在链表尾部添加元素的操作非常高效,时间复杂度为 O (1)。

在指定位置插入元素

add(int index, E element)方法可以在链表的指定位置插入一个元素。

public void add(int index, E element) {checkPositionIndex(index);if (index == size)linkLast(element);elselinkBefore(element, node(index));
}

该方法首先调用checkPositionIndex方法检查索引是否越界(要求0 <= index <= size)。如果索引等于size,说明要在链表尾部插入元素,直接调用linkLast方法即可;否则,调用linkBefore方法在指定节点前插入元素。这里的node(index)方法用于获取指定索引位置的节点:

Node<E> node(int index) {if (index < (size >> 1)) {Node<E> x = first;for (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;}
}

node(index)方法通过判断索引与链表长度一半的大小关系,决定从链表头部还是尾部开始遍历查找指定索引位置的节点。如果索引小于链表长度的一半,从链表头部开始遍历;否则从链表尾部开始遍历。这种优化策略可以减少遍历的节点数量,提高查找效率。

四、元素删除操作

移除指定位置的元素

remove(int index)方法用于移除链表中指定位置的元素。

public E remove(int index) {checkElementIndex(index);return unlink(node(index));
}

该方法先调用checkElementIndex方法检查索引是否越界(要求0 <= index < size),然后通过node(index)方法获取指定索引位置的节点,最后调用unlink方法移除该节点并返回其存储的元素。

E unlink(Node<E> x) {final E element = x.item;final Node<E> next = x.next;final Node<E> prev = x.prev;if (prev == null) {first = next;} else {prev.next = next;x.prev = null;}if (next == null) {last = prev;} else {next.prev = prev;x.next = null;}x.item = null;size--;modCount++;return element;
}

unlink方法通过调整节点之间的引用关系,将指定节点从链表中移除。它先保存要移除节点的元素值、后继节点和前驱节点,然后根据前驱和后继节点的情况更新链表的头节点first或尾节点last,以及相关节点的前驱和后继引用。最后将被移除节点的元素值置为null,更新元素数量size和修改次数modCount,并返回被移除的元素。

移除指定元素的第一个匹配项

remove(Object o)方法用于移除链表中指定元素的第一个匹配项。

public boolean remove(Object o) {if (o == null) {for (Node<E> x = first; x != null; x = x.next) {if (x.item == null) {unlink(x);return true;}}} else {for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item)) {unlink(x);return true;}}}return false;
}

该方法通过遍历链表,分别处理要移除的元素为null和不为null的情况。找到匹配的元素后,调用unlink方法将其移除并返回true;如果遍历完链表都没有找到匹配元素,则返回false

五、元素查找操作

查找指定元素首次出现的索引

indexOf(Object o)方法用于返回指定元素在链表中首次出现的索引,如果不存在则返回 -1。

public int indexOf(Object o) {int index = 0;if (o == null) {for (Node<E> x = first; x != null; x = x.next) {if (x.item == null)return index;index++;}} else {for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item))return index;index++;}}return -1;
}

该方法从链表头部开始遍历,分别处理查找元素为null和不为null的情况,找到匹配元素时返回其索引,遍历完链表都未找到则返回 -1。

查找指定元素最后一次出现的索引

lastIndexOf(Object o)方法用于返回指定元素在链表中最后一次出现的索引,如果不存在则返回 -1。

public int lastIndexOf(Object o) {int index = size;if (o == null) {for (Node<E> x = last; x != null; x = x.prev) {index--;if (x.item == null)return index;}} else {for (Node<E> x = last; x != null; x = x.prev) {index--;if (o.equals(x.item))return index;}}return -1;
}

该方法从链表尾部开始遍历,分别处理查找元素为null和不为null的情况,找到匹配元素时返回其索引,遍历完链表都未找到则返回 -1。

通过对LinkedList底层源码的剖析,我们清楚地了解了它的结构和各种操作的实现原理。LinkedList在插入和删除元素时具有高效性,尤其是在链表中间位置进行操作时,不需要像ArrayList那样进行大量元素的移动。然而,由于其基于链表结构,随机访问元素的时间复杂度较高,需要遍历链表来查找指定位置的元素。因此,在实际开发中,我们应根据具体的需求和操作场景,合理选择使用LinkedList或其他集合类,以达到最佳的性能和功能实现。

相关文章:

Java 中 LinkedList 的底层源码

在 Java 的集合框架中&#xff0c;LinkedList是一个独特且常用的成员。它基于双向链表实现&#xff0c;与数组结构的集合类如ArrayList有着显著差异。深入探究LinkedList的底层源码&#xff0c;有助于我们更好地理解其工作原理和性能特点&#xff0c;以便在实际开发中做出更合适…...

使用服务器部署DeepSeek-R1模型【详细版】

文章目录 引言deepseek-r1IDE或者终端工具算力平台体验deepseek-r1模型总结 引言 在现代的机器学习和深度学习应用中&#xff0c;模型部署和服务化是每个开发者面临的重要任务。无论是用于智能推荐、自然语言处理还是图像识别&#xff0c;如何高效、稳定地将深度学习模型部署到…...

k8s,1.修改容器内主机名和/etc/hosts 文件,2.root特权容器,3.pod安全策略(基于名称空间

1.修改容器内主机名和/etc/hosts 文件,让持久生效,通过修改资源清单方式---kind: PodapiVersion: v1metadata:name: rootspec:hostname: myhost # 修改主机名hostAliases: # 修改 /etc/hosts- ip: 192.168.88.240 # IP 地址hostnames: # 名…...

MSPFN 代码复现

1、环境配置 conda create -n MSPFN python3.9 conda activate MSPFN pip install opencv-python pip install tensorflow pip install tqdm pip install matplotlib2、train 2.1 创建数据集 2.1.1 数据集格式 |--rainysamples |--file1&#xff1a; |--file2:|--fi…...

除了console.error,还有什么更好的错误处理方式?

除了 console.error,在 Vue 应用中进行更好的错误处理可以采用以下几种方式: 一、使用全局错误处理 Vue 的错误捕获在 Vue 2 中,可以使用 errorHandler 来捕获全局的错误: Vue.config.errorHandler = (err, vm, info) => {// 处理错误,例如记录日志logError(err, info…...

力扣.270. 最接近的二叉搜索树值(中序遍历思想)

文章目录 题目描述思路复杂度Code 题目描述 思路 遍历思想(利用二叉树的中序遍历) 本题的难点在于可能存在多个答案&#xff0c;并且要返回最小的那一个&#xff0c;为了解决这个问题&#xff0c;我门则要利用上二叉搜索树中序遍历为有序序列的特性&#xff0c;具体到代码中&a…...

Yageo国巨的RC系列0402封装1%电阻库来了

工作使用Cadence多年&#xff0c;很多时候麻烦的就是整理BOM&#xff0c;因为设计原理图的时候图省事&#xff0c;可能只修改value值和封装。 但是厂家&#xff0c;规格型号&#xff0c;物料描述等属性需要在最后的时候一行一行的修改&#xff0c;繁琐又容易出错&#xff0c;过…...

wait/notify/join/设计模式

JUC wait obj.wait() 让进入 object 监视器的线程到 waitSet 等待wait&#xff08;&#xff09;方法会释放对象的锁&#xff0c;进入 WaitSet 等待区&#xff0c;从而让其他线程就机会获取对象的锁。无限制等待&#xff0c;直到 notify 为止wait(long n&#xff09;有时限的等…...

Windows Docker笔记-Docker拉取镜像

通过在前面的章节《安装docker》中&#xff0c;了解并安装成功了Docker&#xff0c;本章讲述如何使用Docker拉取镜像。 使用Docker&#xff0c;主要是想要创建并运行Docker容器&#xff0c;而容器又要根据Docker镜像来创建&#xff0c;那么首当其冲&#xff0c;必须要先有一个…...

七大排序思想

目录 七大排序的时间复杂度和稳定性 排序 插入排序 简单插入排序 希尔排序 选择排序 简单选择排序 堆排序 交换排序 冒泡排序 快速排序 快排的递归实现 hoare版本的快排 挖坑法的快排 双指针法的快排 快排的非递归 归并排序 归并的递归实现 归并的非递归实现…...

intra-mart实现简易登录页面笔记

一、前言 最近在学习intra-mart框架&#xff0c;在此总结下笔记。 intra-mart是一个前后端不分离的框架&#xff0c;开发时主要用的就是xml、html、js这几个文件&#xff1b; xml文件当做配置文件&#xff0c;html当做前端页面文件&#xff0c;js当做后端文件&#xff08;js里…...

SpringBoot整合RocketMQ

前言 在当今快速发展的软件开发领域&#xff0c;构建高效、稳定的应用系统是每个开发者的追求。Spring Boot 作为一款极具影响力的开发框架&#xff0c;凭借其强大的自动化配置和便捷的开发特性&#xff0c;极大地简化了项目搭建过程。使用 Spring Boot&#xff0c;我们无需再…...

深入理解 YUV Planar 和色度二次采样 —— 视频处理的核心技术

深入理解 YUV Planar 和色度二次采样 —— 视频处理的核心技术 在现代视频处理和编码中,YUV 颜色空间和**色度二次采样(Chroma Subsampling)**是两个非常重要的概念。它们的结合不仅能够显著减少视频数据量,还能在保持较高视觉质量的同时优化存储和传输效率。而 YUV Plana…...

项目顺利交付,几个关键阶段

年前离放假还有10天的时候&#xff0c;来了一个应急项目&#xff0c; 需要在放假前一天完成一个演示版本的项目&#xff0c;过年期间给甲方领导看。 本想的最后几天摸摸鱼&#xff0c;这么一来&#xff0c;非但摸鱼不了&#xff0c;还得加班。 还在虽然累&#xff0c;但也是…...

第七天 开始学习ArkTS基础,理解声明式UI编程思想

学习 ArkTS 的声明式 UI 编程思想是掌握 HarmonyOS 应用开发的核心基础。以下是一份简洁高效的学习指南&#xff0c;帮助你快速入门&#xff1a; 一、ArkTS 声明式 UI 核心思想 数据驱动 UI f(state)&#xff1a;UI 是应用状态的函数&#xff0c;状态变化自动触发 UI 更新。单…...

windows C++ Fiber (协程)

协程&#xff0c;也叫微线程&#xff0c;多个协程在逻辑上是并发的&#xff0c;实际并发由用户控件。 在windows上引入了纤程(fiber)。 WinBase.h 中函数原型 #if(_WIN32_WINNT > 0x0400)// // Fiber begin //#pragma region Application Family or OneCore Family or Game…...

游戏引擎学习第89天

回顾 由于一直没有渲染器&#xff0c;终于决定开始动手做一个渲染器&#xff0c;虽然开始时并不确定该如何进行&#xff0c;但一旦开始做&#xff0c;发现这其实是正确的决定。因此&#xff0c;接下来可能会花一到两周的时间来编写渲染器&#xff0c;甚至可能更长时间&#xf…...

2025新鲜出炉--前端面试题(一)

文章目录 1. vue3有用过吗, 和vue2之间有哪些区别2. vue-router有几种路由, 分别怎么实现3. webpack和rollup这两个什么区别, 你会怎么选择4. 你能简单介绍一下webpack项目的构建流程吗5. webpack平时有手写过loader和plugin吗6. webpack这块你平时做过哪些优化吗&#xff1f;7…...

教程 | i.MX RT1180 ECAT_digital_io DEMO 搭建(一)

本文介绍 i.MX RT1180 EtherCAT digital io DEMO 搭建&#xff0c;Master 使用 TwinCAT &#xff0c;由于步骤较多&#xff0c;分为上下两篇&#xff0c;本文为第一篇&#xff0c;主要介绍使用 TwinCAT 控制前的一些准备。 原厂 SDK 提供了 evkmimxrt1180_ecat_examples_digit…...

Pyecharts系列课程04——折线图/面积图(Line)

本章我们学习在Pyecharts中折线图&#xff08;Line&#xff09;的使用。折线图通用应用于数据的趋势分析。 折线图 我们现在有两组数据&#xff0c;x_data是2024年的月份&#xff0c;y_data为对应张三甲每个月的用电量。 # 家庭每月用电量趋势 x_data ["1月", &q…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...

[ACTF2020 新生赛]Include 1(php://filter伪协议)

题目 做法 启动靶机&#xff0c;点进去 点进去 查看URL&#xff0c;有 ?fileflag.php说明存在文件包含&#xff0c;原理是php://filter 协议 当它与包含函数结合时&#xff0c;php://filter流会被当作php文件执行。 用php://filter加编码&#xff0c;能让PHP把文件内容…...

MySQL的pymysql操作

本章是MySQL的最后一章&#xff0c;MySQL到此完结&#xff0c;下一站Hadoop&#xff01;&#xff01;&#xff01; 这章很简单&#xff0c;完整代码在最后&#xff0c;详细讲解之前python课程里面也有&#xff0c;感兴趣的可以往前找一下 一、查询操作 我们需要打开pycharm …...