JDK源码分析：LinkedList

发布于：2024-10-24 编辑：匿名来源：网络

1.背景我们先来了解一下腾讯混元模型，什么是“LinkedList”。下图是混元大模型的答案：代码语言：txt复制 LinkedList是Java集合框架中的一种数据结构，它实现了List和Deque接口。

LinkedList 是一个双向链表，这意味着每个元素都包含对前一个和下一个元素的引用。这种数据结构允许在列表的两端进行高效的插入和删除操作。

LinkedList 的主要特性：动态大小：与数组不同，LinkedList 的大小可以动态增长或缩小。高效的插入和删除：在 LinkedList 的开头、结尾或中间插入或删除元素时，不需要移动其他元素，因此这些操作通常比 ArrayList 执行得更快。

内存效率：LinkedList 在内存使用方面可能比 ArrayList 更高效，因为它不需要连续的内存空间来存储元素。访问速度：与ArrayList相比，LinkedList的随机访问速度较慢，因为需要从头或尾开始遍历链表才能找到特定位置的元素。

线程不安全：LinkedList 不是线程安全的。如果多个线程同时修改LinkedList，可能会导致数据不一致。

在多线程环境下，可以使用Collections.synchronizedList()方法将LinkedList包装成线程安全的列表，或者使用CopyOnWriteArrayList（虽然更适合读多写少的场景）。 2、源码分析 2.1 类定义代码语言：javascript copy public class LinkedList extends AbstractSequentialListimplements List, Deque, Cloneable, java.io.Serialized{} 源码分析：LinkedList继承AbstractSequentialListAbstractSequentialList 是Java集合框架中的一个抽象类，它实现了List接口，并提供了用于顺序访问列表元素的迭代器。

AbstractSequentialList 为希望以顺序方式访问其元素的列表提供了一个公共基础实现。 LinkedList 实现 List 接口：具有线性链表操作，如：size、isEmpty、contains、containsAlladd、addAll、removeAll、retainAll、clear、subListLinkedList 实现 Deque 接口：具有双向链表操作，如：addFirst、removeFirst、pollFirst 、getFirst、peekFirstaddLast、removeLast、pollLast、getLast、peekLast2.2 基本属性代码语言：javascript copytransient int size = 0;/** * 指向第一个节点的指针。

*/transient Node first;/** * 指向最后一个节点的指针。 */transient Node last;/** 修改次数*/protectedtransient int modCount = 0;源码分析：LinkedList有两个内置指针，包括头结点first和结束指针lastLinkedList。

尺寸也已定。标识有效元素的数量（不包括头节点和结束指针）。

LinkedList设置modCount来标识修改操作的次数。 modCount字段用于跟踪列表的结构修改次数，以确保在迭代过程中发生并发修改时能够快速失败。

直接触发异常ConcurrentModificationException2.3 基本操作：添加、删除、修改、检查（1）添加元素图片通过阅读源码，LinkedList有7种添加元素的方式，add(E e)：在末尾添加一个元素列表（默认添加在列表末尾，即尾部插入方式） add(int index, E element)：在指定位置插入一个元素。 addFirst(E e)：将一个元素添加到列表的开头。

addLast(E e)：将一个元素添加到列表末尾（与 add(E e) 相同）。 Push(E e)：将一个元素添加到列表的开头（与 addFirst(E e) 相同）。

addAll 的两个重载方法：批量插入元素并解析 add(E e) 方法源码语言： javascript copy public boolean add(E e) { linkLast(e); }返回 true;}void linkLast(E e) { Final Node l = last;最终 Node newNode = new Node<>(l, e, null);最后=新节点； if (l == null)first = newNode;否则 l.next = newNode;尺寸++； modCount++;}Node(Node 上一个, E 元素, Node 下一个) { this.item = element;这.下一个 = 下一个; this.prev = prev;}图片源码分析： linkLast(e) ：尾部插入方式创建新的Node节点：前驱指针指向last，当前数据为e，后继指针为空容量大小，个数修改次数（2）删除元素图片分析remove()方法源码源码分析：代码语言：javascript 复制 public E remove() { return removeFirst();} public E removeFirst() { Final Node f = first ; if (f == null) 抛出新的 NoSuchElementException(); return unlinkFirst(f);}private E unlinkFirst(Node f) { // 断言 f == first && f != null;最终E元素=f.item； // [1] 最终 Node next = f.next; // [2] f.它em = 空； // [3] f.next = null; // 帮助 GC // [4] 第一个 = 下一个; // [5] if (next == null) last = null; else // [6] next.prev = null; // [7] 大小--; modCount++； // [8] return element;} 源码分析：中间变量：next局部变量携带被删除节点的next指针（下一个元素地址），并被设置为被删除节点的item值为null。将被删除节点的next指针设置为null。

将第一个指针设置为下一个局部变量（下一个元素地址）。如果下一个局部变量为 null，则表示没有元素。

顺便说一句，将last设置为null。否则，设置下一个局部变量。

变量的前驱指针为空，因为下一个局部变量的元素对于头节点容量为-1，操作次数返回删除的数据 (3)修改元素图像并更新set()方法。源代码语言：javascript copy public E set(int index, E element) { // 【1】 checkElementIndex(index); // 【2】 Node x = node(index); // 【3】 E oldVal = x.item; //【4】x.item = 元素; // [5] return oldVal;}Node node(int index) { // 断言 isElementIndex(index); // [2.1] 右移操作，size/2 if (index < (size >> 1)) { // [2.2] Node x = first; // [2.3] 从头部开始遍历 for (int i = 0; i < index; i++) // [2.4]x = x.下一个； // [2.5] 返回 x; } else { // [2.6] 从末尾遍历 Node x = last; for (int i = size - 1; i > index; i-- ) // [2.7] x = x.prev; // [2.8] 返回 x; }}private void checkElementIndex(int ??index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}private boolean isElementIndex(int ??index) { return index >= 0 && index < size ;} 源码分析：检查元素是否合法。

如果不合法，则会抛出异常IndexOutOfBoundsException。通过遍历链表，得到元素地址。

计算要更新的索引下标。从第一个更新更接近，更接近最后，更接近第一个，从头部开始遍历，用for循环遍历，得到前一个元素的next指向的元素地址，距离最后更近，从尾部开始遍历，遍历用for循环，获取下一个元素 prev指向的元素地址获取更新前的值，更新新值，返回更新前的值 (4)获取元素图片，获取索引下标，get()方法源码语言：txt copy public E get(int index) { // [ 1】 checkElementIndex(index); // 【2】 return node(index).item;}private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}Node 节点(int index) { // 断言 isElementIndex(index); // [2.1] 右移操作，size/2 if (index < (size >> 1)) { // [2.2] Node< E> x = first; // [2.3] 从头开始??遍历 for (int i = 0; i < index; i++) // [2.4] x = x.next; // [2.5] 返回 x; } else { // [2.6] 从末尾遍历 Node x = last; for (int i = size - 1; i > index; i--) // [2.7] x = x.prev; // [2.8 return 下标，是靠近第一个还是靠近最后一个？已经比较接近第一了。

从头部开始遍历。使用for循环来遍历。

获取前一个元素的下一个所指向的元素地址。现在已经接近最后一次了。

从尾部开始遍历。使用 for 循环。

遍历得到下一个元素的prev指向的元素地址。 3.总结 LinkedList是一个双向链表，这意味着每个元素都包含对前一个和下一个元素的引用。

这种数据结构允许在列表的两端进行有效的处理。插入和删除操作。

3.1 ArrayList和LinkedList的比较。 ArrayList底层是基于动态数组实现的，LinkedList底层是基于链表实现的。

对于随机访问（get/set方法），ArrayList直接通过index定位到数组对应位置的节点，而LinkedList则需要从头节点或者尾节点开始遍历。，直到找到目标节点，所以ArrayList在效率上比LinkedList要好。

对于插入和删除（add/remove方法），ArrayList需要移动目标节点后面的节点（使用System.arraycopy方法移动节点），而LinkedList只需要修改目标节点的next或prev属性前后节点就够了，所以LinkedList在效率上比ArrayList要好。

站长声明

标签：

上一篇：【Git】Git Flow 工作原理

下一篇：Kubernetes 1.20.5构建nacos

深圳市金融机构环境信息披露指引

深圳市金融机构环境信息披露指引深圳金建发【】第37号第一章总则第一条是为了规范深圳市金融机构环境信息披露工作，提高环境质量。根据《信息披露指引》的有关规定，制定本指引。第二条本指引适用于本市从事金融业务的企业，包括银行业金融机构、保险金融机构、证券金融机

06-18
最高授信额度5亿！ “专特新贷”全面开花，地方政府与银行配合默契，

源网真金白银打“专特特新”贷款，这次河南走在了前列。 3月16日，河南推出全国首个专属政府参与风险补偿的金融产品“专特新贷”。不久前，河南刚刚公布20条措施，引导金融机构带动更多中小企业走“专精特新”发展道路。除河南外，安徽还鼓励银行业金融机构创设“专项新增贷

06-18
诚格生物已完成天使轮及Pre-A轮融资，融资总额达数千万元

据投资界11月8日消息，据亿欧报道，诚格生物宣布已完成完成天使轮及Pre-A轮融资。，融资总额达数千万元。据悉，天使轮融资由钟南山院士旗下产学研集群企业广州虎研所医药科技有限公司领投，杨浦湾创新创业孵化器跟投； Pre-A轮融资由三泽创投领投，光华创投跟投。目前两轮

06-18
三星将为特斯拉提供下一代自动驾驶芯片

近日，海外媒体报道称，特斯拉正在考虑生产成本、三星技术在特斯拉自家芯片设计中的可行性以及长期合作的可能性。在考虑了性因素等因素后，他决定与三星电子签约。据悉，特斯拉新款Hardware4计算机将与其即将推出的超现代皮卡Cyber??truck一同亮相，而三星将击败台积电获得

06-08
国产自动驾驶芯片如何应用在汽车上？ -甲子光年

今年将是大算力的自动驾驶芯片上市之年。作者 |赵健刘小倩自动驾驶普及正在加速。 1月12日，工信部发文称，年销售新能源汽车1万辆，其中20%的新增乘用车市场配备组合辅助驾驶系统。两年前，L2级辅助驾驶的普及率仅为3.3%。智能汽车的发展离不开汽车的大脑——自动驾驶芯

06-18
联想投资长江产业基金，持股9.7%

8月18日，有消息称长江产业基金发生工商变更，新增联想（北京）有限公司作为股东。同时，公司注册资本由2亿元增至30.4亿元，增长52%。股权渗透率显示，联想（北京）有限公司持有该公司9.7%的股份。长江产业基金成立于2001年，由湖北省财政出资1亿元人民币设立。通过与社会

06-18
和福老面完成近8亿元E轮融资，华人文化资本领投

据7月8日消息，国内餐饮领先品牌和福餐饮宣布完成近8亿元E轮融资。本轮融资由华人文化资本领投，新股东中为资本、老股东腾讯投资、龙湖资本跟投。不到一年时间，和福连续两次融资近13亿元，加速布局之势令人瞩目。禾富表示，本轮融资将主要用于全产业链体系的深度布局、新

06-18
管理规模突破1300亿，张坤一一季度大幅加仓医药、银行

今日，张坤管理的四只基金，分别是易方达中小盘、易方达蓝筹精选、易方达蓝筹精选、易方达基金基金优质企业三年持有、易方达亚洲精选发布。年度季度报告。截至一季度末，张坤管理规模已突破亿元。从行业配置来看，张坤一季度进一步均衡调整仓位，整体组合增加银行、生物医

06-18
中通二次IPO没你想象的那么简单

一直盛传赴港二次上市的中通快递（以下简称“中通”）终于官宣了！ 9月16日，中通通讯宣布拟在香港联交所主板全球发行股票上市。该计划是10,000股A类普通股全球发行和上市的一部分。预计募集资金达1亿港元（15.6亿美元，5700万元人民币）。此次公开发行将以港币最高价定价

06-18
超粮网获得数千万美元A轮融资，由物阅资本独家投资，

据投资界9月28日消息，超粮网宣布完成数千万美元A轮融资，由五岳资本独家投资。据悉，本轮融资将用于标准化仓储系统的建设以及IT系统的开发和升级。据了解，超粮网成立于2007年，目前服务会员超过2万名。截至年底，平台累计交易额突破1亿元，每年实现数千万的公司利润。

06-17
36岁女学术大师出炉热门单曲

杨璐菡是谁？就在日前，美国马里兰大学医学中心进行了一项开创性的工作。他们将猪心脏移植到57岁的患者大卫贝内特体内。手术三天后，患者的健康状况良好。这是人类数十年来追求利用动物器官移植拯救生命的重要一步。这与众多科学家人的共同努力密不可分。杨璐菡和他共同

06-18
二季度全球经济复苏有望超出预期，境外资本继续看好中国

二季度全球经济复苏有望超预期。外资持续看好中国。许多国家的疫苗接种速度正在加快。此外，财政措施仍在加大力度。一季度全球经济明显复苏。国际组织近期纷纷上调经济增长预期，中外机构普遍预计二季度全球经济复苏有望超预期。中国市场受到机构坚定青睐。渣打银行4月

06-18