1. 引言

ArrayList 是 Java 集合框架中最常用的数据结构之一。它基于动态数组实现，提供了快速的随机访问和高效的尾部插入操作。无论是初学者还是资深开发者，`ArrayList` 都是日常开发中不可或缺的工具。本文将深入探讨 `ArrayList` 的实现原理、常见操作及其性能特点，并结合源码解析其内部机制。

2. ArrayList 的基本概念

2.1 什么是 ArrayList？

ArrayList 是 Java 集合框架中的一个类，实现了 `List` 接口。它基于动态数组实现，允许存储重复元素，并且元素是有序的（按插入顺序）。

2.2 ArrayList 的特点

有序性：元素按照插入顺序存储。
可重复性：允许存储重复的元素。
随机访问：通过索引可以快速访问元素。
非线程安全：ArrayList` 不是线程安全的，如果需要线程安全，可以使用 Collections.synchronizedList或 CopyOnWriteArrayList。

3. ArrayList 的实现原理

源码解析

public class ArrayList<E>{


	private static final int DEFAULT_CAPACITY = 10; //默认的初始容量大小，用于无参构造时


	private static final Object[] EMPTY_ELEMENTDATA = {};  //有参构造当传入的值为0时，使用数组赋值为一个空数组



	private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//无参构造时，创建的数组为空


	transient Object[] elementData; //存储ArrayList元素的数组缓冲区

	private int size; //数组的元素个数


	public ArrayList(int initialCapacity) { //有参构造
		if (initialCapacity > 0) { //如果提供的初始容量大于0，则
			this.elementData = new Object[initialCapacity];
		} else if (initialCapacity == 0) {
			this.elementData = EMPTY_ELEMENTDATA;//当初始值为0将一个空数组赋值给该elementData数组
		} else {//非法时，则抛出异常
			throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
		}
	}


	public ArrayList() {
		this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;//无参构造时，默认的数组大小为空数组
	}


	private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;



	public boolean add(E e) {//e为添加进来的元素
		ensureCapacityInternal(size + 1);  // 确保数组容量足够
		elementData[size++] = e;//合法则将元素添加到数组末尾当中，size++
		return true;
	}


	private void ensureExplicitCapacity(int minCapacity) {
		if (minCapacity - elementData.length > 0)//判断返回的最小容量与数组的长度，大于则需要扩容
			grow(minCapacity);
	}


	private static int calculateCapacity(Object[] elementData, int minCapacity) {
		if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//当数组为空数组时
			return Math.max(DEFAULT_CAPACITY, minCapacity);//返回默认长度10和最小容量之间的最大值
		}
		return minCapacity; //数组不为空时，返回最小容量
	}



	private void grow(int minCapacity) {
		// overflow-conscious code
		int oldCapacity = elementData.length;//原数组的长度
		int newCapacity = oldCapacity + (oldCapacity >> 1);//新长度为原长度的1.5倍
		if (newCapacity - minCapacity < 0)//判断扩容后的长度与数组所需最小长度进行比较，作差小于0，则新长度为minCapacity
			newCapacity = minCapacity;
		if (newCapacity - MAX_ARRAY_SIZE > 0) //判读是否溢出
			newCapacity = hugeCapacity(minCapacity);
		// minCapacity is usually close to size, so this is a win:
		elementData = Arrays.copyOf(elementData, newCapacity);//将原数组的内容进行拷贝到新数组中
	}


	private static int hugeCapacity(int minCapacity) {
		if (minCapacity < 0) // 小于0则异常
			throw new OutOfMemoryError();
		return (minCapacity > MAX_ARRAY_SIZE) ?//进行判断大小，防止数组长度溢出
				Integer.MAX_VALUE :
				MAX_ARRAY_SIZE;
	}


	public int indexOf(Object o) {//传入的元素o
		if (o == null) {//判断是否为空，为空则在数组中寻找为null的元素值，返回其下标
			for (int i = 0; i < size; i++)
				if (elementData[i] == null)
					return i;
		} else {//不为null，则进行比较元素的内容是否一致，返回下标
			for (int i = 0; i < size; i++)
				if (o.equals(elementData[i]))
					return i;
		}
//		都不满足返回-1
		return -1;
	}


	public int lastIndexOf(Object o) {
		if (o == null) {//为空时，从最后一个元素往前找，返回为null的元素
			for (int i = size - 1; i >= 0; i--)
				if (elementData[i] == null)
					return i;
		} else {//不为空时，从最后一个元素往前找，返回为o的元素的下标
			for (int i = size - 1; i >= 0; i--)
				if (o.equals(elementData[i]))
					return i;
		}
		//		都不满足返回-1
		return -1;
	}


	@SuppressWarnings("unchecked")//不需要进行下标的检查
	E elementData(int index) {
		return (E) elementData[index];//返回对应下标的值
	}


	public E remove(int index) {//传入下标
		rangeCheck(index);//判断下标是否超出

		E oldValue = elementData(index);//返回被删除的的元素值
0 1 2 3
			4-1-1
		int numMoved = size - index - 1;//需要移动的元素个数
		if (numMoved > 0)//大于0，则进行元素的拷贝，从原数组index+1的位置开始拷贝到elementData数组下标为index的位置开始到numMoved的长度
			System.arraycopy(elementData, index + 1, elementData, index, numMoved);
		elementData[--size] = null; // 数组长度-1，并将对应的值为null

		return oldValue;//返回被删除的的元素值
	}


	public boolean remove(Object o) {
		if (o == null) {//o为null时，开始寻找为null的下标
			for (int index = 0; index < size; index++)
				if (elementData[index] == null) {
					fastRemove(index);//下标传入，并进行覆盖操作
					return true;
				}
		} else {
			for (int index = 0; index < size; index++)
				if (o.equals(elementData[index])) {
					fastRemove(index);//下标传入，并进行覆盖操作
					return true;
				}
		}
//		都不满足则为false，失败
		return false;
	}



	private void fastRemove(int index) {
		int numMoved = size - index - 1;//需要移动的长度
		if (numMoved > 0)//大于0，则进行元素的拷贝，从原数组index+1的位置开始拷贝到elementData数组下标为index的位置开始到numMoved的长度
			System.arraycopy(elementData, index + 1, elementData, index, numMoved);
		elementData[--size] = null; // 数组长度-1，并将对应的值为null

	}


	public void clear() {
		for (int i = 0; i < size; i++)//将数组中所有元素的值为null
			elementData[i] = null;

		size = 0;//赋值数组元素的数量为0
	}


	private void rangeCheck(int index) {
		if (index >= size) //检查下标是否越界，大于则抛异常
			throw new IndexOutOfBoundsException();
	}
}

4. ArrayList 的性能分析

4.1 时间复杂度

随机访问：O(1)。
尾部插入：O(1)（平均情况）。
中间插入/删除：O(n)。

4.2 空间复杂度 

需要额外的空间用于动态扩容。

4.3 适用场景

适合：频繁读取和尾部插入的场景。
不适合：频繁中间插入/删除的场景。

5. 总结

ArrayList是 Java 中最常用的集合类之一，它的实现基于动态数组，具有以下特点：
优点：
随机访问速度快。
尾部插入效率高。
缺点：
中间插入/删除效率低。
需要额外的空间用于扩容。
适用场景：
适合读取多、修改少的场景。
不适合频繁插入/删除的场景

希望这篇博客对你有所帮助！如果有任何问题或建议，欢迎在评论区留言讨论。