说一说ArrayList的实现原理

得分点

​ 数组实现、默认容量为10、每次扩容1.5倍

参考答案

标准回答

​ ArrayList是基于数组实现的，它的内部封装了一个Object[]数组。

​ 通过默认构造器创建容器时，该数组先被初始化为空数组，之后在首次添加数据时再将其初始化成长度为10的数组。我们也可以使用有参构造器来创建容器，并通过参数来显式指定数组的容量，届时该数组被初始化为指定容量的数组。

​ 如果向ArrayList中添加数据会造成超出数组长度限制，则会触发自动扩容，然后再添加数据。扩容就是数组拷贝，将旧数组中的数据拷贝到新数组里，而新数组的长度为原来长度的1.5倍。

​ ArrayList支持缩容，但不会自动缩容，即便是ArrayList中只剩下少量数据时也不会主动缩容。如果我们希望缩减ArrayList的容量，则需要自己调用它的trimToSize()方法，届时数组将按照元素的实际个数进行缩减。

加分回答

​ Set、List、Queue都是Collection的子接口，它们都继承了父接口的iterator()方法，从而具备了迭代的能力。但是，相比于另外两个接口，List还单独提供了listIterator()方法，增强了迭代能力。iterator()方法返回Iterator迭代器，listIterator()方法返回ListIterator迭代器，并且ListIterator是Iterator的子接口。ListIterator在Iterator的基础上，增加了向前遍历的支持，增加了在迭代过程中修改数据的支持。

延伸阅读

​ ArrayList的关键代码如下：

// 默认容量
private static final int DEFAULT_CAPACITY = 10;
// 空数组（指定容量）
private static final Object[] EMPTY_ELEMENTDATA = {};
// 空数组（默认容量）
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 元素数组
transient Object[] elementData;
// 元素个数
private int size;

// 创建默认容量的集合（在首次添加数据时分配容量）
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

// 创建指定容量的集合
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } 
    ...
}

// 追加数据
public boolean add(E e) {
    // 先扩容
    ensureCapacityInternal(size + 1);
    // 再追加
    elementData[size++] = e;
    return true;
}

// 扩容的底层逻辑
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // newCapacity有可能整数溢出
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // newCapacity有可能超出上限
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 拷贝数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}