不遗余力地接近，费尽心思地琢磨，偶尔以特立独行标榜，归于安静，归于遗忘，归于平和，也终成生命中荡起的涟漪。 —— 宜追寻

ArrayList 概述

介绍

1. ArrayList底层基于数组队列实现，可以动态增长，相当于动态数组，可以存放null元素。
2. ArrayList继承AbstractList类，实现了List，Cloneable，RandomAccess接口，是顺序容器，放入到容器中的顺序和实际存储的顺序相同。
3. RandomAccess是一个标志接口，表明支持随机访问，在ArrayList中可以通过序号快速获取元素对象。

基本操作

操作	含义
add(E e)	向容器中添加元素
add(int index, E element)	向容器中对应位置添加元素
addAll(Collection<? extends E> c)	向容器中添加多个元素
addAll(int index, Collection<? extends E> c)	向容器中对应位置添加多个元素
set(int index, E element)	对指定位置进行赋值
get(int index)	获取指定位置的元素
remove(int index)	删除指定位置的元素，并将之后的元素都向前移动一个位置，最后位置引用设置为null
remove(Object o)	删除满足第一个和o相等的元素，其余操作同上
indexOf(Object o)	获取元素o第一次出现的位置
lastIndexOf(Object o)	获取元素o最后一次出现的位置
size()	ArrayList存储元素的数量

ArrayList中所有方法

ArrayList主要机制和特点

扩容机制（以JDK17为例）

介绍

Java中标准数组的长度是固定的，创建之后便无法改变，但很多实际情况中需要动态增长的数组。ArrayList底层是以Object[]（elementDate[]）为基础，配合自动扩容机制使ArrayList成为最常用的容器之一。

扩容步骤及源码

1. ArrayList构造方法： 以无参构造方法创建ArrayList时，会初始化一个空数组，当第一次添加元素时，会将数组容量初始化为10，见下面add()方法。JDK6 new 无参构造的 ArrayList 对象时，直接创建了长度是 10 的 Object[] 数组 elementData 。

public ArrayList(int initialCapacity) {
    //如果指定容量，则数组大小即为指定的容量大小
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}


public ArrayList() {
    //初始化空数组
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}


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

1. 扩容发生在调用add()方法时

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // 扩容方法
    elementData[size++] = e;
    return true;
}

1. add()方法调用ensureCapacityInternal()方法进行扩容,minCapacity：最小扩容量

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

calculateCapacity()：如果传入的是空数组，则取默认数组容量（默认为10）和minCapacity之间最大值

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

ensureExplicitCapacity():判断是否需要扩容

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    //如果最小扩容量比elementData[]空间要大，则需要扩容
    if (minCapacity - elementData.length > 0)
        //扩容实际方法
        grow(minCapacity); 
}

1. grow():扩容的实际方法

private void grow(int minCapacity) {
    //原数组的长度
    int oldCapacity = elementData.length;
    //新数组的长度，扩容到1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //判断新数组容量是否满足，足够则使用，否则使用minCapacity
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
     //判断预设长度是否会造成溢出
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 将elementDate数组从旧数组复制到新数组中
    elementData = Arrays.copyOf(elementData, newCapacity);
}

对比和其他

ArrayList和Array（数组）的区别

维度	ArrayList	Array
底层实现	基于动态数组	基于静态数组
存储类型	对象	基本数据类型和对象
创建后是否可以改变大小	可以动态扩容	否
操作	丰富的API	数组的基本操作

ArrayList和Vector的区别

ArrayList：List接口主要实现类，线程不安全 Vecotr：List接口的古老实现类，使用synchronized修饰，线程安全

ArrayList和LinkedList的对比

• 底层数据结构：Arraylist使用Object数组，LinkedList使用双向链表（JDK1.7取消了循环）。
• 内存空间占用：LinkedList中每个元素所占用的空间都要存储直接前驱地址，直接后继地址和数据，所以同样的数据要比ArrayList使用更多的空间。
• 访问速度：ArrayList实现了RandomAccess接口，支持快速随机访问。
• 插入和删除操作：ArrayList末尾插入和删除时间复杂度都是O(1)，指定位置插入是O(n);LinkedList头部插入，头部删除，末尾插入，末尾删除时间复杂度都是O(1),其他都是O(n)。
• 线程安全：都是线程不安全。

Fail-Fast机制:

fail-fast机制是Java集合中的一种错误机制。ArrayList中主要通过记录modCount参数来实现。在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的结构进行了修改（增加、删除），则会抛出Concurrent Modification Exception（并发修改异常）。

参考

一文彻底弄懂fail-fast、fail-safe机制（带你撸源码） - 知乎 (zhihu.com) ArrayList 源码分析 | JavaGuide(Java面试 + 学习指南) Collection - ArrayList 源码解析 | Java 全栈知识体系 (pdai.tech)