74. LinkedList、Vector 与 Stack

LinkedList 长什么样

LinkedList 底层是一条「双向链表」：每个元素都记着前一个和后一个的位置，像一节节火车车厢连起来。插入一节新车厢，只要把前后两节的指针改一下就行，不用挪动其他车厢。

它有两个本领：

• 实现了 List 接口，能当普通列表用（有序、可重复、可索引）。
• 实现了 Deque 接口，能在两头随时加、随时取（当队列或栈用）。

LinkedList<String> list = new LinkedList<>();
list.add("尾");
list.addFirst("头");   // 头部插入，O(1)
list.addLast("尾2");   // 尾部插入，O(1)
System.out.println(list); // [头, 尾, 尾2]
```bash

## 它适合什么场景

因为链表增删不用挪动其他元素，所以 LinkedList 在「两头频繁增删」时很快。

```java
// 在头部插入：LinkedList 比 ArrayList 快得多
LinkedList<Integer> deque = new LinkedList<>();
deque.addFirst(1); // 头部加
deque.addFirst(2);
Integer head = deque.pollFirst(); // 取走头部并删除

但它按下标随机访问（get(i)）很慢：得从头一节节数过去，列表越长越慢。所以「又要在中间按索引访问、又要频繁增删」的需求，LinkedList 两头都不讨好——中间访问慢、中间增删也慢（因为要先找到位置）。

Deque 方法一览

LinkedList 当双端队列用时，这些方法是它最常露脸的：

LinkedList<String> dq = new LinkedList<>();
dq.offerFirst("a");  // 头部入队，推荐用 offer 而非 add
dq.offerLast("b");   // 尾部入队
String f = dq.peekFirst(); // 看头部但不删
String v = dq.pollFirst(); // 取走头部并删除
```bash

`offer`/`peek`/`poll` 比起 `add`/`get`/`remove` 更温和：队列空了或满了不会抛异常，而是返回 `false`/`null`，更适合队列语义。这也是第 77 章会展开讲的双端队列用法。

## Vector：该进博物馆的类

`Vector` 是 Java 1.0 就有的老类，几乎和 ArrayList 一样，但每个方法都加了 `synchronized` 锁。

```java
// 历史兼容写法，新代码不要这么写
Vector<String> v = new Vector<>(); // 方法全同步，慢

Stack：用 Deque 代替它

Stack 是「栈」这种数据结构（后进先出），但它继承自 Vector，连带着继承了那套过时的同步设计，还把栈该有的方法 push/pop/peek 和 List 的方法搅在一起，容易用错。

// 历史兼容写法，不推荐
Stack<Integer> st = new Stack<>();
st.push(1);
st.pop();
```java

现代写法的标准替代是 `ArrayDeque`，当栈用既快又干净（详见第 77 章）：

```java
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);        // 压栈
Integer top = stack.pop(); // 弹栈

三个类的定位清单

• ArrayList：默认首选，查得快，中间增删慢。
• LinkedList：首尾频繁增删、当队列/栈用时考虑。
• ArrayDeque：做队列或栈的现代首选，替代 Stack。
• Vector / Stack：历史兼容，新代码禁用。

一个容易混的点：栈和队列

很多人分不清栈和队列。记住两个生活类比：

• 队列像食堂排队，先来的先打完饭走（先进先出，FIFO）。
• 栈像一摞盘子，你只能从最上面拿，最后放上去的先被拿走（后进先出，LIFO）。

LinkedList 和 ArrayDeque 都能当队列也能当栈，因为 Deque 两头都能操作；而老 Stack 只能当栈，还慢，自然被淘汰。

什么时候 LinkedList 真的不如 ArrayList

不少初学者听「链表插入快」就以为 LinkedList 处处快，这是误区。链表快的前提是「你已经站在要操作的位置旁边」。如果你是通过下标 get(500) 去访问，LinkedList 得从头数 500 次才到，这时候它比 ArrayList 慢得多。

所以经验很朴素：默认用 ArrayList。只有当你的操作几乎全是在头部、尾部频繁增删，几乎从不按索引访问中间元素时，LinkedList 的优势才显现。现实里这种场景不算多，所以你会看到很多项目里 LinkedList 出场率远低于 ArrayList。

另外提醒一句，LinkedList 也实现了 Queue 和 Deque 接口，理论上能当队列用。但第 77 章会告诉你，专门的 ArrayDeque 在队列场景性能更好、也更省内存，所以 LinkedList 的队列身份基本被 ArrayDeque 替代了。真要用链表，多半是你在刷算法题、需要自己手写节点操作的时候。

一个判断清单

把前面说的收敛成一句话清单，遇到选型拿不准就照着对：

• 要存一列、能重复、主要按下标读 → ArrayList。
• 要在两头疯狂增删、几乎不按索引读中间 → 才考虑 LinkedList。
• 要当栈或队列 → ArrayDeque，别碰 Stack 和 Vector。
• 看到老代码里 new Vector() 或 new Stack() → 这是历史遗留，新代码换成上面对应的实现。

记住这条就够：先把 ArrayList 和 ArrayDeque 用熟，LinkedList 和那些古董类基本是特殊场景或历史代码的份。

一句话收尾

Vector 和 Stack 不是完全不能用，而是「有更好的替代品」。新项目一律用 ArrayList 和 ArrayDeque，把这两个古董留在历史代码里就好。链表的价值只在特定场景闪光，别被「插入快」这句半截话带偏。

小结

LinkedList 是双向链表，适合两头频繁增删，同时能当 Deque 用；Vector 和 Stack 是古董类，方法带同步、设计过时，现代代码用 ArrayList 和 ArrayDeque 替代即可。下一章看「不可重复」的那一支——Set。