LinkedList接口源码解读

LinkedList 接口源码解读（一）

前言

因为追求质量，所以写的较慢。大概在接下来的三天内会把LinkedList源码解析出完。大概还有两篇文章。废话不多说，正片开始！

大家都知道，LinkedList是在Java底层中是由 双向链表 实现的。那么今天我们就来阅读下源码，看看Java是如何实现这个功能强大的集合。

注意： JDK1.6 之前为双向循环链表，JDK1.7 取消了循环，只使用了双向链表。

首先，我们看一下LinkedList类定义

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, Serializable {// transient 关键字表示被该关键字修饰的属性不会被序列化。transient int size;transient Node<E> first;transient Node<E> last;private static final long serialVersionUID = 876323262645176354L;
}

一. 继承和实现关系

LinkedList 类继承了 AbstractSequentialList ，而AbstractSequentialList 又继承了 AbstractList 。

  • 我们知道 ArrayList也继承了AbstractList ，所以LinkedList中的大部分方法会和ArrayList相似。

LinkedList类实现了List、Deque 、Cloneable、Serializable 接口。

  • List ： **表明它是一个列表，支持添加、删除、查找等操作，并且可以通过下标进行访问。 **

  • Deque ： 继承自 Queue 接口，具有双端队列的特性，支持从两端插入和删除元素，方便实现栈和队列等数据结构。

  • Cloneable ：Cloneable 注解是一个标记接口，我们点进去会发现它并没有任何方法。此接口表明LinkedList具有拷贝能力，可以进行深拷贝或浅拷贝操作 。

    package java.lang;public interface Cloneable {
}

  • Serializable : 表明它可以进行序列化操作，也就是可以将对象转换为字节流进行持久化存储或网络传输，非常方便。
    在这里插入图片描述

二、属性实现

LinkedList 中的元素属性是通过 Node 类来声明的：

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

三、初始化

在进入正题之前，我先来给各位科普下 transient 关键字的作用是什么？

相信大家在阅读源码的过程中，很多属性的定义前都会加transient关键字。

  • transient是Java语言的关键字，用来表示一个成员变量不是该对象序列化的一部分。当一个对象被序列化的时候，transient所修饰的变量的值不包括在序列化的结果中。
transient int size;  // 链表节点的个数，默认为 0
transient Node<E> first;  // 指向链表的第一个节点
transient Node<E> last;  // 指向链表的最后一个节点
private static final long serialVersionUID = 876323262645176354L;// 无参构造方法，调用此构造方法创建的集合长度默认为 0
public LinkedList() {this.size = 0;
}// 有参构造方法，传入一个集合类型作为参数，会创建一个与传入集合相同元素的链表对象
public LinkedList(Collection<? extends E> c) {this();this.addAll(c);
}

在调用有参构造方法时，LinkedList会调用两个方法this()、addAll()。

  • this()：调用有参构造的时候，首先会去调用无参构造，创建一个默认大小为 0 的集合。

  • addAll()：底层就是将传过来的集合类型转换成 Object[]数组，然后依次遍历数组中的每个元素，添加到链表上。

源码：

// 将集合类型保存到链表中
public boolean addAll(Collection<? extends E> c) {// 底层调用了重载后的 addAll(int index, Collection<? extends E> c)  return this.addAll(this.size, c);  // 等同于 return this.addAll(0, c);
}

// addAll() 最终实现类
public boolean addAll(int index, Collection<? extends E> c) {// 索引越界检查，条件为：index >= 0 && index <= this.size// 满足条件返回true，否则报错this.checkPositionIndex(index);Object[] a = c.toArray();  // 转换成 Object[]int numNew = a.length;// 非空校验if (numNew == 0) {return false;} else {// 核心逻辑！！// pred 可以理解为记录节点位置的指针。每有一个新节点就会更新 pred 的值// succ 是一个标记节点，循环结束后会判断当前 succ 是否为 nullNode pred;  Node succ;if (index == this.size) {  // 调用有参构造方法时，size = 0 并且 index = 0，所以会进入下方的逻辑succ = null;pred = this.last;  // 此时，链表为空，所以 last = null。可以转换成 pred = null} else {succ = this.node(index);pred = succ.prev;}Object[] var7 = a;int var8 = a.length;// 循环数组，依次往链表中添加元素for(int var9 = 0; var9 < var8; ++var9) {Object o = var7[var9];  // 取出指定索引的值E e = o;// LinkedList 底层是由双向链表实现的// 此语句的意思为：创建一个前缀指针指向 pred，值为 e，后缀指针指向 null 的新节点Node<E> newNode = new Node(pred, e, (Node)null);if (pred == null) {  // 第一次循环时 pred 肯定为 null，进入下方逻辑// 表明当前 newNode 是链表的第一个节点// 设置 LinkedList 的 first 指针指向此新节点this.first = newNode;  } else {  // 除了第一次进入循环，后面的每次循环都会进下方逻辑// 依次往链表中添加元素 1 -> 2 -> 3pred.next = newNode;}// 更新 pred 的值pred = newNode;}if (succ == null) {// 此时的 pred 节点是当前链表的最后一个值// 设置 LinkedList 的 last 指针指向此循环结束后的最后一个 pred 节点this.last = pred;  } else {pred.next = succ;succ.prev = pred;}// 无关操作  更新链表中的节点数// size 是链表所用来记录当前节点值的// modCount 是 List 集合存储元素个数的值// 因为 LinkedList 继承了 AbstractSequentialList，所以 List 的操作它也都有this.size += numNew;++this.modCount;return true;}}

四、插入元素

LinkedList 除了实现了 List 接口相关方法，还实现了 Deque 接口的很多方法，所以我们有很多种方式插入元素。

下面我将以 List 、Queue、Stack这三种数据结构分开带大家阅读源码。

可能会有朋友好奇，Stack是什么？Stack是栈这种数据结构，他的特点是只有一端能进出，这就导致栈的特点是先进后出，这和队列Queue的先进后出恰好相反

那朋友们又要好奇了，LinkedList在他的类方法定义上也没看到一个叫 Stack的接口啊，它怎么能当作栈呢？

大家要记住，数据结构底层都是相通的。栈有多种实现方式，可以通过单向链表实现栈、数组实现栈、双向链表实现栈，而 LinkedList正是通过双向链表来实现了对栈的操作

/*** 为了让大家能够明白上面那句话的意思，我用单向链表实现了一个栈，各位可以看看代码* @Description 单向链表实现栈* @Author Mr.Zhang* @Date 2024/8/2 14:40* @Version 1.0*/
public class LinkedListStack<E> implements Iterable<E> {// 容量private int capacity;private int size;  // 栈中元素的个数// 头指针指向哨兵节点private Node<E> head = new Node<>(null, null);public LinkedListStack(int capacity) {this.capacity = capacity;}static class Node<E> {E value;Node<E> next;public Node(E value, Node<E> next) {this.value = value;this.next = next;}}/*** 向栈顶压入元素** @param value 待压入值* @return 压入成功返回 true，否则返回 false*/@Overridepublic boolean push(E value) {if (isFull()) {return false;}head.next = new Node<E>(value, head.next);size++;return true;}/*** 从栈顶弹出元素** @return 栈非空返回栈顶元素，栈为空返回 null*/@Overridepublic E pop() {if (isEmpty()) {return null;}E value = head.next.value;head.next = head.next.next;size--;return value;}/*** 返回栈顶元素，不弹出** @return 栈非空返回栈顶元素，栈为空返回 null*/@Overridepublic E peek() {if (isEmpty()) {return null;}return head.next.value;}/*** 检查栈是否为空** @return  空返回 true，否则返回 false*/@Overridepublic boolean isEmpty() {return head.next == null;}/*** 检查栈是否已满** @return 满了返回 true，否则返回 false*/@Overridepublic boolean isFull() {return capacity == size;}/*** 方便我用 增强for循环 测试*/@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {Node<E> p = head.next;@Overridepublic boolean hasNext() {return p != null;}@Overridepublic E next() {E value = p.value;p = p.next;return value;}};}
}
  • List
    • add(E e) ： 用于在 LinkedList 的尾部插入元素，即将新元素作为链表的最后一个元素，时间复杂度为 O(1)。
    • addAll(int index, Collection<? extends E> c)：用于通过给定的集合类型数据创建一个LinkedList。 (此源码已经在上面了，下方不重复解读)
    • add(int index, E element)：用于在指定位置插入元素。这种插入方式需要先移动到指定位置，再修改指定节点的指针完成插入/删除，因此需要移动平均 n/2 个元素，时间复杂度为 O(n)。

源码：

// 在 LinkedList 尾部添加元素
public boolean add(E e) {this.linkLast(e);return true;
}// 向 LinkedList 尾部添加元素的底层实现方法
void linkLast(E e) {Node<E> l = this.last;  // 获取最后一个节点// 根据传入的 e 创建新节点，新节点的前一个指针指向之前链表的最后一个节点Node<E> newNode = new Node(l, e, (Node)null);  this.last = newNode;  // 更新新节点的值if (l == null) {  // 判断如果当前链表为空this.first = newNode;  // 则将 LinkedList 的 last 指针也指向这个新节点} else {l.next = newNode; // 更新 l 的 next 指向的节点}// 无关操作  更新链表中的节点数++this.size;++this.modCount;
}// 根据指定的索引插入元素
public void add(int index, E element) {// 索引越界检查，条件为：index >= 0 && index <= this.size// 满足条件返回true，否则报错this.checkPositionIndex(index);if (index == this.size) {  // 如果传递过来的 index 正好等于数组长度，则证明是向链表最后添加元素this.linkLast(element);} else {// 核心代码this.linkBefore(element, this.node(index));  // this.node(index)：找到待插入索引目前存在的节点元素}
}// 根据指定的索引插入元素的底层实现方法
void linkBefore(E e, Node<E> succ) {// 定义一个节点元素保存 succ 的 prev，也就是它的前一节点信息Node<E> pred = succ.prev;// 初始化节点，并指明前驱和后继节点Node<E> newNode = new Node<>(pred, e, succ);// 将 succ 节点前驱引用 prev 指向新节点succ.prev = newNode;// 判断前驱节点是否为空，为空表示 succ 是第一个节点if (pred == null) {this.first = newNode;  // 当前 newNode 节点就是新的首节点，所以要让 first 指向 newNode} else {pred.next = newNode;}// 无关操作  更新链表中的节点数++this.size;++this.modCount;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/390775.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

手机上音乐如何转换成MP3格式？分享5款音频格式转换APP

手机上音乐如何转换成MP3格式？分享5款音频格式转换APP

手机上音乐如何转换成MP3格式&#xff1f;相信很多外出办公或者不经常使用电脑的工作人士&#xff0c;学生党&#xff0c;媒体从业者都有这样的疑惑和需求。不同设备和应用可能支持不同的音频格式&#xff0c;导致某些情况下需要将音乐文件转换为MP3格式以确保兼容性。下面&…
阅读更多...
操作系统|day4.Linux、Linux内核、Linux负载、Linux文件存储

操作系统|day4.Linux、Linux内核、Linux负载、Linux文件存储

文章目录 LinuxLinux内核定义功能态 Linux负载定义 Linux文件存储链接分类区别使用场景 拷贝 Linux Linux内核 定义 内核是操作系统的核心&#xff0c;具有很多最基本功能&#xff0c;它负责管理系统的进程、内存、设备驱动程序、文件和网络系统&#xff0c;决定着系统的性能…
阅读更多...
.NET周刊【7月第4期 2024-07-28】

.NET周刊【7月第4期 2024-07-28】

国内文章 .NET 高性能缓冲队列实现 BufferQueue https://mp.weixin.qq.com/s/fUhJpyPqwcmb3whuV3CDyg BufferQueue 是一个用 .NET 编写的高性能的缓冲队列实现&#xff0c;支持多线程并发操作。 项目地址&#xff1a;https://github.com/eventhorizon-cli/BufferQueue 项目…
阅读更多...
【虚拟仿真】Unity3D中实现2DUI显示在3D物体旁边

【虚拟仿真】Unity3D中实现2DUI显示在3D物体旁边

推荐阅读 CSDN主页GitHub开源地址Unity3D插件分享简书地址QQ群：398291828大家好，我是佛系工程师☆恬静的小魔龙☆，不定时更新Unity开发技巧，觉得有用记得一键三连哦。 一、前言 这篇文章来实现2DUI显示在3D物体旁边，当我们需要在3D模型旁边显示2DUI的时候，比如人物的对…
阅读更多...
grep工具的使用

grep工具的使用

grep [options]…… pattern [file]…… 工作方式&#xff1a; grep 在一个或者多个文件中搜索字符串模板&#xff0c;如果模板中包括空格&#xff0c;需要使用引号引起来&#xff0c;模 板后的所有字符串会被看作是文件名。 工作结果&#xff1a;如果模板搜索成功&#xf…
阅读更多...
Springboot+Vue在线水果(销售)商城管理系统-附源码与配套论文

Springboot+Vue在线水果(销售)商城管理系统-附源码与配套论文

1.1 研究背景 互联网概念的产生到如今的蓬勃发展&#xff0c;用了短短的几十年时间就风靡全球&#xff0c;使得全球各个行业都进行了互联网的改造升级&#xff0c;标志着互联网浪潮的来临。在这个新的时代&#xff0c;各行各业都充分考虑互联网是否能与本行业进行结合&#xf…
阅读更多...
Java:进程和线程

Java:进程和线程

文章目录 进程线程的概念和区别总结如何创建线程1.继承Thread重写run2.实现Runnable重写run3.继承Thread重写run,通过匿名内部类来实现4. 实现Runnable重写run,通过匿名内部类来实现5.基于lambda表达式来创建 虚拟线程 并发编程: 通过写特殊的代码&#xff0c;把多个CPU核心都利…
阅读更多...
Shell编程 --基础语法（1）

Shell编程 --基础语法（1）

文章目录 Shell编程基础语法变量定义变量使用变量命令的使用只读变量删除变量 传递参数字符串获取字符串长度字符串截取 数组定义方式关联数组获取数组的长度 总结 Shell编程 Shell是一种程序设计语言。作为命令语言&#xff0c;它交互式解释和执行用户输入的命令或者自动地解…
阅读更多...
【人工智能基础三】卷积神经网络基础（CNN）

【人工智能基础三】卷积神经网络基础（CNN）

文章目录 1. 卷积神经网络结构2. 卷积神经网络计算2.1. 卷积层计算2.2. 池化层计算2.3. 全连接层计算 3. 典型卷积神经网络3.1. AlexNet3.2. VGGnet 卷积神经网络(Convolutional Neural Network&#xff0c;CNN)是一类包含卷积计算且具有深度结构的前馈神经网络(Feedforward Ne…
阅读更多...
计算机毕业设计Python+Tensorflow股票推荐系统 股票预测系统 股票可视化 股票数据分析 量化交易系统 股票爬虫 股票K线图 大数据毕业设计 AI

计算机毕业设计Python+Tensorflow股票推荐系统 股票预测系统 股票可视化 股票数据分析 量化交易系统 股票爬虫 股票K线图 大数据毕业设计 AI

1、用pycharm打开项目&#xff0c;一定要打开包含manage.py文件所在文件夹 2、配置解释器&#xff1a;建议使用Anaconda(Python 3.8(base))&#xff0c;低于3.8版本的&#xff0c;页面会不兼容 3、安装依赖库&#xff1a;打开pycharm的终端&#xff0c;输入&#xff1a; pip in…
阅读更多...
Docker-学习笔记(借助宝塔面板)

Docker-学习笔记(借助宝塔面板)

ubuntu环境 一、安装 可以参考官网进行或其他博客进行安装 1.进入宝塔面板 进图Docker菜单&#xff0c;查看是否提示安装。 2.查看是否安装 查看版本 docker -v 证明已经安装 二、常用命令 1.查看版本 docker -v 2.启动、停止、重启docker systemctl start docker…
阅读更多...
自制安卓车机软件（含APP）

自制安卓车机软件（含APP）

本软件使用APPinventor2编程软件&#xff0c;耗时5天和3天调试&#xff0c;具有高德导航&#xff0c;视频播放&#xff0c;网易云音乐&#xff0c;酷狗&#xff0c;抖音&#xff0c;&#xff08;需下载车机版软件&#xff09;和自定义添加软件&#xff0c;网页有哔哩哔哩&#…
阅读更多...
无人机工程师技术高级证书详解

无人机工程师技术高级证书详解

随着无人机技术的飞速发展&#xff0c;其在航拍、农业、测绘、救援、物流等多个领域的应用日益广泛&#xff0c;对无人机工程师的专业技能与综合素质提出了更高要求。无人机工程师技术高级证书&#xff0c;作为对无人机领域高级工程师专业技能的权威认证&#xff0c;不仅是对个…
阅读更多...
简单搭建dns服务器

简单搭建dns服务器

目录 一.安装服务 二.编写子配置文件 三.编写主配置文件 四.编写文件 五.测试 一.安装服务 [rootnode1 ~]# dnf install bind -y 二.编写子配置文件 [rootnode1 ~]# vim /etc/named.rfc1912.zones 三.编写主配置文件 [rootnode1 ~]# vim /etc/named.conf 四.编写文件 …
阅读更多...
【Python】Numpy概述安装及使用

【Python】Numpy概述安装及使用

文章目录 Numpy概述Numpy开发环境搭建Numpy使用创建数组创建一维数组创建二维数组创建三维数组&#xff0c;array()函数ndmin参数的使用array()函数dtype参数的使用随机数创建 Numpy概述 Numpy是科学计算基础库&#xff0c;提供大量科学计算相关功能&#xff0c;比如数据统计&…
阅读更多...
GuLi商城-商品服务-API-新增商品-调试会员等级相关接口

GuLi商城-商品服务-API-新增商品-调试会员等级相关接口

在网关服务中配置路由： 代码： nacos这些服务都要启动： 如果有不是一个命名空间中的，要改成同一个命名空间中 启动商品product服务遇到循环依赖问题，解决：
阅读更多...
Leetcode 第 135 场双周赛题解

Leetcode 第 135 场双周赛题解

Leetcode 第 135 场双周赛题解 Leetcode 第 135 场双周赛题解题目1&#xff1a;3222. 求出硬币游戏的赢家思路代码复杂度分析 题目2&#xff1a;3223. 操作后字符串的最短长度思路代码复杂度分析 题目3&#xff1a;3224. 使差值相等的最少数组改动次数思路代码复杂度分析 题目4…
阅读更多...
classical Chinese

classical Chinese

classical Chinese 中型娃娃暑假作业背诵 文言文《伯牙鼓琴》 1&#xff09;拿到文言文&#xff0c;先看一遍 2&#xff09;用白话文&#xff08;现代文&#xff09;翻译一次 3&#xff09;用白话文对照回去文言文&#xff08;白话文中那些需要替换回文言文呢&#xff09; 虽…
阅读更多...
神奇海洋养鱼小程序游戏广告联盟流量主休闲小游戏源码

神奇海洋养鱼小程序游戏广告联盟流量主休闲小游戏源码

在海洋养鱼小程序中&#xff0c;饲料、任务系统、系统操作日志、签到、看广告、完成喂养、每日签到、系统公告、积分商城、界面设计、拼手气大转盘抽奖以及我的好友等功能共同构建了一个丰富而互动的游戏体验。以下是对这些功能的进一步扩展介绍&#xff1a; 饲料 任务奖励&a…
阅读更多...
非对称加密：数据安全的双重保障

非对称加密：数据安全的双重保障

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023