Java 链表（LinkedList）

likuoelie

396人浏览 · 2026-02-07 16:07:15

likuoelie · 2026-02-07 16:07:15 发布

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 的更好替代品。