Java 集合框架：LinkedList 的介绍、利用、原理与源码剖析

Java 集合框架：LinkedList 的介绍、使用、原理与源码剖析

Java 集合框架里包含多种用于数据存储和操作的类，LinkedList 是其中重要且常用的一个实现。作为一个双向链表，LinkedList 提供了高效的插入和删除操作，特别适用于频繁进行元素增删的场景。对很多开发者而言，吃透 LinkedList 的特性和工作原理，是提升代码性能、优化数据处理逻辑的关键。这篇从概述、与 ArrayList 的对比、核心源码思路三个角度讲清楚。

一、LinkedList 概述

LinkedList 是 List 接口的一个实现，本质上是一个双向链表。与 ArrayList 相比，LinkedList 的元素在内存中不是连续存放的。

它的每个元素（称为节点）都包含两部分数据：一部分是真正存储的数据，另一部分是指向前一个节点和后一个节点的链接（指针）。换句话说，链表里的每个节点都要额外背两个引用，这也是它在遍历和内存占用上不如 ArrayList 的根本原因。

二、LinkedList 的优点：增删只改指针

LinkedList 最大的优点在于插入和删除元素时效率很高。因为链表的数据结构使得它只需要修改前后节点的指针即可——插入一个元素，改两个引用；删除一个元素，也是改两个引用。这和 ArrayList 完全不同。

对比一下 ArrayList 的代价

ArrayList 底层是连续数组，往中间插入一个元素，这个位置之后的所有元素都要整体往后挪一位；容量不够时还要扩容重建数组。数组越大、插入位置越靠前，代价越大。

三、什么时候该用 LinkedList，什么时候不该

• 适合用 LinkedList：在队列、栈场景频繁在头尾增删元素（LinkedList 本身就是 Deque 的实现，addFirst / addLast / removeFirst / removeLast 都是 O(1)）；批量处理数据流时用迭代器边走边删。
• 不适合用 LinkedList：需要大量随机访问（get(i)）——它每次都要从头部或尾部顺着链走过去，节点越多越慢；以及元素数量不大、代码可读性优先的场景。

面试里那句经典结论也就由此而来：ArrayList 查快改慢（尤其是中间插入），LinkedList 改（增删）快查慢。

四、源码层面的几个关键设计

1. 内部类 Node

LinkedList 内部只维护一个 Node 的静态内部类，三个字段：item（数据）、prev（前驱指针）、next（后继指针）。这就是「双向」二字的来源——每个节点既能往前走也能往后走，所以从中间某个节点出发删除时，不用再从头找一遍前驱。

2. 只维护头尾两个引用

LinkedList 实例里存了 first 和 last 两个指针指向首尾节点，再加上一个 size 记录元素个数。它不维护任何一个指向「当前位置」的游标，所以任何按下标的操作都必须从端点开始遍历——这就是 get(index) 效率低的原因。

3. 空链表的表示

源码里对首尾节点的连接做了很多「任意一个为空就短路」的判断，因为双向链表首尾相连时可能出现 prev == null 又被当成前驱去遍历的情况，所以每个指针跳转前都要判空。这也是双向链表实现比单向链表啰嗦的地方。

4. 迭代器与 fail-fast

LinkedList 的迭代器会记录 modCount（修改次数），遍历过程中如果结构被非迭代器方式修改（比如外部再 add 一个），会抛 ConcurrentModificationException。这是 fail-fast 机制，目的是尽早暴露并发修改，而不是保证安全——多线程下要自己加锁或用并发容器。

五、几个高频方法对照

• add(E)：追加到尾部，O(1)；
• add(int,E)：按位置插入，先遍历到该位置再改指针，O(n)；
• remove(int) / remove(Object)：删除并返回值；
• get(int)：取第 index 个，源码会判断 index 在前半段还是后半段，决定从 first 还是 last 开始遍历，但仍然 O(n)；
• offer() / poll()：作为队列使用，入队出队都在尾部/头部，O(1)。

六、小结

LinkedList 是一个双向链表，元素在内存中不连续，靠节点里的 prev/next 指针串起来；它增删快（只改指针）、随机访问慢（要顺着链走）。源码上只维护 first/last 两个引用加一个 size，配合 fail-fast 迭代器。

实际选型记住一点就够：要「按位取、顺序遍历」用 ArrayList；要「队列/栈、头尾频繁增删」用 LinkedList。Java 8 之后有大量场景推荐直接上 ArrayDeque 代替 LinkedList 做队列，因为它在缓存局部性上表现更好——但这属于另一个话题了。

qidao123.com企服评测-应用市场 编辑提示