LinkedList 深度分析

作者：Ethan.Yang
博客：https://blog.ethanyang.cn (opens new window)

---

基于JDK11进行分析, 大部分公司已经开始使用JDK11

一、继承体系

继承结构

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

父类/接口	作用	责任说明
AbstractSequentialList	抽象骨架	为基于顺序访问（如链表）的 List 提供模板实现
AbstractList	抽象骨架	复用大部分 List 接口的公共实现逻辑
List	行为规范	定义有序可重复集合的基本操作，如 add、get、remove 等
Deque	行为规范	定义双端队列操作，如 addFirst、removeLast 等
Queue	行为规范	定义队列操作，如 offer、poll、peek 等
Cloneable	接口能力	支持对象浅拷贝，通过 clone() 方法实现
Serializable	接口能力	支持对象序列化，可跨 JVM 传输或持久化存储

---

二、底层数据结构解析

LinkedList 是一个基于 双向链表（Doubly Linked List） 实现的集合容器，结构简单却灵活，适用于插入、删除频繁的场景。本节将从源码角度出发，深度解析其底层结构与运行机制。

本章节以原理结构为主, 具体源码解析可查看核心方法源码解析

核心字段

// 当前链表中元素数量
transient int size = 0;

// 指向链表头部的节点
transient Node<E> first;
// 指向链表尾部的节点
transient Node<E> last;

双向链表的基础字段

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

构造方法解析

public LinkedList() {
}

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}


public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    for (Object o : a)
        linkLast((E) o);
    return true;
}

• 默认构造器：初始化为空链表，first 和 last 都为 null。

• 带参数构造器：允许通过传入其他集合快速初始化，调用 addAll(c) 完成元素拷贝。

注意：链表的添加操作不需要像 ArrayList 一样考虑扩容问题，因此效率稳定。

fail-fast 的核心机制

LinkedList 继承自 AbstractList，同样具备 modCount 字段，用于记录结构性修改次数：

• 每次插入或删除元素时，modCount++；
• 迭代器在创建时保存 expectedModCount，在 next() 时对比是否一致；
• 若检测到 modCount 被外部修改（非迭代器），则抛出 ConcurrentModificationException，实现 fail-fast。

---

三、核心方法解析(JDK11)

增

1. 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;
       size++;
       modCount++;
   }
   

   • 常数时间复杂度 O(1)。
   • 修改前后指针，适配空链表场景。

2. add(int index, E element)

   指定位置插入

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

删

remove(int index)

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

// 查找到删除的结点
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;
    }
}

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;
    size--;
    // fair-fast机制
    modCount++;
    return element;
}

• 只修改相邻指针，不涉及数组拷贝；
• 时间复杂度 O(n)。

remove(Object o)

• 从头节点开始遍历匹配，首次命中即删除；
• 时间复杂度为 O(n)。

查

get(int index)

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

• 首先进行参数检查, 由于是链表不考虑扩容

• 元素的获取依赖于 node(int index) 方法进行定位：

  • 采用前后分段遍历策略，提升中间位置访问性能。

  • 时间复杂度为 O(n)，最优为 O(1)（头/尾），最差 O(n)（中间）。

替换元素

set(int index, E element)

public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

• 不修改结构，仅替换值；

• modCount 不变；

• 时间复杂度 O(n)。

清空列表

clear()

public void clear() {
    for (Node<E> x = first; x != null;) {
        Node<E> next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    first = last = null;
    size = 0;
    modCount++;
}

• 所有节点引用置空，有利于 GC；

• 时间复杂度 O(n)。

modCount说明

• 定义在 AbstractList 中，用于检测迭代过程中集合结构变化，触发 ConcurrentModificationException，实现 fail-fast 机制。具体流程与ArrayList类似。

---

四、常见问题

并发风险：非线程安全

问题描述

LinkedList 并非线程安全。多个线程同时对其读写时，可能引发如下问题：

• 数据覆盖：两个线程同时 add，最后一个 add 的节点可能覆盖另一个。
• 结构损坏：并发修改导致 next 或 prev 丢失，链表结构被破坏。
• ConcurrentModificationException：在迭代过程中被结构性修改。

示例

LinkedList<String> list = new LinkedList<>();

Runnable writer = () -> {
    for (int i = 0; i < 1000; i++) {
        list.add("item" + i); // 非线程安全
    }
};

new Thread(writer).start();
new Thread(writer).start();

可能抛异常或结果异常（元素丢失、链表断裂）

解决方案

• 使用 外部同步：

Collections.synchronizedList(new LinkedList<>());

• 使用 CopyOnWriteArrayList（读多写少），但它是基于数组的，非链表结构；
• 若需线程安全 + 链表特性，考虑 ConcurrentLinkedDeque 或 LinkedBlockingDeque；
• 自定义加锁（如 ReentrantLock）包裹操作逻辑；

在多线程场景下 避免直接使用 LinkedList，可根据场景选择合适的线程安全容器。

迭代过程中修改，导致 ConcurrentModificationException

问题描述

在使用增强 for 或 Iterator 遍历时对结构进行修改，会抛出异常：

for (String s : list) {
    if (s.equals("a")) {
        list.remove(s); // 抛出 ConcurrentModificationException
    }
}

原因：LinkedList 使用了 fail-fast 机制，modCount 与迭代器中的 expectedModCount 不一致就抛异常。

解决方案

• 使用 Iterator 的 remove() 方法或使用 Java8 removeIf()

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    if (iterator.next().equals("a")) {
        iterator.remove(); // 正确方式
    }
}

list.removeIf(s -> s.equals("a"));

空指针异常

问题描述

当链表为空时访问 getFirst() / getLast()，会抛出 NoSuchElementException，而非返回 null。

LinkedList<String> list = new LinkedList<>();
list.getFirst(); // 抛异常

解决方案

使用对应的“安全版”方法：

方法	安全版本
getFirst()	peekFirst()
getLast()	peekLast()
remove()	poll()

这些方法在链表为空时返回 null，更安全。

性能陷阱：随机访问低效

没啥好说的, 链表随机访问需要进行遍历

内存泄漏：未释放节点引用

问题描述

LinkedList 使用双向链表结构，节点之间互相引用。如果外部持有旧节点引用，可能导致对象无法被 GC，造成内存泄漏。

解决方案

• 确保不持有无用节点引用；
• clear() 方法已经做了引用断开操作，应优先使用；

public void clear() {
    for (Node<E> x = first; x != null;) {
        Node<E> next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    first = last = null;
    size = 0;
    modCount++;
}