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 接口，增加了一些操作有序集合的功能：

java">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）来存储元素。容量不足时，会进行扩容操作。

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

3.2 核心方法解析

add(E e) 方法

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

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

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

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

java">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)：

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

4. LinkedList 源码解析

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

4.1 数据结构

LinkedList 使用内部的 Node 类表示链表节点：

java">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() 方法会在链表尾部插入新元素：

java">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;                     // 更新第一个节点elsel.next = newNode;                    // 否则更新前节点的 nextsize++;
}

get(int index) 方法

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

java">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) 方法

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