LinkedList

ℹ️定位说明

List 系列第 2 篇详篇。LinkedList 是"一身兼两职"的实现：同时实现 List 和 Deque——既能当链表版序列，又能当双端队列/栈/队列（本篇"扩展用法"一节）。头尾操作 O(1) 是它的主场，随机访问 O(n) 是它的短板。队列与双端队列的系统讲解见 03-Queue 系列（ArrayDeque 是它作为队列场景的主要对手）。

概念与本质

LinkedList 是 Java 中基于 双向链表 实现的集合类，位于 java.util 包中。它既实现了 List 接口（可随机访问、插入、删除），也实现了 Deque 接口（支持队列、双端队列操作），因此功能非常全面。

public class LinkedList<E> extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, Serializable

本质上是一个 双向链表，每个节点 Node 保存当前元素、前一个节点、后一个节点：

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> 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`

常用方法与使用示例

创建方式

List<String> list = new LinkedList<>();
Deque<Integer> deque = new LinkedList<>();

常见操作

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)	需遍历链表

底层实现细节解析

添加元素（尾部）

public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    final Node<E> l = last;  // 原尾节点
    final Node<E> 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）。

删除元素

public E remove(int index) {
    return unlink(node(index));// 定位节点（O(n)） 断开指针
}

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; // 前驱节点跳过当前节点

    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：

x.item = null;
x.next = null;
x.prev = null;

这是为了防止“对象游离”（元素虽然删除了，但由于引用仍存在，导致垃圾回收不了）。

查找优化

不像 ArrayList 支持索引随机访问，LinkedList 每次查找元素都要从头或尾开始遍历，时间复杂度为 O(n)：

public E get(int 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;
    }
}

效率瓶颈：

随机访问需遍历链表，时间复杂度O(n)，不适合高频查询场景。

应用场景与注意事项

适用场景

高频头尾操作：
- 双端队列（Deque）、栈（push/pop）、队列（offer/poll）。

     Deque<String> 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<String> it = list.iterator();
   while (it.hasNext()) {
       if (it.next().equals("目标")) {
           it.remove(); // 安全删除（更新modCount）
       }
   }

内存管理：
- 长时间持有大链表时，主动删除节点后需置空引用（如node.item = null），防止 GC 延迟。

线程安全方案

同步包装器：

  List<String> syncList = Collections.synchronizedList(new LinkedList<>());

并发容器替代：
- 无界队列：ConcurrentLinkedQueue（无锁，适合高并发）。
- 有界队列：LinkedBlockingQueue（阻塞式，支持容量限制）。

扩展用法（作为队列与栈）

由于 LinkedList 实现了 Deque 接口，它不仅可以当 List，也能当作：

1. 双端队列（Deque）

  Deque<String> deque = new LinkedList<>();
  deque.offerFirst("A"); // 头插
  deque.offerLast("B");  // 尾插
  String first = deque.pollFirst(); // 头删
  String last = deque.pollLast();  // 尾删

2. 栈（模拟 Stack）

  Deque<Integer> stack = new LinkedList<>();
  stack.push(1);   // 等价于addFirst()
  int top = stack.pop(); // 等价于removeFirst()，LIFO

3. 队列（Queue）

  Queue<String> queue = new LinkedList<>();
  queue.offer("X"); // 尾插（FIFO）
  String head = queue.poll(); // 头删

Fail-Fast 机制

实现方式：

通过modCount变量记录集合结构修改次数（增删操作时modCount++）。
迭代器创建时保存当前modCount，遍历时若发现modCount变化，抛出ConcurrentModificationException。

示例错误：

List<String> list = new LinkedList<>();
list.add("a");
Iterator<String> it = list.iterator();
list.remove(0); // 修改结构，modCount变化
it.next(); // 抛出ConcurrentModificationException

正确做法：使用迭代器的remove()方法（内部更新modCount）。

Iterator<String> 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 的双向链表本质，能帮助开发者在不同场景下做出高效选择，避免因数据结构误用导致性能问题。

⬅️ ArrayList 🏠 00-Java ➡️ Vector

02-LinkedList