ArrayList源码分析

一、ArrayList简介

ArrayList的底层数据结构是动态数组，它的容量可以动态增长。在添加元素前可以使用ensureCapacity来增大数组的大小。

ArrayList继承自AbstractList，实现了List, RandomAccess, Cloneable, Serializable这些接口。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
        
}

• List: 表明它是一个列表，支持添加、删除、查找等操作，并且可以通过下标进行访问。
• RandomAccess:这是一个标识接口，标志该类支持快速随机访问。
• Cloneable:表明该类具有拷贝能力，支持深拷贝和浅拷贝。
• Serializble:表明该类可以进行序列化操作，可以将对象转为字节流进行持久化存储或网络传输。

ArrayList和Vector的区别

• ArrayList是List的主要实现类，底层使用Object[]数组存储，线程不安全；
• Vector是List的古老实现类，底层使用Object[]数组存储，线程安全。

ArrayList可以存储null值吗

ArrayList中可以存储任何类型对象，包括null值，不过不建议这么做，因为null值无意义，会让代码难以维护（如忘记判空处理导致空指针异常）。

ArrayList与LinkedList区别

• 是否线程安全：ArrayList和LinkedList都是不同步的，即不保证线程安全。
• 底层数据结构：ArrayList底层使用Object[]数组；LinkedList底层使用双向链表。
• 插入和删除是否受元素位置影响：
  • ArrayList使用数组存储，在末尾插入和删除时间复杂度为O(1)，在指定位置i插入和删除时间复杂度为O(n)。
  • LinkedList使用链表存储，在头尾插入和删除时间复杂度为O(1)，但是在指定位置插入和删除时间复杂度为O(n)。
• 是否支持快速随机访问：ArrayList支持，LinkedList不支持。
• 内存空间占用：ArrayList的空间浪费主要体现在列表结尾会预留一定的空间，LinkedList的空间浪费主要体现在每个节点中会额外保存前驱指针和后继指针。

二、源码分析

构造函数

先看一下一些ArrayList的成员变量：

/**
 * 默认初始容量大小
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * 空数组实例（空列表实例）
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * Shared empty array instance used for default sized empty instances. We
 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
 * first element is added.
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * will be expanded to DEFAULT_CAPACITY when the first element is added.
 */
transient Object[] elementData; 

/**
 * 列表的大小（列表中元素的个数）
 */
private int size;

再查看ArrayList的构造方法：

/**
 * 默认构造函数（使用初始容量10构造一个空列表）
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/**
 * 带初始容量的构造函数
*/
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        //创建initialCapacity大小的数组
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        //构造空数组
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                initialCapacity);
    }
}

/**
 * 创建包含指定collection中所有元素的列表，这些元素利用该集合的迭代器按顺序返回
 */
public ArrayList(Collection<? extends E> c) {
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        // replace with empty array.
        elementData = EMPTY_ELEMENTDATA;
    }
}

注意：以无参构造方法创建ArrayList时，实际上初始化赋值的是一个空数组，当真正像数组中添加元素时，才会分配容量。即向数组中添加第一个元素时，容量变为10。

扩容机制