LinkedList / Deque 链表类源码

概述

LinkedList 是 Java 集合框架中基于双向链表实现的 List 和 Deque 双接口类。它同时实现了 List（有序列表）、Deque（双端队列）和 Queue（队列）三个接口，因此可以当做列表、栈、队列或双端队列使用。

AbstractSequentialList 提供了基于迭代器的顺序访问骨架，LinkedList 在其基础上通过 Node 节点实现了链式存储。

本文基于 OpenJDK 21 源码，从双向链表结构开始，逐层深入到插入、删除、查找、双端操作等核心实现。

本文基于 OpenJDK 21 源码分析。

---

核心源码解析

① Node 的双向链表结构

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {

    transient int size = 0;
    transient Node<E> first;
    transient Node<E> last;

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

• first 指向链表头节点，last 指向链表尾节点
• 每个 Node 包含前驱指针 prev、后继指针 next 和元素 item
• transient 修饰：自定义序列化只遍历实际节点

② linkLast(E) / linkFirst(E) 的插入

头插入：

private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

尾插入：

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

• linkFirst()：新节点 prev=null，next=原first
• linkLast()：新节点 prev=原last，next=null
• 空链表时 first=last=null，插入后同时更新头尾
• addFirst(E) / addLast(E) / add(E) / offer(E) 内部都调用 linkFirst() / linkLast()

③ unlink(Node<E>) 的移除

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;
        x.prev = null;
    }

    if (next == null) {
        last = prev;           // 删除尾节点
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;             // 辅助 GC
    size--;
    modCount++;
    return element;
}

• 断开前驱和后继指针
• 被删除节点所有引用置 null，辅助 GC

④ get(int) 的二分查找

public E get(int index) {
    checkElementIndex(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;
    }
}

• size >> 1 即 size/2
• 索引在前半部分 → 从头遍历
• 索引在后半部分 → 从尾遍历
• 时间复杂度 O(n/2)，而非 O(1)

⑤ add(int, E) 的 node(index)

public void add(int index, E element) {
    checkPositionIndex(index);
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

• 找到指定位置的 node(index)
• 新节点插入到该节点之前
• 若 index == size 则直接尾插

⑥ Deque 接口的双端操作

LinkedList 实现了完整的 Deque 接口，提供双端操作：

操作	头	尾
插入（异常）	addFirst(e)	addLast(e)
插入（特殊值）	offerFirst(e)	offerLast(e)
移除（异常）	removeFirst()	removeLast()
移除（特殊值）	pollFirst()	pollLast()
查看（异常）	getFirst()	getLast()
查看（特殊值）	peekFirst()	peekLast()

栈操作（来自 Deque）：

public void push(E e) { addFirst(e); }
public E pop() { return removeFirst(); }

队列操作：

public boolean offer(E e) { return add(e); }  // 尾插
public E poll() { return (first == null) ? null : unlinkFirst(); }
public E peek() { return (first == null) ? null : first.item; }

⑦ DescendingIterator 逆序遍历

private class DescendingIterator implements Iterator<E> {
    private final ListItr itr = new ListItr(size);
    public boolean hasNext() { return itr.hasPrevious(); }
    public E next() { return itr.previous(); }
    public void remove() { itr.remove(); }
}

• 内部委托 ListItr.previous() 实现
• 从链表尾部向头遍历，使用 prev 指针

descendingIterator() 方法返回该迭代器，支持逆序遍历。

⑧ LinkedList vs ArrayList 选型

操作	ArrayList	LinkedList
随机访问 get(int)	O(1)	O(n)
尾部插入 add(E)	O(1) 均摊	O(1)
头部插入 addFirst(E)	O(n)	O(1)
中间插入 add(int, E)	O(n)	O(n)
内存占用	较少（仅数组+元素）	较多（节点指针开销）
迭代效率	更高（CPU 缓存友好）	较低（链表节点分散）
适用场景	随机访问多、尾部插入多	头尾操作多、频繁中间插入

---

总结

LinkedList 的双向链表设计使其在头尾插入和删除场景中具有 O(1) 的高效性能，同时通过 Deque 接口支持栈、队列和双端队列操作。但其随机访问 O(n) 的开销使得在需要频繁索引访问的场景中不如 ArrayList 高效。

日常开发中，ArrayList 是绝大多数场景的首选；LinkedList 适用于需要频繁头尾操作或需要 Deque 双端功能的场景。