# ArrayList 源码分析

# 1 简介

底层：Object[]，容量能动态增长。在添加大量元素前，会先调用 ensureCapacity 来增加 ArrayList 的容量，可以减少递增再分配的次数。

ArrayList 继承了 AbstractList，实现了 List，RandomAccess，Cloneable，Serializable 等接口。

• RandomAccess：标志接口，接口体是空的，只是用来表明 ArrayList 是支持快速随机访问的。
• Cloneable：能被克隆
• Serializable：可序列化

# 1.1 ArrayList 和 Vector 的区别

底层都是 Object[]，但是 ArrayList 线程不安全，Vector 线程安全。

# 1.2 ArrayList 和 LinkedList 的区别

1. 线程安全：ArrayList 和 LinkedList 都是线程不安全的。
2. 底层数据结构：ArrayList 是 Object[]，LinkedList 底层是双向链表。
3. 插入和删除：ArrayList 插入和删除元素的时间复杂度受元素位置的影响，为 O(n - i)；LinkedList 的插入和删除元素的时间复杂度不受插入元素位置的影响，都近似于 O(1)，但如果在指定位置插入和删除，需要先移动到指定位置再执行操作，时间复杂度近似于 O(n)。
4. 是否支持快速随机访问：ArrayList 支持，LinkedList 不支持。
5. 内存空间占用：ArrayList 需要在列表末尾预留一定的容量空间，LinkedList 的每一个元素都需要多消耗 pre 和 next 指针的空间。

# 2 核心源码分析

# 2.1 属性

1. 默认初始容量大小

   private static final int DEFAULT_CAPACITY = 10;
   

2. 元素个数

   private int size;
   

3. 存放数据的数组

   transient Object[] elementData
   

4. 空数组

   private static final Object[] EMPTY_ELEMENTDATA = {};
   

5. 用于默认大小实例的共享空数组实例

   private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}
   

# 2.2 构造函数

1. 无参

   public ArrayList(){
   	this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
   }
   

   注意：以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10。（用了懒汉式的单例设计模式）

2. 指定容量

   public ArrayList(int initialCapacity){
   	if (initialCapacity > 0){
   		this.elementData = new Object[initialCapacity];
   	} else if (initialCapacity == 0){
   		this.elementData = EMPTY_ELEMENTDATA;
   	} else {
   		//抛出异常
   	}
   }
   

3. 指定 collection

   public ArrayList(Collection<? extends E> c){
   	elementData = c.toArray();
   	if ((size = elementData.length) != 0){
   		if (elementData.getClass() != Object[].class){
   			elementData = Arrays.copyOf(elementData, size, Object[].class);
   		}
   	} else {
           this.elementData = EMPTY_ELEMENTDATA;
       }
   }
   

# 2.3 扩容机制

# 2.3.1 add 方法

# 2.3.2 ensureCapacityInternal 方法

# 2.3.3 ensureExplicitCapacity

# 2.3.4 grow 方法

# 2.3.5 hugeCapacity 方法

# 2.4 拷贝机制

# 2.5 ensureCapacity 方法