LinkedList 是基于双向链表实现的集合类，同时实现了 List、Deque 和 Queue 接口。它既可以当普通列表使用，也可以当队列、双端队列、栈使用。

但在真实业务里，LinkedList 远没有新手想象中那么常用。它的优势主要在头尾节点操作和已定位节点的插入删除；如果需要按索引访问或大量遍历，通常不如 ArrayList。

1. 核心特点

特点	说明
底层结构	双向链表
有序	按链表节点顺序保存
可重复	允许重复元素
允许 null	可以存多个 null
随机访问慢	get(index) 需要遍历
头尾操作快	addFirst、addLast、removeFirst、removeLast 是 O(1)
非线程安全	多线程写入需要额外同步

2. 双向链表结构

每个节点保存元素，以及前驱、后继引用。

LinkedList
┌──────────────┐
│ first ───┐   │
│ last  ───────┼─────────────┐
│ size = 3     │             │
└──────────────┘             │
             │               │
             ▼               ▼
null <- [A] <-> [B] <-> [C] -> null

节点结构：

Node
├─ item
├─ prev
└─ next

因为每个元素都需要一个节点对象，且节点包含前后指针，所以 LinkedList 的内存开销通常高于 ArrayList。

3. 作为 List 使用

List<String> list = new LinkedList<>();
list.add("A");
list.add("B");
list.add(1, "X");

按索引插入时，LinkedList 需要先找到目标位置：

add(index, value)
  │
  ▼
判断 index 在前半段还是后半段
  │
  ├─ 前半段：从 first 往后找
  └─ 后半段：从 last 往前找
  │
  ▼
找到节点后修改指针

所以 list.add(index, value) 不是纯 O(1)，整体通常是 O(n)。

4. 查找元素

String value = list.get(1000);

查找流程：

index < size / 2 ?
  │
  ├─ 是：从 first 开始 next 遍历
  └─ 否：从 last 开始 prev 遍历

虽然做了前后半区优化，但本质还是链表遍历，时间复杂度 O(n)。

不要这样遍历 LinkedList：

for (int i = 0; i < list.size(); i++) {
    process(list.get(i));
}

这会让每次 get(i) 都重新遍历，整体可能退化为 O(n²)。

推荐：

for (String value : list) {
    process(value);
}

5. 插入与删除

头部插入：

list.addFirst("A");

原链表：
[B] <-> [C]

addFirst(A)：
[A] <-> [B] <-> [C]

尾部插入：

list.addLast("D");

删除头尾：

list.removeFirst();
list.removeLast();

头尾操作只需要修改少量引用，是 O(1)。但按值删除仍然需要遍历查找：

list.remove("A"); // O(n)

6. 作为 Queue 使用

LinkedList 实现了 Queue。

Queue<String> queue = new LinkedList<>();
queue.offer("A");
queue.offer("B");

System.out.println(queue.poll()); // A

队列语义：

offer -> [A, B, C] -> poll
          head tail

方法对比：

操作	抛异常方法	返回特殊值方法
入队	add	offer
出队	remove	poll
查看队首	element	peek

业务代码通常优先用 offer、poll、peek，避免空队列时抛异常。

7. 作为 Deque 使用

Deque 支持两端操作。

Deque<String> deque = new LinkedList<>();
deque.offerFirst("A");
deque.offerLast("B");
deque.pollFirst();
deque.pollLast();

双端结构：

offerFirst              offerLast
    │                      │
    ▼                      ▼
[ head ] <-> ... <-> [ tail ]
    ▲                      ▲
pollFirst              pollLast

不过如果只是做栈或队列，通常更推荐 ArrayDeque，因为数组结构更紧凑，缓存友好。

8. LinkedList 与 ArrayDeque

对比项	LinkedList	ArrayDeque
底层结构	双向链表	循环数组
内存占用	高，每个节点有指针	较低
头尾操作	O(1)	均摊 O(1)
随机访问	支持但慢	不支持
是否允许 null	允许	不允许
队列/栈推荐度	一般	更推荐

栈场景：

Deque<String> stack = new ArrayDeque<>();
stack.push("A");
stack.push("B");
System.out.println(stack.pop());

不要优先使用 Stack，它是早期遗留类，继承自 Vector，同步模型和 API 都不够现代。

9. 性能误区

9.1 “LinkedList 增删一定比 ArrayList 快”

不一定。中间插入删除分两步：

找到位置 O(n)
修改指针 O(1)

如果位置是通过索引给出的，定位成本仍然很高。

9.2 “链表不需要扩容，所以一定更省内存”

不一定。链表每个元素都要一个节点对象，还要保存 prev 和 next，对象数量多，内存开销和 GC 压力可能更大。

9.3 “LinkedList 适合大量遍历”

通常不如 ArrayList。数组连续存储，CPU 缓存命中更好；链表节点分散，遍历时指针跳转更多。

10. 适用场景

适合：

• 需要频繁从头尾插入删除。
• 已经持有迭代器位置，需要在附近插入删除。
• 需要一个允许 null 的 Deque。

不适合：

• 大量随机访问。
• 大量按索引遍历。
• 对内存占用敏感。
• 普通业务列表。

普通列表优先 ArrayList，队列和栈优先 ArrayDeque。

Tips 快问快答

Q：LinkedList 底层是什么？ A：双向链表，每个节点保存元素、前驱和后继引用。

Q：LinkedList 的 get(index) 是 O(1) 吗？ A：不是，需要从头或尾遍历，时间复杂度 O(n)。

Q：为什么 LinkedList 按索引遍历很慢？ A：每次 get(i) 都要重新找节点，循环里使用可能变成 O(n²)。

Q：LinkedList 插入删除一定快吗？ A：只有已定位节点或头尾操作快；如果要先按索引查找，整体仍可能是 O(n)。

Q：LinkedList 能当队列用吗？ A：能，它实现了 Queue 和 Deque。

Q：栈应该用 LinkedList 还是 Stack？ A：通常用 ArrayDeque，不推荐老的 Stack。

Q：LinkedList 允许 null 吗？ A：允许。

Q：LinkedList 线程安全吗？ A：不安全，需要外部同步或使用并发集合。

Q：为什么 ArrayDeque 经常比 LinkedList 更适合队列？ A：它基于数组，内存更紧凑，缓存友好，头尾操作也很快。

Q：普通业务列表什么时候选 LinkedList？ A：很少。只有明确依赖链表头尾操作或迭代器插入删除特性时再考虑。