LinkedList 源码分析

LinkedList 源码分析

1. 概述

LinkedList 是 Java 集合框架中的一个实现类，基于双向链表实现，提供了较高效的插入和删除操作。它实现了 List、Deque、Queue 接口，并支持序列化。

---

2. 类声明

public class LinkedList<E> extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Queue<E>, Cloneable, Serializable {
    // 成员变量及方法
}

• 继承关系：
  • AbstractSequentialList<E>：提供了基于链表的基础实现。
• 实现的接口：
  • List<E>：实现 List 接口。
  • Deque<E>：支持双端队列的操作。
  • Queue<E>：实现队列接口，支持 FIFO 操作。
  • Cloneable：支持克隆。
  • Serializable：支持序列化。

---

3. 关键成员变量

transient Node<E> first; // 链表的第一个节点
transient Node<E> last;  // 链表的最后一个节点
private int size;        // 链表的大小

• first：指向链表头部的节点。
• last：指向链表尾部的节点。
• size：记录链表的元素个数。

---

4. 构造方法

(1) 无参构造方法

public LinkedList() {
    first = last = null;
    size = 0;
}

• 初始化空链表，first 和 last 都为 null，size 为 0。

(2) 通过集合初始化的构造方法

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);  // 将集合元素加入链表
}

• 通过将指定集合中的元素添加到当前链表来初始化链表。

---

5. 核心方法

(1) add(E e) 方法

public boolean add(E e) {
    linkLast(e); // 链接到链表的尾部
    return true;
}

• 通过 linkLast() 将元素添加到链表的尾部。

(2) linkLast(E e) 方法

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

• 创建新节点并将其添加到链表尾部。
• 更新尾节点 last。
• 如果链表为空，则新节点也是头节点 first。

(3) get(int index) 方法

public E get(int index) {
    checkElementIndex(index);
    return node(index).item; // 返回指定索引的元素
}

• 使用 node(index) 获取指定索引的节点，并返回其元素。

(4) node(int 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;
    }
}

• 如果索引小于链表的中间位置，从头节点开始遍历，否则从尾节点开始遍历。
• 返回指定索引位置的节点。

(5) remove(int index) 方法

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index)); // 删除指定节点
}

• 使用 unlink(node(index)) 删除指定索引的节点。

(6) unlink(Node<E> node) 方法

private E unlink(Node<E> node) {
    final E element = node.item;
    final Node<E> next = node.next;
    final Node<E> prev = node.prev;

    if (prev == null)
        first = next;
    else
        prev.next = next;

    if (next == null)
        last = prev;
    else
        next.prev = prev;

    node.item = null;
    node.next = null;
    node.prev = null;
    size--;
    modCount++;
    return element;
}

• 删除节点并更新前后节点的链接。
• 如果删除的是头节点或尾节点，分别更新 first 或 last。
• 清理节点的引用，减少链表大小。

---

6. 遍历方法

LinkedList 支持通过 Iterator 或增强型 for-each 循环进行遍历。

使用增强型 for-each 循环遍历：

for (E item : linkedList) {
    System.out.println(item);
}

使用 Iterator 遍历：

Iterator<E> iterator = linkedList.iterator();
while (iterator.hasNext()) {
    E item = iterator.next();
    System.out.println(item);
}

---

7. 优缺点

优点：

• 插入和删除操作的时间复杂度为 O(1)，特别适用于频繁修改链表（如添加、删除元素）的场景。
• 支持双端队列操作，既可以从头部添加/删除元素，也可以从尾部添加/删除元素。

缺点：

• 随机访问效率较低，时间复杂度为 O(n)，相比 ArrayList，查找元素速度较慢。
• 内存开销较大，每个元素除了存储数据外，还需要存储两个额外的引用（prev 和 next）。

---

8. 总结

LinkedList 通过双向链表实现了 List、Deque 和 Queue 接口，具有高效的插入和删除操作，适合在元素频繁修改的场景下使用。相比 ArrayList，LinkedList 在访问元素时性能较差，但在插入/删除操作上有较大的优势。