LinkedList

本章定位：深入理解 LinkedList 的双向链表结构、双端队列（Deque）能力以及它在"频繁增删"和"队列/栈"场景下的独特优势。与 ArrayList 形成互补，掌握两者的选型决策逻辑。

概述

LinkedList 同时实现了 List 和 Deque 接口，底层基于双向链表。每个节点存储数据以及前后指针。飞翔科技的消息队列、操作历史（撤销/重做）等场景都使用了它的双端操作能力。

特性描述
底层数据结构双向链表 Node<E>（prev / item / next）
实现接口List<E>, Deque<E>, Cloneable, Serializable
随机访问O(n)，需要从头部（或尾部）逐一遍历
头/尾操作O(1)，直接操作 first/last 指针
内存占用较大，每个节点额外存储 prev 和 next 两个引用
线程安全否
允许 null是

AbstractSequentialList 是为顺序访问优化的抽象类。与 AbstractList（随机访问）不同，它要求子类实现 listIterator()，而 LinkedList 的 get(int index) 通过 listIterator(index).next() 实现，每次都是 O(n)。

底层结构

节点定义

private static class Node<E> {
    E item;        // 节点数据
    Node<E> next;  // 后继节点
    Node<E> prev;  // 前驱节点

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

链表结构图解

方法速查表

方法时间复杂度描述
add(E e) / addLast(E e)O(1)尾部添加
addFirst(E e)O(1)头部添加
add(int index, E e)O(n)指定位置插入（需遍历定位）
get(int index)O(n)随机访问（需遍历）
getFirst() / getLast()O(1)获取头/尾元素
remove(int index)O(n)按索引删除（需遍历定位）
removeFirst() / removeLast()O(1)删除头/尾元素
remove(Object o)O(n)按值删除（需遍历查找）
contains(Object o)O(n)线性遍历查找
indexOf(Object o)O(n)线性遍历查找

Deque 接口方法对照

操作抛异常版本返回特殊值版本
头部插入addFirst(e)offerFirst(e)
尾部插入addLast(e)offerLast(e) / offer(e)
头部删除removeFirst() / remove()pollFirst() / poll()
尾部删除removeLast()pollLast()
头部查看getFirst() / element()peekFirst() / peek()
尾部查看getLast()peekLast()

完整示例

示例一：飞翔科技消息队列（作为 Deque 使用）

import java.util.*;

// 场景：飞翔科技内部消息通知系统，使用 LinkedList 作为消息队列
public class MessageQueue {
    public static void main(String[] args) {
        LinkedList<String> messageQueue = new LinkedList<>();

        // 1. 生产者：尾部添加消息（offerLast / addLast）
        messageQueue.offerLast("【系统通知】服务器将于 22:00 维护");
        messageQueue.offerLast("【审批提醒】小崔提交了请假申请");
        messageQueue.offerLast("【会议通知】周五 14:00 技术评审");
        messageQueue.offerLast("【工资通知】本月工资已发放");
        System.out.println("当前队列: " + messageQueue);

        // 2. 消费者：头部取出消息（pollFirst）
        System.out.println("\n=== 处理消息 ===");
        while (!messageQueue.isEmpty()) {
            String message = messageQueue.pollFirst();  // FIFO 出队
            System.out.println("处理: " + message);
        }
        System.out.println("队列已空: " + messageQueue);

        // 3. 紧急消息：头部插队（addFirst）
        messageQueue.addLast("消息A");
        messageQueue.addLast("消息B");
        messageQueue.addFirst("【紧急】CEO 大翔的指令，优先处理！");
        System.out.println("\n插队后: " + messageQueue);

        // 4. LIFO 栈模式：push/pop（实际上是 addFirst/removeFirst）
        LinkedList<String> history = new LinkedList<>();
        history.push("页面A");  // 等价于 addFirst
        history.push("页面B");
        history.push("页面C");
        System.out.println("\n=== 操作历史（栈模式：LIFO） ===");
        while (!history.isEmpty()) {
            System.out.println("回退到: " + history.pop());  // 等价于 removeFirst
        }
    }
}

运行输出：
当前队列: [【系统通知】服务器将于 22:00 维护, 【审批提醒】小崔提交了请假申请, 【会议通知】周五 14:00 技术评审, 【工资通知】本月工资已发放]

=== 处理消息 ===
处理: 【系统通知】服务器将于 22:00 维护
处理: 【审批提醒】小崔提交了请假申请
处理: 【会议通知】周五 14:00 技术评审
处理: 【工资通知】本月工资已发放
队列已空: []

插队后: [【紧急】CEO 大翔的指令，优先处理！, 消息A, 消息B]

=== 操作历史（栈模式：LIFO） ===
回退到: 页面C
回退到: 页面B
回退到: 页面A

示例二：LinkedList vs ArrayList 性能对比

import java.util.*;

// 场景：架构师白歌让小崔用 JMH 思想手写性能对比，理解两种 List 的适用场景
public class ListPerformanceCompare {
    public static void main(String[] args) {
        final int N = 50000;  // 数据量

        // === 头部插入对比 ===
        List<Integer> arrayList = new ArrayList<>();
        long start = System.currentTimeMillis();
        for (int i = 0; i < N; i++) {
            arrayList.add(0, i);  // 每次都要移动所有元素 O(n)
        }
        long arrayHeadTime = System.currentTimeMillis() - start;

        List<Integer> linkedList = new LinkedList<>();
        start = System.currentTimeMillis();
        for (int i = 0; i < N; i++) {
            linkedList.add(0, i);  // addFirst 本质 O(1)
        }
        long linkedHeadTime = System.currentTimeMillis() - start;

        System.out.println("=== 头部插入 " + N + " 次 ===");
        System.out.println("ArrayList 耗时:  " + arrayHeadTime + "ms  (O(n²) 总复杂度)");
        System.out.println("LinkedList 耗时: " + linkedHeadTime + "ms  (O(n) 总复杂度)");

        // === 随机访问对比 ===
        start = System.currentTimeMillis();
        for (int i = 0; i < N; i++) {
            arrayList.get(i);  // O(1)
        }
        long arrayGetTime = System.currentTimeMillis() - start;

        start = System.currentTimeMillis();
        for (int i = 0; i < N; i++) {
            linkedList.get(i);  // O(n)，每次从头/尾遍历，总 O(n²)
        }
        long linkedGetTime = System.currentTimeMillis() - start;

        System.out.println("\n=== 随机访问 " + N + " 次 ===");
        System.out.println("ArrayList 耗时:  " + arrayGetTime + "ms  (O(n) 总复杂度)");
        System.out.println("LinkedList 耗时: " + linkedGetTime + "ms  (O(n²) 总复杂度)");

        // === 尾部追加对比 ===
        arrayList.clear();
        linkedList.clear();
        start = System.currentTimeMillis();
        for (int i = 0; i < N; i++) {
            arrayList.add(i);
        }
        long arrayTailTime = System.currentTimeMillis() - start;

        start = System.currentTimeMillis();
        for (int i = 0; i < N; i++) {
            linkedList.add(i);
        }
        long linkedTailTime = System.currentTimeMillis() - start;

        System.out.println("\n=== 尾部追加 " + N + " 次 ===");
        System.out.println("ArrayList 耗时:  " + arrayTailTime + "ms");
        System.out.println("LinkedList 耗时: " + linkedTailTime + "ms");
    }
}

运行输出（参考值，实际因机器而异）：
=== 头部插入 50000 次 ===
ArrayList 耗时:  620ms  (O(n²) 总复杂度)
LinkedList 耗时: 3ms  (O(n) 总复杂度)

=== 随机访问 50000 次 ===
ArrayList 耗时:  2ms  (O(n) 总复杂度)
LinkedList 耗时: 2800ms  (O(n²) 总复杂度)

=== 尾部追加 50000 次 ===
ArrayList 耗时:  3ms
LinkedList 耗时: 2ms

选型决策：ArrayList vs LinkedList

关键认知：LinkedList 在中间位置插入也是 O(n)——因为需要遍历定位到插入位置（node(index) 方法），真正的 O(1) 仅发生在已持有节点引用或操作头尾时。

易错场景

反例一：用 for-i 遍历 LinkedList

小崔第一次写 LinkedList 遍历时沿用了 ArrayList 习惯：

// ❌ 错误：for-i 遍历 LinkedList（每次 get(i) 都是 O(n)）
LinkedList<String> list = new LinkedList<>();
// ... 填充数据
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));  // 每次 get 从头遍历，总 O(n²)
}

纠正：

// ✅ 正确：使用增强 for 或 Iterator（O(n) 总复杂度）
for (String s : list) {
    System.out.println(s);
}

// 或显式使用 Iterator
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    System.out.println(it.next());
}

增强 for 循环编译为 Iterator 遍历，Iterator 的 next() 记录当前位置，不会重复遍历。

反例二：并发修改 LinkedList 的中间节点

// ❌ 错误：多线程操作 LinkedList 可能导致节点指针断裂
LinkedList<String> list = new LinkedList<>();
list.add("A");
list.add("B");

// 线程1：在尾部添加
new Thread(() -> list.addLast("C")).start();
// 线程2：在头部删除
new Thread(() -> list.removeFirst()).start();
// 可能结果：size 计数错乱、节点链断裂导致 NPE

纠正：使用 Collections.synchronizedList(new LinkedList<>()) 或 ConcurrentLinkedDeque。

面试考点

Q1：ArrayList 和 LinkedList 的区别？如何选择？

维度ArrayListLinkedList
底层动态数组双向链表
随机访问O(1)O(n)
头尾增删O(n) / O(1)O(1)
内存占用紧凑（仅数据）每节点额外 2 个引用
缓存友好是（连续内存）否（节点分散）
实现接口ListList + Deque

选择规则：读多写少 + 随机访问 → ArrayList；频繁头尾增删 + 队列/栈 → LinkedList；尾部追加 + 遍历 → ArrayList（缓存友好）。大多数业务场景 ArrayList 是正确选择。

Q2：LinkedList 的 get(int index) 内部如何优化？

JDK 8 做了二分优化：如果 index < size/2，从 first 开始向后遍历；否则从 last 开始向前遍历。这让平均遍历距离从 n 降到 n/2，但复杂度仍是 O(n)。核心代码在 node(int index) 方法中。

Q3：为什么说 LinkedList 也能当栈和队列使用？

LinkedList 实现了 Deque 接口，天然支持双端操作。作为队列（FIFO）使用 offerLast + pollFirst；作为栈（LIFO）使用 push（即 addFirst）+ pop（即 removeFirst）。相比 Stack（遗留类，用 Vector 实现，性能差），LinkedList 是更好的栈选择。在 Java 6 后也可以用 ArrayDeque 替代，后者性能更优。

Q4：LinkedList 的内存占用为什么大？

每个元素需要创建独立的 Node 对象（对象头 + prev 指针 + item 指针 + next 指针），以 64 位 JVM（开启压缩指针）为例，一个 Node 约占用 24 字节对象头 + 4×3 = 12 字节引用 = 约 36 字节，而 ArrayList 每个元素只占 4 或 8 字节（引用）。此外，链表节点在堆上分散存储，不利用 CPU 缓存行（cache line），访问效率更低。

Q5：为什么 JDK 官方更推荐 ArrayDeque 而非 LinkedList 作为栈/队列？

ArrayDeque 基于循环数组，避免了 LinkedList 的节点对象开销和指针维护成本。它同时实现了 Deque 接口，头尾操作都是 O(1) 且常数因子更小。此外 ArrayDeque 的内存连续性好（缓存友好），且不产生大量小对象降低 GC 压力。唯一的不足是 ArrayDeque 不支持 null 元素（null 被用作特殊标记判断空槽），而 LinkedList 支持 null。