当前位置：首页 > article >正文

Java 中 List 源码解析：深度剖析与实现

article 2025/2/28 20:01:46

List 是 Java 中最常用的数据结构之一，广泛用于存储有序的元素集合。它是 Java 集合框架中的一个接口，提供了多种常见的实现，如 ArrayList、LinkedList、Vector 等。通过对 List 接口及其常见实现类的源码分析，开发者可以深入理解其内部机制和实现方式，进而优化应用程序的性能，做出更合适的选择。

本文将通过深入解析 List 接口及其常见实现（特别是 ArrayList 和 LinkedList）的源码，帮助开发者全面理解 Java 中 List 的实现原理和使用场景。

1. `List` 接口概述

在 Java 集合框架中，List 是一个有序的集合接口，表示一个元素序列，允许重复元素。与 Set 不同，List 允许按照插入顺序访问元素，并提供了元素插入和删除的灵活操作。

List 接口声明如下：

public interface List<E> extends Collection<E> {
    boolean add(E e);
    void add(int index, E element);
    E get(int index);
    E remove(int index);
    boolean contains(Object o);
    int size();
    Iterator<E> iterator();
    ListIterator<E> listIterator();
    List<E> subList(int fromIndex, int toIndex);
}

1.1 `List` 接口常用方法

add(E e)：添加元素到列表的尾部。
get(int index)：根据索引获取指定位置的元素。
remove(int index)：根据索引移除指定位置的元素。
contains(Object o)：检查列表是否包含指定元素。
size()：返回列表中元素的个数。
subList(int fromIndex, int toIndex)：返回从 fromIndex 到 toIndex 范围的子列表。

2. `ArrayList` 实现解析

ArrayList 是 List 接口的一个常见实现，底层基于动态数组实现，允许快速随机访问，但在插入和删除元素时性能较差，特别是在数组中间插入或删除时。

2.1 `ArrayList` 类结构

ArrayList 类的关键字段如下：

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    private static final int DEFAULT_CAPACITY = 10;
    transient Object[] elementData;
    private int size;

    public ArrayList() {
        this.elementData = new Object[DEFAULT_CAPACITY];
    }

    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else {
            this.elementData = new Object[DEFAULT_CAPACITY];
        }
    }

    public boolean add(E e) {
        ensureCapacity(size + 1);  // 保证容量足够
        elementData[size++] = e;
        return true;
    }

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

    public int size() {
        return size;
    }
}

展开

2.2 `elementData` 数组

ArrayList 底层是通过一个 Object[] elementData 数组来存储元素。这个数组的容量是动态变化的，默认容量为 10，当元素数量超过当前容量时，ArrayList 会自动增加容量，通常是扩展为原来容量的 1.5 倍。

2.3 `add(E e)` 方法

add 方法用于向 ArrayList 中添加元素。为了确保数组容量足够，add 方法会先调用 ensureCapacity 方法检查当前容量。如果当前容量不足以容纳新增元素，就会扩展容量。

private void ensureCapacity(int minCapacity) {
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
        int newCapacity = oldCapacity + (oldCapacity >> 1);  // 扩展为原容量的 1.5 倍
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

2.4 `get(int index)` 方法

get 方法通过索引直接访问 elementData 数组中的元素。它会先通过 rangeCheck 方法检查索引是否合法，如果不合法会抛出 IndexOutOfBoundsException 异常。

private void rangeCheck(int index) {
    if (index >= size) {
        throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }
}

2.5 `remove(int index)` 方法

remove 方法会将指定索引的元素移除，并将后续的元素向前移动，确保没有空缺。

public E remove(int index) {
    rangeCheck(index);
    E oldValue = (E) elementData[index];
    int numMoved = size - index - 1;
    if (numMoved > 0) {
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    }
    elementData[--size] = null;  // 清理空闲的元素
    return oldValue;
}

2.6 `ArrayList` 性能特点

随机访问：ArrayList 提供 O(1) 的时间复杂度来访问任何元素。
插入/删除：在数组的中间插入或删除元素时，性能较差，时间复杂度为 O(n)，因为需要移动数组中的元素。

2.7 使用场景

ArrayList 非常适合于需要频繁访问元素而不需要经常进行插入和删除操作的场景，如数据查询、缓存管理等。

3. `LinkedList` 实现解析

LinkedList 也是 List 接口的一个实现，但它与 ArrayList 不同，底层实现是双向链表。LinkedList 在进行插入和删除操作时具有优势，因为它只需要调整节点的引用，而不需要移动元素。

3.1 `LinkedList` 类结构

LinkedList 类的核心结构是双向链表，其中每个节点包含一个元素值和指向前后节点的引用。

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
    transient Node<E> first;
    transient Node<E> last;
    private int size;

    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 boolean add(E e) {
        linkLast(e);
        return true;
    }

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

    public E get(int index) {
        Node<E> node = node(index);
        return node.item;
    }

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

展开