--- title: "02-LinkedList" created: 2025-12-02 tags: - Java --- # LinkedList > [!note] 定位说明 > List 系列第 2 篇详篇。LinkedList 是"一身兼两职"的实现：同时实现 `List` 和 `Deque`——既能当链表版序列，又能当双端队列/栈/队列（本篇"扩展用法"一节）。头尾操作 O(1) 是它的主场，随机访问 O(n) 是它的短板。队列与双端队列的系统讲解见 03-Queue 系列（ArrayDeque 是它作为队列场景的主要对手）。 ## 概念与本质 `LinkedList` 是 Java 中基于 **双向链表** 实现的集合类，位于 `java.util` 包中。它既实现了 `List` 接口（可随机访问、插入、删除），也实现了 `Deque` 接口（支持队列、双端队列操作），因此功能非常全面。 ```java public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, Serializable ``` 本质上是一个 **双向链表**，每个节点 Node 保存当前元素、前一个节点、后一个节点： ```java private static class Node { E item; Node next; Node prev; } ``` 头节点 `first` → 节点1 → 节点2 → 节点3 → ... → `last` 尾节点 `last` ← 节点3 ← 节点2 ← 节点1 ← `first` 正因为是双向结构，所以： - 可以实现从前向后、从后向前遍历 - 插入删除只需要断开和重接指针，效率高 - 但是不支持 O(1) 索引定位，需从头或尾遍历定位 ## 核心特性 | 特性 | 说明 | | --- | --- | | **底层结构** | 双向链表，每个节点有前驱和后继指针 | | **增删效率高** | 插入、删除只需改变指针，O(1) 复杂度 | | **查询效率低** | 无法快速随机访问，查询需从头/尾遍历，O(n) 复杂度 | | **线程不安全** | 多线程环境需手动同步 | | **支持双端队列** | 实现了 `Deque` 接口，支持头尾操作 | | **允许存 null 元素** | 可存多个 null | | **非 fail-safe** | 支持 fail-fast 机制，结构修改时若有迭代器在遍历，将抛出 `ConcurrentModificationException` | ## 常用方法与使用示例 ### 创建方式 ```java List list = new LinkedList<>(); Deque deque = new LinkedList<>(); ``` ### 常见操作 ```java list.add("a"); // 尾部添加 list.add(1, "b"); // 插入到指定位置 list.remove("a"); // 删除指定元素 list.remove(0); // 删除指定下标元素 list.set(0, "new"); // 替换元素 String s = list.get(0); // 获取元素（注意效率低） list.getFirst(); // 头部元素 list.getLast(); // 尾部元素 list.offerFirst("a"); // 头部添加 list.pollLast(); // 尾部弹出 ``` | **操作** | **方法示例** | **时间复杂度** | **说明** | | --- | --- | --- | --- | | **头插元素** | **addFirst(e)**, **offerFirst(e)** | O(1) | 直接修改头节点指针 | | **尾插元素** | **add(e)**, **offerLast(e)** | O(1) | 直接修改尾节点指针 | | **中间插入** | **add(index, e)** | O(n) | 需遍历定位到目标位置 | | **头删元素** | **removeFirst()**, **pollFirst()** | O(1) | 直接断开头节点 | | **尾删元素** | **removeLast()**, **pollLast()** | O(1) | 直接断开尾节点 | | **中间删除** | **remove(index)** | O(n) | 需遍历定位到目标节点 | | **按值删除** | **remove(Object o)** | O(n) | 遍历查找元素并删除 | | **查询元素** | **get(index)** | O(n) | 需遍历链表 | ## 底层实现细节解析 ### 添加元素（尾部） ```java public boolean add(E e) { linkLast(e); return true; } void linkLast(E e) { final Node l = last; // 原尾节点 final Node newNode = new Node<>(l, e, null); // 新节点指向原尾节点 last = newNode; // 更新尾节点 if (l == null) first = newNode; // 原链表为空 else l.next = newNode; // 原尾节点指向新节点 size++; modCount++; // 记录结构修改（支持fail-fast） } ``` - 头尾插入`O(1)`，中间插入需遍历定位（`O(n)`）。 - 通过`modCount`实现快速失败机制（`fail-fast`）。 ### 删除元素 ```java public E remove(int index) { return unlink(node(index));// 定位节点（O(n)） 断开指针 } E unlink(Node x) { final E element = x.item; final Node next = x.next; final Node prev = x.prev; if (prev == null) first = next; // 删除的是头节点 else prev.next = next; // 前驱节点跳过当前节点 if (next == null) last = prev; // 删除的是尾节点 else next.prev = prev; // 后继节点跳过当前节点 // 清除引用，帮助GC x.item = null; x.next = null; x.prev = null; size--; modCount++; return element; } ``` 只需修改前后指针即可完成删除，时间复杂度为 O(1)（前提是已经找到该节点）。 在删除元素时，LinkedList 会主动断开引用以利于 GC： ```java x.item = null; x.next = null; x.prev = null; ``` 这是为了防止“对象游离”（元素虽然删除了，但由于引用仍存在，导致垃圾回收不了）。 ### 查找优化 不像 ArrayList 支持索引随机访问，LinkedList 每次查找元素都要从头或尾开始遍历，时间复杂度为 O(n)： ```java public E get(int index) { return node(index).item; // 调用定位方法 } Node node(int index) { // 二分法优化：前半部分从头遍历，后半部分从尾遍历 if (index < (size >> 1)) { // 前半部分，从头开始 Node x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { // 后半部分，从尾开始 Node x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } ``` **效率瓶颈**： - 随机访问需遍历链表，时间复杂度`O(n)`，不适合高频查询场景。 ## 应用场景与注意事项 #### **适用场景** 1. **高频头尾操作**： - 双端队列（`Deque`）、栈（`push/pop`）、队列（`offer/poll`）。 ```java Deque stack = new LinkedList<>(); stack.push("A"); // 头插（O(1)） String top = stack.pop(); // 头删（O(1)） ``` 2. **动态数据场景**： - 元素数量不确定，频繁插入 / 删除（如日志记录、消息队列）。 #### **避坑要点** 1. **避免随机访问**： - 禁止大量使用`get(index)`、`set(index, e)`（`O(n)`效率低下）。 2. **迭代器安全删除**： ```java Iterator it = list.iterator(); while (it.hasNext()) { if (it.next().equals("目标")) { it.remove(); // 安全删除（更新modCount） } } ``` 3. **内存管理**： - 长时间持有大链表时，主动删除节点后需置空引用（如`node.item = null`），防止 GC 延迟。 #### **线程安全方案** - **同步包装器**： ```java List syncList = Collections.synchronizedList(new LinkedList<>()); ``` - 并发容器替代： - 无界队列：`ConcurrentLinkedQueue`（无锁，适合高并发）。 - 有界队列：`LinkedBlockingQueue`（阻塞式，支持容量限制）。 ## 扩展用法（作为队列与栈） 由于 LinkedList 实现了 `Deque` 接口，它不仅可以当 `List`，也能当作： **1. 双端队列（Deque）** ```java Deque deque = new LinkedList<>(); deque.offerFirst("A"); // 头插 deque.offerLast("B"); // 尾插 String first = deque.pollFirst(); // 头删 String last = deque.pollLast(); // 尾删 ``` **2. 栈（模拟 Stack）** ```java Deque stack = new LinkedList<>(); stack.push(1); // 等价于addFirst() int top = stack.pop(); // 等价于removeFirst()，LIFO ``` **3. 队列（Queue）** ```java Queue queue = new LinkedList<>(); queue.offer("X"); // 尾插（FIFO） String head = queue.poll(); // 头删 ``` ## Fail-Fast 机制 **实现方式**： - 通过`modCount`变量记录集合结构修改次数（增删操作时`modCount++`）。 - 迭代器创建时保存当前`modCount`，遍历时若发现`modCount`变化，抛出`ConcurrentModificationException`。 **示例错误**： ```java List list = new LinkedList<>(); list.add("a"); Iterator it = list.iterator(); list.remove(0); // 修改结构，modCount变化 it.next(); // 抛出ConcurrentModificationException ``` 正确做法：使用迭代器的`remove()`方法（内部更新modCount）。 ```java Iterator it = list.iterator(); while (it.hasNext()) { if (it.next().equals("a")) { it.remove(); // 安全 } } ``` ## 线程安全与并发建议 - `LinkedList` 本身是**非线程安全**的 - 如果在多线程环境中使用，应考虑： - 外部加锁（synchronized） - 使用 `Collections.synchronizedList(new LinkedList<>())` - 或者直接使用并发容器，如： - `ConcurrentLinkedQueue`（无锁、非阻塞） - `LinkedBlockingQueue`（支持阻塞） ## LinkedList 的设计哲学 - **核心优势**：双向链表赋予其**灵活的增删能力**和**多接口适配性**（List/Deque）。 - **本质局限**：无索引导致随机访问低效，内存占用高于数组。 - **选型原则**： - 选 LinkedList：需高频头尾操作、实现双端队列 / 栈、元素动态变化。 - 选 ArrayList：需高频随机访问、数据量固定或可预估。 理解 LinkedList 的双向链表本质，能帮助开发者在不同场景下做出高效选择，避免因数据结构误用导致性能问题。 --- ⬅️ [[01-ArrayList|ArrayList]] 🏠 [[00-Java|00-Java]] ➡️ [[03-Vector|Vector]]