Java List 源码解析——从基础到深度剖析

Java 集合框架中的 List 接口是开发中最常用的组件之一。无论是对数据的有序管理，还是对元素的高效访问，List 都发挥着重要作用。在这篇博客中，我们将从 List 的设计出发，逐步深入解析其主要实现类的源码，帮助你全面理解其工作原理和性能特点。

1. List 简介

1.1 什么是 List？

List 是 Java 集合框架（Java Collections Framework）中的一个接口，继承自 Collection 接口。它代表了一个有序的、可重复的元素集合。
例如：[A, B, C, A] 是一个合法的 List。

1.2 List 的主要实现类

在实际开发中，List 有以下几个常用实现类：

ArrayList：基于动态数组实现，适用于频繁随机访问的场景。
LinkedList：基于双向链表实现，适用于频繁插入和删除的场景。
CopyOnWriteArrayList：线程安全，适用于多读少写的并发场景。

2. List 接口设计

2.1 接口的定义

以下是 List 接口的核心定义，它扩展了 Collection 接口，增加了一些操作有序集合的功能：

public interface List<E> extends Collection<E> {
    void add(int index, E element);
    E get(int index);
    E remove(int index);
    int indexOf(Object o);
    int lastIndexOf(Object o);
    List<E> subList(int fromIndex, int toIndex);
    // 其他方法省略
}

2.2 特点

有序性：List 会按照元素插入的顺序进行存储。
允许重复：List 允许存储重复的元素。
随机访问：可以通过索引直接访问元素。

3. ArrayList 源码解析

ArrayList 是最常用的 List 实现类，其底层基于动态数组。以下是它的详细分析。

3.1 数据结构

ArrayList 使用一个动态数组（Object[] elementData）来存储元素。容量不足时，会进行扩容操作。

// ArrayList 的核心属性
transient Object[] elementData;
private int size; // 当前 ArrayList 的大小

3.2 核心方法解析

add(E e) 方法

add() 方法是向列表中添加元素的核心方法。以下是其简化的源码：

public boolean add(E e) {
    ensureCapacityInternal(size + 1); // 确保容量足够
    elementData[size++] = e;         // 添加元素
    return true;
}

容量检查
调用 ensureCapacityInternal(size + 1) 方法，确保数组有足够的容量来存储新元素。如果容量不足，会触发扩容。

扩容机制 grow() 方法用于扩容，扩容逻辑如下：

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容为原来的 1.5 倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    elementData = Arrays.copyOf(elementData, newCapacity);
}

get(int index) 方法

通过索引访问元素，复杂度为 O(1)：

public E get(int index) {
    rangeCheck(index); // 检查索引是否越界
    return elementData[index];
}

4. LinkedList 源码解析

LinkedList 是基于双向链表实现的 List，更适合频繁的插入和删除操作。

4.1 数据结构

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

4.2 核心方法解析

add(E e) 方法

add() 方法会在链表尾部插入新元素：

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

get(int index) 方法

get() 方法通过遍历链表找到目标节点，复杂度为 O(n)：

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. CopyOnWriteArrayList 源码解析

CopyOnWriteArrayList 是一种线程安全的 List，它通过写时复制（Copy-On-Write）实现线程安全。

5.1 数据结构

CopyOnWriteArrayList 的底层也是一个数组，但每次写操作都会复制整个数组。

5.2 核心方法解析

add(E e) 方法

public boolean add(E e) {
    synchronized (lock) { // 加锁保证线程安全
        Object[] elements = getArray(); // 获取当前数组
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1); // 复制数组
        newElements[len] = e;
        setArray(newElements); // 替换原数组
        return true;
    }
}