LinkedList 插入真的是 O(1) 吗？深度解析 Java 双向链表的性能陷阱与源码真相
LinkedList 的插入操作真的是 O(1) 吗？这个看似常识的答案，在实际生产中可能让你踩坑。
大多数开发者知道 LinkedList 基于双向链表，却忽略了它在真实场景中的性能陷阱：for 循环 + get(i) 会让时间复杂度退化到 O(n²)，CPU 缓存不友好导致的性能下降，以及每个节点额外 ~32 字节的内存开销。
本文将从源码级别揭示 LinkedList 的真实面貌，看完你将掌握：
- LinkedList 的底层是基于什么数据结构实现的？
- LinkedList 的插入和删除操作时间复杂度是否都是 O(1)？
- LinkedList 和 ArrayList 相比，哪种结构更占内存？
- LinkedList 真的不支持随机访问吗？
- LinkedList 是线程安全的吗？
简介
LinkedList 底层是基于双向链表实现的，内部有三个属性：size 用来存储元素个数，first 指向链表头节点，last 指向链表尾节点。
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
// 元素个数
transient int size = 0;
// 头节点
transient Node<E> first;
// 尾节点
transient Node<E> last;
}
头尾节点都是由 Node 节点组成，Node 节点表示双向链表的一个元素，内部结构如下：
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;
}
}
类图架构
«interface»
Collection<E>
+add(E e) : boolean
+remove(Object o) : boolean
+contains(Object o) : boolean
+size() : int
+isEmpty() : boolean
«interface»
List<E>
+get(int index) : E
+add(int index, E e) : void
+remove(int index) : E
+indexOf(Object o) : int
«interface»
Deque<E>
+addFirst(E e) : void
+addLast(E e) : void
+removeFirst() : E
+removeLast() : E
+peekFirst() : E
+peekLast() : E
«abstract»
AbstractSequentialList<E>
LinkedList<E>
-transient int size
-transient Node<E> first
-transient Node<E> last
-static class Node
+LinkedList()
+add(E e) : boolean
+add(int index, E e) : void
+get(int index) : E
+remove(int index) : E
+addFirst(E e) : void
+addLast(E e) : void
+removeFirst() : E
+removeLast() : E
-node(int index) : Node
-linkLast(E e) : void
-linkFirst(E e) : void
-unlink(Node x) : E
LinkedList 实现了 List 接口，提供了集合操作的常用方法，当然也包含随机访问的方法，只不过没有像 ArrayList 那样实现 RandomAccess 接口，LinkedList 提供的随机访问方法时间复杂度不是常量级别的。
LinkedList 还实现了 Deque 接口，Deque 是 double ended queue 的缩写，读音是 /dek/，读错就尴尬了。
Deque 是双端队列，可以在头尾进行插入和删除操作，兼具栈和队列的性质。
Deque 提供了大量增删查方法，目的是区分不同语义：对于添加操作，addFirst() 在队列满时会抛出异常，而 offerFirst() 则返回 false；对于删除和查询，以 poll/peek 开头的方法在元素不存在时返回 null，而以 remove/get/element 开头的方法则会抛出异常。
常用方法分类如下：
| 操作类型 | 头部操作（抛出异常） | 头部操作（返回特殊值） | 尾部操作（抛出异常） | 尾部操作（返回特殊值） |
|---|---|---|---|---|
| 添加 | addFirst(e)、push(e) | offerFirst(e) | addLast(e)、add(e) | offerLast(e)、offer(e) |
| 删除 | removeFirst()、remove()、pop() | pollFirst()、poll() | removeLast() | pollLast() |
| 查询 | getFirst()、element() | peekFirst()、peek() | getLast() | peekLast() |
核心工作原理
add(e) 尾部添加
addFirst(e) 头部添加
add(index,e) 任意位置
是
否
remove 删除
removeFirst
removeLast
remove(index)
remove(Object)
找到
未找到
get(index)
getFirst/getLast
初始化: first=null, last=null, size=0
添加元素?
linkLast: 新节点prev指向原last\nlast更新为新节点\n原last.next指向新节点\nsize++ modCount++
linkFirst: 新节点next指向原first\nfirst更新为新节点\n原first.prev指向新节点\nsize++ modCount++
index == size?
node(index): 按index与size/2比较\n决定从头或尾遍历
linkBefore: 在目标节点前插入新节点\n修改前后节点指针\nsize++ modCount++
按位置还是按值?
unlinkFirst: 断开头节点引用\nitem和next置null\nsize-- modCount++
unlinkLast: 断开尾节点引用\nitem和prev置null\nsize-- modCount++
node(index) 定位节点
unlink: 断开前后节点引用\nitem/prev/next置null\nsize-- modCount++
从头/尾遍历查找equals
返回false
查询元素?
node(index) 定位节点
返回 node.item
直接返回 first.item / last.item
初始化
LinkedList 只有一个构造方法——无参构造，并不能像 ArrayList 那样指定初始容量。
List<Integer> list = new LinkedList<>();
构造方法的底层实现也是一个空方法，没有做任何操作：
public LinkedList() {
}
这意味着 LinkedList 创建时不会预先分配任何节点，所有节点都是在添加元素时才动态创建。
💡 核心提示：LinkedList 的无参构造是真正的"零成本"初始化——它不分配任何内存。这与 ArrayList 不同（ArrayList 无参构造也只是赋值空数组引用，同样零分配）。但 LinkedList 每次
add都要new Node()，意味着每次添加都是一次独立的堆分配，在大量元素场景下，这会导致内存碎片化，且每个节点的 GC 追踪开销更大。
添加元素
添加元素的方法根据位置区分，共有三种：在头部添加、在尾部添加、在任意位置添加。
| 方法含义 | 不返回值 | 返回布尔值 |
|---|---|---|
| 在头部添加 | addFirst(e)、push(e) | offerFirst(e) |
| 在尾部添加 | addLast(e) | add(e)、offer(e)、offerLast(e) |
| 在任意位置添加 | add(index, e) | - |
先看一下使用最多的 add(e) 方法底层实现：
// 添加元素
public boolean add(E e) {
// 在末尾添加元素
linkLast(e);
return true;
}
// 在末尾添加元素
void linkLast(E e) {
// 1. 获取尾节点
final Node<E> l = last;
// 2. 初始化新节点
final Node<E> newNode = new Node<>(l, e, null);
// 3. 追加到末尾
last = newNode;
if (l == null) {
first = newNode;
} else {
l.next = newNode;
}
size++;
modCount++;
}
linkLast 的核心逻辑：保存原尾节点 → 创建新节点（前驱指向原尾节点） → 更新 last 指针 → 如果链表为空则同时设置 first → 否则将原尾节点的 next 指向新节点。
再看一个从头部添加元素的 push()：
// 添加元素
public void push(E e) {
// 在头部添加元素
addFirst(e);
}
// 在头部添加元素
public void addFirst(E e) {
linkFirst(e);
}
// 在头部添加元素，底层私有实现
private void linkFirst(E e) {
// 1. 获取头节点
final Node<E> f = first;
// 2. 初始化新节点
final Node<E> newNode = new Node<>(null, e, f);
// 3. 追加到头部
first = newNode;
if (f == null) {
last = newNode;
} else {
f.prev = newNode;
}
size++;
modCount++;
}
linkFirst 与 linkLast 逻辑对称：保存原头节点 → 创建新节点（后继指向原头节点） → 更新 first 指针 → 如果链表为空则同时设置 last → 否则将原头节点的 prev 指向新节点。
最后看在任意位置添加的 add(index, e) 底层实现：
// 在下标index位置添加元素
public void add(int index, E element) {
// 检查下标是否越界
checkPositionIndex(index);
// 如果index等于链表长度，则添加到末尾
if (index == size) {
linkLast(element);
} else {
// 添加到指定位置前面（先找到index位置的元素）
linkBefore(element, node(index));
}
}
// 在当前元素前面添加新元素
void linkBefore(E e, Node<E> succ) {
final Node<E> pred = succ.prev;
// 创建新节点，并将新节点插入到当前节点之前
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null) {
first = newNode;
} else {
pred.next = newNode;
}
size++;
modCount++;
}
这里调用了 checkPositionIndex 进行越界检查（允许 index == size，因为可以在末尾追加）：
// 检查位置下标是否越界
private void checkPositionIndex(int index) {
if (!isPositionIndex(index)) {
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
}
// 判断位置下标是否合法
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
add(index, e) 内部还依赖了 node(index) 方法来定位节点，这个方法在查询部分详细分析。
查询元素
查询元素的方法按位置区分，共有三种：查询头节点、查询尾节点、查询任意位置元素。
| 方法含义 | 如果不存在则返回null | 如果不存在则抛异常 |
|---|---|---|
| 查询头部 | peek()、peekFirst() | getFirst()、element() |
| 查询尾部 | peekLast() | getLast() |
| 查询任意位置 | - | get(index) |
看一下从头查询的 element() 方法的底层实现：
// 查询元素
public E element() {
return getFirst();
}
// 获取第一个元素
public E getFirst() {
final Node<E> f = first;
if (f == null) {
throw new NoSuchElementException();
}
return f.item;
}
再看一个查询尾节点的 getLast() 方法的底层实现：
// 获取最后一个元素
public E getLast() {
final Node<E> l = last;
if (l == null) {
throw new NoSuchElementException();
}
return l.item;
}
头尾查询都是 O(1) 时间复杂度，因为直接访问 first 和 last 指针。
再看一个查询任意位置的方法 get(index) 的底层实现：
// 查询下标是index位置的元素
public E get(int index) {
// 检查下标是否越界
checkElementIndex(index);
// 返回对应下标的元素
return node(index).item;
}
// 返回对应下标的元素
Node<E> node(int 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;
}
}
node(index) 方法做了一个重要优化：通过 index < (size >> 1) 判断索引落在前半段还是后半段，前半段从头节点开始向后遍历，后半段从尾节点开始向前遍历。这样最多只需要遍历链表的一半，将最坏情况的遍历步数从 n 降低到了 n/2。
💡 核心提示：虽然
node(index)做了优化，但时间复杂度仍然是 O(n)。这意味着在 LinkedList 上做随机访问（如get(i)在循环中）的性能远远劣于 ArrayList。下面这个代码就是一个经典陷阱：// 糟糕的做法：每次循环都要从头部/尾部遍历到 index for (int i = 0; i < list.size(); i++) { process(list.get(i)); }这段代码的总时间复杂度是 O(n²)，因为每次
get(i)都要遍历最多 n/2 步。应该使用迭代器或增强 for 循环来遍历 LinkedList。
越界检查 checkElementIndex 与 checkPositionIndex 不同——它要求 index < size（不允许等于），因为查询必须指向已存在的元素：
// 检查下标是否越界
private void checkElementIndex(int index) {
if (!isElementIndex(index)) {
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
}
// 判断下标是否越界
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
可见 LinkedList 也支持随机访问，只不过时间复杂度是 O(n)。
除了按索引查询，LinkedList 还提供了按值查找的方法 indexOf(Object o)：
// 返回指定元素第一次出现的下标
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
indexOf 从头到尾线性遍历查找，对 null 值做了特殊处理（用 == 而不是 equals），时间复杂度为 O(n)。
删除元素
删除元素的方法按位置区分，也分为三种：删除头节点、删除尾节点、删除任意位置节点。
| 方法含义 | 返回布尔值（不存在返回false） | 返回旧值（不存在抛异常） |
|---|---|---|
| 从头部删除 | remove(o)、removeFirstOccurrence | remove()、poll()、pollFirst()、removeFirst()、pop() |
| 从尾部删除 | removeLastOccurrence | pollLast()、removeLast() |
| 从任意位置删除 | - | remove(index) |
先看一个从头开始删除的方法 remove() 的底层实现：
// 删除元素
汇聚全球AI编程工具，助力开发者即刻编程。
更多推荐
4
0- 0
已为社区贡献3条内容
所有评论(0)