LinkedList 底层实现：双向链表的工作原理
核心结构：一句话概括
LinkedList 底层是双向链表——每个节点存储自己的值，以及前一个和后一个节点的引用。
java
public class LinkedList<E> {
transient Node<E> first; // 头节点
transient Node<E> last; // 尾节点
transient int size = 0; // 节点数量
// 节点结构
private static class Node<E> {
E item; // 元素值
Node<E> prev; // 前驱节点
Node<E> next; // 后继节点
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.prev = prev;
this.next = next;
}
}
}内部结构图
双向链表就像一列火车：
┌──────────────────────────────────────────────────────────┐
│ LinkedList 内部结构 │
├──────────────────────────────────────────────────────────┤
│ │
│ first │
│ │ │
│ ▼ │
│ ┌────┐ ┌────┐ ┌────┐ ┌────┐ │
│ │null│◀───│ A │◀───│ B │◀───│ C │───▶│null│ │
│ │ │ │ │ │ │ │ │ │
│ └────┘ └────┘ └────┘ └────┘ │
│ ↑ first last │
│ │ │
│ null │
│ │
│ Node 结构： │
│ ┌─────────┬──────────┬─────────┐ │
│ │ prev │ item │ next │ │
│ └─────────┴──────────┴─────────┘ │
└──────────────────────────────────────────────────────────┘添加元素：O(1) 的秘密
LinkedList 添加元素不需要移动任何已有元素，只需要改变几个指针：
添加到末尾
java
void linkLast(E e) {
final Node<E> l = last;
// 新节点的 prev 指向原尾节点
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null) {
// 原链表为空，新节点成为头节点
first = newNode;
} else {
// 原尾节点的 next 指向新节点
l.next = newNode;
}
size++;
}添加到指定位置
java
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++;
}图示：
添加 "X" 到 [A, B, C] 的第 2 个位置：
操作前：
┌────┐ ┌────┐ ┌────┐
│ A │◀──▶│ B │◀──▶│ C │
└────┘ └────┘ └────┘
↑
succ
修改指针：
1. X.prev = B.prev (即 A)
2. X.next = B
3. B.prev = X
4. A.next = X
操作后：
┌────┐ ┌────┐ ┌────┐ ┌────┐
│ A │◀──▶│ X │◀──▶│ B │◀──▶│ C │
└────┘ └────┘ └────┘ └────┘获取元素：O(n) 的代价
这是 LinkedList 的最大弱点：
java
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;
}
}性能陷阱
get(500000) 在 100 万元素的 LinkedList 中需要遍历 50 万元素。同样的操作，ArrayList 只需要一步。
java
LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 1000000; i++) {
list.add(i);
}
// ❌ 极慢：O(n)
int value = list.get(500000);
// ✅ 快：O(1)
ArrayList<Integer> array = new ArrayList<>(list);
int value = array.get(500000);删除元素：O(1) 的优势
只要拿到了节点引用，删除是 O(1)：
java
E unlink(Node<E> x) {
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next; // 删除的是头节点
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev; // 删除的是尾节点
} else {
next.prev = prev;
x.next = null;
}
x.item = null; // 帮助 GC
size--;
return element;
}图示：
删除 [A, B, C] 中的 B：
操作前：
┌────┐ ┌────┐ ┌────┐
│ A │◀──▶│ B │◀──▶│ C │
└────┘ └────┘ └────┘
↑
要删除
修改指针：
1. A.next = C
2. C.prev = A
操作后：
┌────┐ ┌────┐
│ A │◀──▶│ C │
└────┘ └────┘性能总结
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
头部添加 addFirst() | O(1) | 只需修改头指针 |
尾部添加 addLast() | O(1) | 只需修改尾指针 |
按索引获取 get(i) | O(n) | 需遍历链表 |
按索引插入 add(i, e) | O(n) | 需先找到位置 |
按索引删除 remove(i) | O(n) | 需先找到位置 |
迭代器删除 it.remove() | O(1) | 已有节点引用 |
contains | O(n) | 需遍历查找 |
真正的 O(1) 操作
LinkedList 作为 Deque（双端队列）使用时，以下操作都是 O(1)：
java
LinkedList<Integer> list = new LinkedList<>();
// 头部操作
list.addFirst(1); // O(1)
list.removeFirst(); // O(1)
list.getFirst(); // O(1)
// 尾部操作
list.addLast(2); // O(1)
list.removeLast(); // O(1)
list.getLast(); // O(1)
// 作为队列（FIFO）
list.offer(3); // 队尾添加
list.poll(); // 队首取出
// 作为栈（LIFO）
list.push(4); // 入栈
list.pop(); // 出栈适用场景
✅ LinkedList 擅长的
java
// 场景1：用迭代器遍历时频繁增删
LinkedList<String> list = new LinkedList<>();
list.addAll(Arrays.asList("A", "B", "C", "D", "E"));
Iterator<String> it = list.iterator();
while (it.hasNext()) {
String s = it.next();
if (s.equals("C")) {
it.remove(); // O(1) 删除，已知节点引用
}
}
// 场景2：双端队列操作
Deque<Integer> deque = new LinkedList<>();
deque.addFirst(1);
deque.addLast(2);
deque.removeFirst();
deque.removeLast();
// 场景3：大量在头部/尾部操作
while (hasMore()) {
deque.offer(read()); // O(1)
}❌ LinkedList 不擅长的
java
// ❌ 按索引随机访问
list.get(5000); // O(n)，太慢
// ❌ 频繁中间插入（虽然理论上是 O(1)）
// 但你得先 O(n) 找到位置
// ✅ 用迭代器遍历 + 按位置操作
ListIterator<String> it = list.listIterator(2); // 从位置 2 开始
it.add("X"); // O(1) 插入与 ArrayList 的本质区别
ArrayList：数组，连续内存
- 随机访问快（一步到位）
- 中间增删需要移动元素
LinkedList：链表，分散内存
- 随机访问慢（需要遍历）
- 中间增删只需改指针
记住：
ArrayList 用「索引」思考
LinkedList 用「迭代器」思考总结
LinkedList = 双向链表。头尾操作 O(1)，按索引访问 O(n)。适合用迭代器遍历时增删，不适合随机访问。