JDK9.0 LinkedList源码阅读记录

2024-06-15 01:08
文章标签 源码 记录 阅读 linkedlist jdk9.0

本文主要是介绍JDK9.0 LinkedList源码阅读记录，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

概述

LinkedList继承体系
java.lang.Objectjava.util.AbstractCollection<E>java.util.AbstractList<E>java.util.AbstractSequentialList<E>java.util.LinkedList<E>
LinkedList定义
public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable

说明：
１．LinkedList是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
３．LinkedList 实现 List 接口，能进行队列操作。
４．LinkedList 实现Deque接口，即能将LinkedList当作双端队列使用。
５．LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
６．LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
７．LinkedList 是非同步的。
８．ArrayList底层是由数组支持，而LinkedList是由双向链表实现的，其中的每个对象包含数据的同时还包含指向链表中前一个与后一个元素的引用。

LinkedList方法

public LinkedList();//无参构造器
public LinkedList(Collection<? extends E> c) ;//构造器，以集合c创建LinkedList对象
void linkLast(E e);//给linkFirst的添加last节点添加元素
void linkBefore(E e, Node<E> succ);//在节点succ之前插入元素　
private E unlinkFirst(Node<E> f);//移除节点，用于移除首节点
private E unlinkLast(Node<E> l);//移除节点，用于移除尾节点
E unlink(Node<E> x);//移除x节点
public E getFirst();//获取首节点
public E getLast() ;//获取尾节点
public E removeFirst();//移除首节点
public E removeLast();//移除尾节点 
public void addFirst(E e) ;//添加元素作为首节点
public void addLirst(E e) ;//添加元素作为尾节点
public boolean contains(Object o);//判断是否包含对象o
public int size();//获取当前的包含的元素数量
public boolean add(E e);//添加元素
public boolean remove(Object o);//移除对象
public boolean addAll(Collection<? extends E> c) ;//添加集合c的所有元素
public boolean addAll(int index, Collection<? extends E> c);//在index处　添加集合c的所有元素 
public E get(int index) ;//获取索引为index的元素．．．．．．等
源代码分析
单向链表和双向链表

这里写图片描述
这里写图片描述
这里写图片描述
这里写图片描述
双向链表添加节点
单向链表(单链表)是链表的一种，它由节点组成，每个节点都包含下一个节点的引用。
双向链表(双链表)是链表的一种。和单链表一样，双链表也是由节点组成，它的每个数据结点中都有两个引用指向前后节点，分别指向直接前驱和直接后继。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

LinkedList节点

一个节点包含了元素值，前驱引用和后置引用，可以很方面的找到前后节点．

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 int size = 0;  //元素的数量
transient Node<E> first;　//指向第一个节点
transient Node<E> last;//指向末尾节点
添加节点

可以看出，添加节点时，只是改变节点的next和prev指向即可，因此效率很高

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++;
}
void linkBefore(E e, Node<E> succ) {// assert succ != null;final Node<E> pred = succ.prev;final Node<E> newNode = new Node<>(pred, e, succ);succ.prev = newNode;if (pred == null)first = newNode;elsepred.next = newNode;size++;modCount++;
}
删除节点

可以看出，删除节点时，只是改变节点的next和prev指向即可，因此效率很高

 E unlink(Node<E> x) {// 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 {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;
}
查找／删除／设置指定位置的节点元素

LinkedList是链表，不能直接使用索引进行查询，需要进行遍历，其使用的是二分查找，但是只用了一次．如果一直使用二分查找，效率会提高很多．

Node<E> node(int index) {// assert isElementIndex(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;}}
迭代器

有两个迭代器Iterator和ListIterator，使用其来对元素进行遍历
两个的实现类都是实现了Iterator接口．
从以下可以看出ListIterator提供的功能更多．
Iterator

public boolean hasNext()
public E next() 
public void remove()

ListIterator

public boolean hasNext();//是否还存在后节点
public E next();//获取当前的元素值
public boolean hasPrevious();//是否存在前节点
public E previous();//获取当前的元素值
public int nextIndex();//获取当前迭代的索引
public int previousIndex();//获取当前迭代的索引
public void remove();//移除元素
public void set(E e) ;//设置当前迭代到元素
public void add(E e);//添加元素至末节点

总结

  1. 与ＡrrayList相比，ＡrrayList的数据结构是动态数组,LinkedList的数据结构是双向链表．
  2. LinkedList也可以通过索引进行定位，但是其是通过遍历来进行定位，效率较低，而且只使用了一次二分法．
  3. LinkedList没有进行同步处理，因此会存在线程不安全性，使用时需要注意．
  4. 可以使用迭代器进行访问．　
  5. 实现clone方法，可以被拷贝．
  6. 可以被序列化 ．
  7. 相比于 ＡrrayList，保存同等的数据量的情况下，LinkedList所占用的空间更大，因为每个节点都要保存前后节点的引用．
  8. LinkedList的效率请看这里ArrayList和LinkedList性能比较

相关文章

JDK9.0 ArrayList源码阅读记录
JDK9.0 LinkedList源码阅读记录
ArrayList和LinkedList性能比较
JDK9.0 Vector源码阅读记录
JDK9.0 Hashtable源码阅读记录
Java9.0 HashMap源码阅读记录
JDK9.0 HashSet源码阅读记录

这篇关于JDK9.0 LinkedList源码阅读记录的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1062006。

相关文章

JAVA智听未来一站式有声阅读平台听书系统小程序源码

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来，一站式有声阅读平台听书系统 🌟&nbsp;开篇：遇见未来，从“智听”开始 在这个快节奏的时代，你是否渴望在忙碌的间隙，找到一片属于自己的宁静角落？是否梦想着能随时随地，沉浸在知识的海洋，或是故事的奇幻世界里？今天，就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统，它正悄悄改变着我们的阅读方式，让未来触手可及！ 📚&nbsp;第一站：海量资源，应有尽有 走进“智听
阅读更多...
Java ArrayList扩容机制 （源码解读）

Java ArrayList扩容机制 （源码解读）

结论：初始长度为10，若所需长度小于1.5倍原长度，则按照1.5倍扩容。若不够用则按照所需长度扩容。 一. 明确类内部重要变量含义         1：数组默认长度         2:这是一个共享的空数组实例，用于明确创建长度为0时的ArrayList ，比如通过 new ArrayList<>(0)，ArrayList 内部的数组 elementData 会指向这个 EMPTY_EL
阅读更多...
如何在Visual Studio中调试.NET源码

如何在Visual Studio中调试.NET源码

今天偶然在看别人代码时，发现在他的代码里使用了Any判断List<T>是否为空。 我一般的做法是先判断是否为null，再判断Count。 看了一下Count的源码如下： 1 [__DynamicallyInvokable]2 public int Count3 {4 [__DynamicallyInvokable]5 get
阅读更多...
工厂ERP管理系统实现源码（JAVA）

工厂ERP管理系统实现源码（JAVA）

工厂进销存管理系统是一个集采购管理、仓库管理、生产管理和销售管理于一体的综合解决方案。该系统旨在帮助企业优化流程、提高效率、降低成本，并实时掌握各环节的运营状况。 在采购管理方面，系统能够处理采购订单、供应商管理和采购入库等流程，确保采购过程的透明和高效。仓库管理方面，实现库存的精准管理，包括入库、出库、盘点等操作，确保库存数据的准确性和实时性。 生产管理模块则涵盖了生产计划制定、物料需求计划、
阅读更多...
Node.js学习记录（二）

Node.js学习记录（二）

目录 一、express 1、初识express 2、安装express 3、创建并启动web服务器 4、监听 GET&POST 请求、响应内容给客户端 5、获取URL中携带的查询参数 6、获取URL中动态参数 7、静态资源托管 二、工具nodemon 三、express路由 1、express中路由 2、路由的匹配 3、路由模块化 4、路由模块添加前缀 四、中间件
阅读更多...
论文阅读笔记: Segment Anything

论文阅读笔记: Segment Anything

文章目录 Segment Anything摘要引言任务模型数据引擎数据集负责任的人工智能 Segment Anything Model图像编码器提示编码器mask解码器解决歧义损失和训练 Segment Anything 论文地址: https://arxiv.org/abs/2304.02643 代码地址:https://github.com/facebookresear
阅读更多...
Spring 源码解读：自定义实现Bean定义的注册与解析

Spring 源码解读：自定义实现Bean定义的注册与解析

引言 在Spring框架中，Bean的注册与解析是整个依赖注入流程的核心步骤。通过Bean定义，Spring容器知道如何创建、配置和管理每个Bean实例。本篇文章将通过实现一个简化版的Bean定义注册与解析机制，帮助你理解Spring框架背后的设计逻辑。我们还将对比Spring中的BeanDefinition和BeanDefinitionRegistry，以全面掌握Bean注册和解析的核心原理。
阅读更多...
记录每次更新到仓库 —— Git 学习笔记 10

记录每次更新到仓库 —— Git 学习笔记 10

记录每次更新到仓库 文章目录 文件的状态三个区域检查当前文件状态跟踪新文件取消跟踪（un-tracking）文件重新跟踪（re-tracking）文件暂存已修改文件忽略某些文件查看已暂存和未暂存的修改提交更新跳过暂存区删除文件移动文件参考资料 咱们接着很多天以前的 取得Git仓库 这篇文章继续说。 文件的状态 不管是通过哪种方法，现在我们已经有了一个仓库，并从这个仓
阅读更多...
音视频入门基础：WAV专题（10）——FFmpeg源码中计算WAV音频文件每个packet的pts、dts的实现

音视频入门基础：WAV专题（10）——FFmpeg源码中计算WAV音频文件每个packet的pts、dts的实现

一、引言 从文章《音视频入门基础：WAV专题（6）——通过FFprobe显示WAV音频文件每个数据包的信息》中我们可以知道，通过FFprobe命令可以打印WAV音频文件每个packet（也称为数据包或多媒体包）的信息，这些信息包含该packet的pts、dts： 打印出来的“pts”实际是AVPacket结构体中的成员变量pts，是以AVStream->time_base为单位的显
阅读更多...
kubelet组件的启动流程源码分析

kubelet组件的启动流程源码分析

概述 摘要: 本文将总结kubelet的作用以及原理，在有一定基础认识的前提下，通过阅读kubelet源码，对kubelet组件的启动流程进行分析。 正文 kubelet的作用 这里对kubelet的作用做一个简单总结。 节点管理 节点的注册 节点状态更新 容器管理(pod生命周期管理) 监听apiserver的容器事件 容器的创建、删除(CRI) 容器的网络的创建与删除
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2