小菜鸟

java菜鸟号正在起航

0%

LinkedList详解

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 7.8k 阅读时长 ≈ 7 分钟

LinkedList 源码深度解析（基于 JDK 8）

LinkedList 是 Java 集合框架中另一种重要的 List 实现类，基于双向链表实现，与 ArrayList 形成互补：ArrayList 擅长随机访问，而 LinkedList 擅长插入和删除操作。本文将从继承关系、链表结构、核心方法及迭代器实现等方面，全面解析 LinkedList 的工作原理。

LinkedList 核心特性与继承关系

核心特性

  • 有序性：元素按插入顺序存储，支持通过索引访问（但效率低于 ArrayList）。
  • 可重复性：允许存储重复元素和 null 值。
  • 双向链表：底层通过节点的前驱（prev）和后继（next）指针维护元素关系，无需连续内存空间。
  • 非线程安全：多线程并发修改可能导致数据不一致（需手动同步或使用并发容器）。
  • 实现 Deque 接口：支持作为队列（FIFO）、栈（LIFO）或双向队列使用，提供丰富的首尾操作方法。

继承关系

LinkedList

1
2
3
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
  • 继承 AbstractSequentialList：复用了顺序访问集合的基础实现（如 get、add 等依赖迭代器的方法）。
  • 实现 List：遵循 List 接口规范，支持列表的基本操作。
  • 实现 Deque：支持双端队列操作（如 addFirst、pollLast 等），可作为队列或栈使用。
  • 实现 Cloneable：支持克隆（浅拷贝，节点引用被复制，但元素对象本身不复制）。
  • 实现 Serializable：支持序列化，通过自定义 writeObject 和 readObject 方法优化序列化过程。

核心结构：双向链表与节点

LinkedList 的核心是双向链表，由节点（Node）组成，每个节点包含元素值、前驱节点和后继节点的引用。

节点类（Node）

1
2
3
4
5
6
7
8
9
10
11
12
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;         // 尾节点（末元素）

链表状态约束：

  • 空链表：first == null && last == null 且 size == 0。
  • 非空链表：
    • 头节点的 prev == null；
    • 尾节点的 next == null；
    • 每个节点的 prev.next 和 next.prev 均指向自身（确保双向引用一致）。

构造函数解析

LinkedList 提供两种构造函数，用于初始化链表：

无参构造器

1
2
public LinkedList() {
}
  • 初始化一个空链表（first = null，last = null，size = 0）。

基于集合初始化

1
2
3
4
public LinkedList(Collection<? extends E> c) {
    this();         // 调用无参构造器初始化空链表
    addAll(c);      // 将集合元素批量添加到链表
}
addAll 方法详解（批量添加元素）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index); // 检查插入位置是否合法（0 ≤ index ≤ size）

    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0) return false; // 集合为空则直接返回

    // 找到插入位置的前驱节点（pred）和后继节点（succ）
    Node<E> pred, succ;
    if (index == size) { 
        // 从尾部插入：前驱为尾节点，后继为 null
        succ = null;
        pred = last;
    } else { 
        // 从中间插入：后继为 index 处的节点，前驱为后继的前驱
        succ = node(index);
        pred = succ.prev;
    }

    // 遍历集合元素，创建节点并插入链表
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null); // 新节点的后继暂时为 null
        if (pred == null) {
            // 前驱为 null 表示插入到头节点位置
            first = newNode;
        } else {
            // 前驱节点的后继指向新节点
            pred.next = newNode;
        }
        pred = newNode; // 移动前驱指针，准备下一个节点插入
    }

    // 连接插入的最后一个节点与原后继节点
    if (succ == null) {
        // 从尾部插入：更新尾节点为最后一个新节点
        last = pred;
    } else {
        // 从中间插入：最后一个新节点的后继指向原后继节点，原后继节点的前驱指向新节点
        pred.next = succ;
        succ.prev = pred;
    }

    size += numNew;   // 更新链表长度
    modCount++;       // 记录结构修改次数（用于迭代器的 fail-fast 机制）
    return true;
}

关键辅助方法 node(int index)：
根据索引查找节点，通过二分优化减少遍历次数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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/2)，虽比 ArrayList 的 O(1) 慢，但比全量遍历更高效。

核心方法解析

添加元素

（1）尾部添加（add(E e)）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean add(E e) {
    linkLast(e); // 调用 linkLast 方法添加到尾部
    return true;
}

// 将元素添加到链表尾部
void linkLast(E e) {
    final Node<E> l = last; // 保存当前尾节点
    final Node<E> newNode = new Node<>(l, e, null); // 新节点的前驱为当前尾节点，后继为 null
    last = newNode; // 更新尾节点为新节点
    if (l == null) {
        // 若原链表为空，新节点同时作为头节点
        first = newNode;
    } else {
        // 原尾节点的后继指向新节点
        l.next = newNode;
    }
    size++;
    modCount++;
}
  • 时间复杂度 O(1)，无需遍历，直接操作尾节点。
（2）指定位置添加（add(int index, E element)）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public void add(int index, E element) {
    checkPositionIndex(index); // 检查索引合法性

    if (index == size) {
        // 索引等于长度，视为尾部添加
        linkLast(element);
    } else {
        // 中间插入：先找到 index 处的节点，再插入其前方
        linkBefore(element, node(index));
    }
}

// 将元素插入到 succ 节点之前
void linkBefore(E e, Node<E> succ) {
    // succ 是 index 处的节点，pred 是其前驱
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ); // 新节点的前驱为 pred，后继为 succ
    succ.prev = newNode; // succ 的前驱指向新节点
    if (pred == null) {
        // pred 为 null 表示 succ 是头节点，更新头节点为新节点
        first = newNode;
    } else {
        // pred 的后继指向新节点
        pred.next = newNode;
    }
    size++;
    modCount++;
}
  • 时间复杂度 O(n)，主要耗时在 node(index) 查找节点（O(n/2)），插入操作本身为 O(1)。

删除元素

（1）删除指定索引元素（remove(int index)）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public E remove(int index) {
    checkElementIndex(index); // 检查索引是否为有效元素索引（0 ≤ index < size）
    return unlink(node(index)); // 找到节点并删除
}

// 从链表中移除节点 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) {
        // 前驱为 null 表示 x 是头节点，更新头节点为 next
        first = next;
    } else {
        // 前驱节点的后继指向 next，断开 x 的前驱引用
        prev.next = next;
        x.prev = null;
    }

    // 处理后继节点
    if (next == null) {
        // 后继为 null 表示 x 是尾节点，更新尾节点为 prev
        last = prev;
    } else {
        // 后继节点的前驱指向 prev，断开 x 的后继引用
        next.prev = prev;
        x.next = null;
    }

    x.item = null; // 清空元素，帮助 GC 回收
    size--;
    modCount++;
    return element; // 返回被删除的元素
}
  • 时间复杂度 O(n)，主要耗时在 node(index) 查找节点，删除操作本身为 O(1)。
（2）删除头节点 / 尾节点（Deque 接口方法）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 删除并返回头节点元素（栈的 pop 操作）
public E removeFirst() {
    final Node<E> f = first;
    if (f == null) throw new NoSuchElementException();
    return unlinkFirst(f);
}

// 删除并返回尾节点元素
public E removeLast() {
    final Node<E> l = last;
    if (l == null) throw new NoSuchElementException();
    return unlinkLast(l);
}

// 内部方法：删除头节点
private E unlinkFirst(Node<E> f) {
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // 帮助 GC
    first = next;
    if (next == null) {
        last = null; // 链表为空
    } else {
        next.prev = null;
    }
    size--;
    modCount++;
    return element;
}
  • 时间复杂度 O(1)，直接操作头 / 尾节点，无需遍历。

获取元素（get(int index)）

1
2
3
4
public E get(int index) {
    checkElementIndex(index); // 检查索引合法性
    return node(index).item; // 查找节点并返回元素
}
  • 时间复杂度 O(n)，依赖 node(index) 方法遍历查找，效率低于 ArrayList 的 O(1)。

迭代器与双向遍历

LinkedList 的迭代器实现 ListItr 支持双向遍历（向前 / 向后），继承自 ListIterator 接口，比普通 Iterator 功能更丰富。

迭代器核心实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned; // 最后返回的节点（用于 remove/set 操作）
    private Node<E> next;         // 下一个要返回的节点
    private int nextIndex;        // 下一个节点的索引
    private int expectedModCount = modCount; // 预期的修改次数（用于 fail-fast）

    // 初始化迭代器，从 index 位置开始
    ListItr(int index) {
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }

    // 是否有下一个元素
    public boolean hasNext() {
        return nextIndex < size;
    }

    // 获取下一个元素（向前遍历）
    public E next() {
        checkForComodification(); // 检查并发修改
        if (!hasNext()) throw new NoSuchElementException();

        lastReturned = next;
        next = next.next; // 移动到下一个节点
        nextIndex++;
        return lastReturned.item;
    }

    // 是否有上一个元素
    public boolean hasPrevious() {
        return nextIndex > 0;
    }

    // 获取上一个元素（向后遍历）
    public E previous() {
        checkForComodification();
        if (!hasPrevious()) throw new NoSuchElementException();

        // 若 next 为 null，说明在尾部，上一个元素是尾节点
        lastReturned = next = (next == null) ? last : next.prev;
        nextIndex--;
        return lastReturned.item;
    }

    // 其他方法：remove、set、add 等（均通过操作节点实现）
}

Fail-Fast 机制

与 ArrayList 类似，ListItr 通过 expectedModCount 和 modCount 检测并发修改：

1
2
3
4
5
final void checkForComodification() {
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}
  • 迭代过程中若通过非迭代器方法（如 list.remove(index)）修改链表结构，会导致 modCount 变化，触发异常。

LinkedList 与 ArrayList 的对比

特性 LinkedList ArrayList
底层结构 双向链表 动态数组
随机访问 慢（O(n)） 快（O(1)）
插入 / 删除（中间） 快（O(1) 插入，O(n) 查找） 慢（O(n) 移动元素）
插入 / 删除（首尾） 快（O(1)） 尾部快（O(1)），头部慢（O(n)）
内存占用 高（需存储前后指针） 低（连续内存，可能有冗余）
遍历效率 迭代器遍历高效 普通 for 循环高效
适用场景 频繁增删（尤其是中间位置） 频繁查询，少量增删

使用注意事项

1. 避免随机访问

LinkedList 的 get(index) 方法效率低（O(n)），若需频繁按索引访问元素，优先选择 ArrayList。

2. 利用 Deque 接口方法

LinkedList 实现了 Deque 接口，可高效作为队列或栈使用：

1
2
3
4
5
6
7
8
9
// 作为队列（FIFO）
LinkedList<String> queue = new LinkedList<>();
queue.add("a"); // 尾部添加
queue.poll();   // 头部删除

// 作为栈（LIFO）
LinkedList<String> stack = new LinkedList<>();
stack.push("a"); // 头部添加（等价于 addFirst）
stack.pop();     // 头部删除（等价于 removeFirst）

3. 线程安全问题

多线程环境下需保证线程安全：

  • 手动同步：synchronized (list) { ... }
  • 使用并发容器：如 ConcurrentLinkedQueue（适用于队列场景）。

4. 批量操作优化

批量添加元素时，addAll 比多次调用 add 更高效（减少 modCount 更新和节点引用调整次数）。

相关文章

欢迎关注我的其它发布渠道