深度拆解 LinkedList 源码：双向链表的内存布局与操作艺术

iPadiPhone

598人浏览 · 2026-02-16 10:04:15

iPadiPhone · 2026-02-16 10:04:15 发布

前言

LinkedList 是 Java 集合框架中 List 和 Deque 接口的双重实现者。与 ArrayList 那种“紧凑型”的连续存储不同，LinkedList 采用了“分布式”的存储结构。这种结构赋予了它极强的灵活性，但也带来了不少性能上的折中。

一、核心组件：Node 节点

理解 LinkedList 的第一步，是理解它的基本单位 —— Node。

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;
    }
}

关键点：

双向性：每个节点都记住了自己的“前任”和“继任”。这使得 LinkedList 可以从头往后找，也可以从后往前找。
非连续空间：节点散落在内存的各个角落，靠指针连接。

二、核心成员变量

transient int size = 0; // 元素个数
transient Node<E> first; // 指向头节点的指针
transient Node<E> last;  // 指向尾节点的指针

有了 first 和 last，LinkedList 对头尾的操作性能达到了巅峰的 O(1)。

三、源码深度解析：增删改查

1. 插入操作：linkLast 与 linkBefore

当我们调用 add(E e) 时，默认是往尾部添加：

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; // 否则旧末尾的 next 指向新节点
    size++;
    modCount++;
}

资深视角：相比于 ArrayList 的扩容搬家，LinkedList 的插入只是简单的“牵手”过程，不需要拷贝数组，因此在纯插入动作上非常高效。

2. 查询操作：折半查找的优化

面试官问：“LinkedList 查询慢，为什么？”

Node<E> node(int index) {
    // 优化：看 index 靠哪头近，就从哪头开始数
    if (index < (size >> 1)) { // size >> 1 等于 size / 2
        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)。在数据量巨大时，这种挨个遍历的行为非常致命。

四、 LinkedList vs ArrayList：终极对决

1. 增删真的快吗？

头尾操作：LinkedList 完胜，复杂度 O(1)。
中间位置操作：LinkedList 需要先通过 node(index) 找到位置（O(n)），然后再执行插入。虽然插入动作本身快，但定位过程很慢。而 ArrayList 虽然定位快，但搬运数据慢。
结论：在实际测试中，如果是在随机位置增删，ArrayList 往往凭借更快的定位速度和 CPU 缓存友好性，表现反而优于 LinkedList。

2. 内存消耗

LinkedList 是典型的空间换时间（或者说空间换灵活性）。

ArrayList 浪费在数组末尾的空余空间。
LinkedList 每个数据都要额外存储两个 8 字节（64位系统）的指针。对于存储小型数据（如 Integer）来说，指针占用的空间甚至比数据本身还大。

五、 LinkedList 的多重身份：Deque 与栈

由于 LinkedList 实现了 Deque（双端队列）接口，它不仅能当列表用，还能当成栈或队列。

// 当作队列 (FIFO)
list.addLast("A");
list.pollFirst();

// 当作栈 (LIFO)
list.push("B"); // 实际调用 addFirst
list.pop();     // 实际调用 removeFirst

注意：虽然 LinkedList 能当栈用，但在高性能场景下，更推荐使用 ArrayDeque。

六、避坑指南：如何正确遍历 LinkedList？

千万不要用普通的 for 循环遍历 LinkedList！

// ❌ 灾难级代码
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

原因：每次 get(i) 都要从头（或尾）重新数一遍。遍历一个长度为 n 的链表，总复杂度会变成惊人的 O(n2)。

✅ 正确做法：使用 Iterator 或 for-each（底层也是 Iterator）。

for (String s : list) {
    System.out.println(s);
}

七、总结

在现代 Java 开发中，LinkedList 的地位其实比较尴尬。

缓存友好性：数组在内存中是连续的，对 CPU 缓存（Cache Line）非常友好；链表节点是散落的，容易导致 Cache Miss。
作者本人发言：LinkedList 的作者 Josh Bloch 曾在推特上表示：“Does anyone actually use LinkedList? I wrote it, and I never use it.”（有人真的用 LinkedList 吗？我写的它，但我从不用。）

建议：