Java 链表（LinkedList）详解：从原理到实战，一篇讲透
LinkedList 是 Java 集合框架中最经典的双向链表实现，同时实现了 List、Deque 接口，常被拿来和 ArrayList 对比。
很多人以为“链表 = 增删快”，但实际使用中很多人踩坑，本文从底层结构、源码核心、时间复杂度、真实场景、与 ArrayList 对比到常见误区，一次性讲清楚。
一、LinkedList 核心特点（一句话总结）
LinkedList 是基于双向链表（doubly-linked list）的线性表结构，
支持高效的头尾增删（O(1)），但随机访问（get/set）较慢（O(n)）。
它同时实现了：
List接口 → 像普通列表使用（有序、可重复、可 null）Deque接口 → 可以当双端队列、栈、队列用
二、底层数据结构（最核心）
LinkedList 的内部节点结构（JDK 8+ 源码简化版）：
private static class Node<E> {
E item; // 存储的元素
Node<E> next; // 后继指针
Node<E> prev; // 前驱指针
}三个关键字段：
transient int size = 0;
transient Node<E> first; // 头节点（头指针）
transient Node<E> last; // 尾节点（尾指针）双向链表示意图：
null ← prev [Node1: item=A] next → [Node2: item=B] next → [Node3: item=C] next → null
↑ ↑ ↑
first 中间节点 last优点：插入/删除时只改指针，不需要移动元素
缺点：访问第 n 个元素需要从头/尾遍历，内存开销大（每个节点多存两个指针）
三、时间复杂度一览表（面试必背）
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| get(index) / set(index) | O(n) | 需遍历到该位置 |
| add(E e) | O(1) | 尾插（addLast） |
| addFirst / addLast | O(1) | 头插 / 尾插 |
| add(index, e) | O(n) | 中间插入需遍历 |
| remove(index) | O(n) | 中间删除需遍历 |
| removeFirst / removeLast | O(1) | 头删 / 尾删 |
| contains / indexOf | O(n) | 线性查找 |
| iterator() | O(1) | 顺序遍历很快 |
结论：头尾操作极快，中间随机访问/修改很慢。
四、LinkedList vs ArrayList（2024-2025 最新对比）
| 维度 | ArrayList | LinkedList | 胜者（常见场景） |
|---|---|---|---|
| 底层结构 | 动态数组 | 双向链表 | — |
| 随机访问 get/set | O(1) | O(n) | ArrayList |
| 尾部添加 | 均摊 O(1)（扩容时 O(n)） | O(1) | 平手 |
| 中间插入/删除 | O(n)（需移动元素） | O(n)（需找到位置）+ O(1) 修改指针 | LinkedList 略优（大数据量） |
| 内存占用 | 连续内存 + 少量冗余 | 每个节点多两个指针（约 16~24 字节） | ArrayList 更省 |
| 缓存友好度 | 高（连续内存，CPU 预取） | 低（节点分散，缓存失效） | ArrayList |
| 实际性能（现代测试） | 几乎全场景完胜（get、add、remove） | 只在极大量头尾操作时占优 | ArrayList（大多数情况） |
2024-2025 真实测试结论（来自多个 benchmark）：
- 绝大多数场景下 ArrayList 完胜（包括中间插入删除）
- LinkedList 只有在频繁头尾增删 + 数据量极大（几十万以上） + 几乎不随机访问时才有优势
- 现代 JVM + 缓存机制让 ArrayList 的移动元素成本远低于预期
五、LinkedList 的高光使用场景（真正该用的时候）
- 当队列 / 双端队列（最常见）
Deque<String> queue = new LinkedList<>();
queue.offer("任务1"); // 队尾入
queue.poll(); // 队首出- 实现栈（LIFO）
Deque<String> stack = new LinkedList<>();
stack.push("A");
stack.pop();- 频繁在头部插入/删除（如 LRU 缓存的链表部分）
- 需要频繁头尾操作且不怎么随机访问（如任务调度队列、消息队列中间层）
- 作为队列的默认实现（Java 早期推荐，现在更多用 ArrayDeque）
注意：ArrayDeque（数组实现的双端队列）在绝大部分队列/栈场景下性能远超 LinkedList，是现代推荐的替代品。
六、常用方法速查（Deque + List 双重身份）
// List 接口常用
add(E e) // 尾部添加
get(int index)
set(int index, E element)
remove(int index)
remove(Object o)
// Deque 接口（双端队列）
addFirst / addLast
offerFirst / offerLast
peekFirst / peekLast // 查看不删除
pollFirst / pollLast // 删除并返回
push / pop // 栈操作（等价于 addFirst / removeFirst）七、常见面试/踩坑问题
- LinkedList 是线程安全的吗？
否！和 ArrayList 一样，多线程下需要自己加锁或用Collections.synchronizedList()/CopyOnWriteArrayList。 - 为什么 LinkedList 实现了 Deque？
因为它是双向链表，天生适合双端操作。 - LinkedList 可以存 null 吗？
可以，而且可以多个 null。 - 为什么现在很少用 LinkedList 做普通 List？
随机访问慢 + 内存开销大 + 缓存不友好，ArrayList 几乎全场景更优。 - ArrayDeque vs LinkedList？
ArrayDeque（数组实现双端队列）在头尾操作更快、内存更省，是 LinkedList 的更好替代品。
八、总结一句话
LinkedList = 双向链表 + List + Deque
优点：头尾增删 O(1)，天然支持队列/栈
缺点：随机访问 O(n)，内存占用高，缓存不友好
现代建议：
- 普通列表 → 优先 ArrayList
- 需要队列/栈 → 优先 ArrayDeque
- 只有极端头尾操作 + 海量数据 + 几乎无随机访问 → 才考虑 LinkedList
想看 LinkedList 源码某个方法详细解析（add / remove / get）、LRU 实现、还是性能测试代码？欢迎继续问～
