Java集合-LinkedList

前言

LinkedList 是 Java 集合框架中的一个双向链表实现，位于 java.util 包下。
它实现了 List、Deque 和 Queue 接口，因此既可以作为列表（List），也可以作为双端队列（Deque）或队列（Queue）使用。
与 ArrayList 不同，LinkedList 的底层数据结构是链表，而不是数组，因此它在插入和删除操作上有优势，但在随机访问上性能较低。

1
2
3

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

源码分析

从 LinkedList 的核心实现入手，分析它的数据结构以及常用方法的实现原理。以下源码为 JDK1.8 版本。

数据结构

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

链表的整体结构由以下字段维护：

1
2
3

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

size：记录链表中元素的数量。
first：指向链表的第一个节点。
last：指向链表的最后一个节点。

构造方法

LinkedList 提供了两种构造方法：无参构造，带集合参数的构造：

// 无参构造
public LinkedList() {
} // 初始化一个空的链表，first 和 last 均为 null

// 带集合参数的构造
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
} // 将指定集合中的元素添加到链表中

核心方法分析

在 LinkedList 中，最为核心的是获取、插入、删除这几个方法。

获取 `get(int index)`

LinkedList 底层基于链表实现，要想访问指定位置的元素只能够从链表的头节点或尾节点向后查找：

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

获取元素的时间复杂度为 $O(n)$，因为需要从头或者从尾遍历元素。

插入 `add(E e)`

向链表尾部添加元素：

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;             // 原尾节点的 next 指向新节点
    size++;
    modCount++;                       // 结构修改计数器，用于 fail-fast
}

尾插的时间复杂度为 $O(1)$，因为只需更新指针。

在指定位置添加一个元素：

public void add(int index, E element) {
    checkPositionIndex(index);         // 检查索引是否合法

    if (index == size)                 // 如果插入位置是尾部
        linkLast(element);             // 调用尾部插入方法
    else                               // 否则在指定位置插入
        linkBefore(element, node(index)); // 在目标节点前插入
}

private void linkBefore(E e, Node<E> succ) {
    // succ 是目标节点（successor，后继节点）
    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++;
}

根据插入位置选择尾部插入（linkLast）或中间插入（linkBefore）。若 index == size，调用 linkLast，时间复杂度为 $O(1)$。

总体时间复杂度为 $O(n)$，用于查找需要插入的位置。

删除 `remove(int index)`

根据索引删除元素：

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

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

删除操作中，查找待删除节点的时间复杂度为 $O(n)$，删除元素时间复杂度为 $O(1)$。

删除后将节点的前后指针置为 null，帮助垃圾回收。

双端队列操作

作为 Deque 的实现，LinkedList 提供了头尾操作，如 addFirst 和 addLast：

public void addFirst(E 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++;
}

头尾操作的时间复杂度均为 $O(1)$。

后记

LinkedList 的优缺点如下：

优点：

插入/删除效率高：在已知节点位置时，只需调整指针，时间复杂度为 $O(1)$。
动态扩展：无需预分配容量，适合动态大小的场景。
双端队列支持：灵活支持头尾操作。

缺点：

随机访问慢：需要遍历链表，时间复杂度为 $O(n)$。
内存开销大：每个节点都需要额外的指针（prev 和 next），比数组结构占用更多内存。
非线程安全：多线程环境中需额外同步措施。

当需要进行频繁的插入/删除操作（如队列、栈实现），或需要双端队列功能时，推荐使用 LinkedList；需要大量随机访问的场景建议使用 ArrayList。