概述 ArrayList 是实现 List 接口的动态数组，所谓动态就是它的大小是可变的。实现了所有可选列表操作，并允许包括 null 在内的所有元素。除了实现 List 接口外，此类还提供一些方法来操作内部用来存储列表的数组的大小。

注意，ArrayList 实现不是同步的。如果多个线程同时访问一个 ArrayList 实例，而其中至少一个线程从结构上修改了列表，那么它必须保持外部同步。所以为了保证同步，最好的办法是在创建时完成，以防止意外对列表进行不同步的访问： List list = Collections.synchronizedList(new ArrayList(…));

image.png

几个参数

  1.     //ArrayList的默认容量为10
  2.     private static final int DEFAULT_CAPACITY = 10;
  4.     private static final Object[] EMPTY_ELEMENTDATA = {};
  6.     private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  8.     //一个对象数组，用于存放数据
  9.     transient Object[] elementData; 
  11.     //用于表示当前数组内有多少条数据
  12.     private int size;
  14.     //数组的最大容量
  15.     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
  • DEFAULT_CAPACITY 每个ArrayList容器都有一个容量，这个参数就是默认的初始容量大小
  • elementData 这是一个对象数组，从此我们可以看到ArrayList的底层用一个对象数组来存储数据的
  • size 用来表示当前容器里已有多少条数据
  • modCount 继承自父类AbstractList，用于记录容器修改的次数（增，删）
  • MAX_ARRAY_SIZE 数组的最大容量是Integer.MAX_VALUE - 8，对于空出的8位，有以下三个解释：①需要8位来存储ArrayList自己的size，以避免机器内存的溢出②最大还是能支持到 Integer.MAX_VALUE（当Integer.MAX_VALUE-8依旧无法满足需求时）

构造器

ArrayList提供了三个构造器：

  • ArrayList()：默认构造函数，提供一个默认空列表。
  • ArrayList(int initialCapacity)：构造一个具有指定初始容量的空列表。
  • ArrayList(Collection<? extends E> c)：构造一个包含指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排列的。
  1.     /**
  2.      *默认构造器，使用定义的默认空的Object数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA
  3.      */
  4.     public ArrayList() {
  5.         this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  6.     }
  8.     /**
  9.      *构造一个具有指定初始容量的空列表
  10.      *@param initialCapacity 初始容量
  11.      */
  12.     public ArrayList(int initialCapacity) {
  13.         //如果指定的初始容量大于0（即合法）
  14.         if (initialCapacity > 0) {
  15.             //构造一个新的指定容量的Object数组
  16.             this.elementData = new Object[initialCapacity];
  17.         } else if (initialCapacity == 0) {
  18.             //如果指定的容量为0，则使用定义的空Object数组EMPTY_ELEMENTDATA
  19.             this.elementData = EMPTY_ELEMENTDATA;
  20.         } else {
  21.             //输入容量不合法，抛出异常
  22.             throw new IllegalArgumentException("Illegal Capacity: "+
  23.                                                initialCapacity);
  24.         }
  25.     }
  27.     /**
  28.      *构造一个包含指定Collection集合元素的列表
  29.      *@param c 指定的Collection集合类
  30.      */
  31.     public ArrayList(Collection<? extends E> c) {
  32.         //将集合转换为数组保存
  33.         elementData = c.toArray();
  34.         //保存该数组的长度（原集合的size），如果不是空集合，进行数组拷贝
  35.         if ((size = elementData.length) != 0) {
  36.             if (elementData.getClass() != Object[].class)
  37.                 elementData = Arrays.copyOf(elementData, size, Object[].class);
  38.         } else {
  39.             //如果是空集合，则使用空的Object数组EMPTY_ELEMENTDATA
  40.             this.elementData = EMPTY_ELEMENTDATA;
  41.         }
  42.     }

添加元素

ArrayList里有4个用于向容器里添加元素的方法

public boolean add(E e)； //向容器的末尾添加元素
public void add(int index, E element)； //向指定的位置插入元素，后面的元素向后移
public boolean addAll(Collection<? extends E> c); //向容器的末尾添加集合c里所有的元素
public boolean addAll(int index, Collection<? extends E> c); //从指定位置开始向容器里添加集合c里所有的元素
public void set(E e)；

  1. /**
  2.  *向容器的末尾添加元素
  3.  *@param e 待插入的元素
  4.  */
  5. public boolean add(E e) {
  6.     //用于扩容的方法
  7.     ensureCapacityInternal(size + 1); 
  8.     //向数组末尾插入元素，size+1
  9.     elementData[size++] = e;
  10.     return true;
  11. }

在这里ensureCapacityInternal(size + 1); 方法主要是用于判断是否需要扩容，传入数组所需的最小容量minCapacity，再进行插入元素操作。

  1. /**
  2.  *向容器内指定位置插入元素
  3.  *@param index 指定数组下标
  4.  *@param element 待插入的元素
  5.  */
  6. public void add(int index, E element) {
  7.     //进行数组下标的范围检查，是否越界
  8.     rangeCheckForAdd(index);
  9.     //同样的进行扩容检查
  10.     ensureCapacityInternal(size + 1);
  11.     //将指定下标后的元素均向后移一位
  12.     System.arraycopy(elementData, index, elementData, index + 1,
  13.                      size - index);
  14.     //向数组内指定位置插入元素
  15.     elementData[index] = element;
  16.     //size+1
  17.     size++;
  18.     }

在这里rangeCheckForAdd(index)； 方法用于检测输入的下标是否越界，越界则抛异常。同样也有扩容检查方法。

从System.arraycopy(elementData, index, elementData, index + 1, size - index); 方法我们可以看出，该方法是用于把一个数组中某一段字节数据放到另一个数组中。因此add方法向指定下标里添加元素并不是覆盖原元素，而是将后面元素向后移空着该位置用于插入元素。

  1. /**
  2.  *向容器的末尾添加集合c里所有的元素
  3.  *@param c 待插入元素的集合
  4.  */
  5. public boolean addAll(Collection<? extends E> c) {
  6.     //获取集合元素的数组
  7.     Object[] a = c.toArray();
  8.     int numNew = a.length;
  9.     //判断是否扩容
  10.     ensureCapacityInternal(size + numNew); 
  11.     //插入数组元素
  12.     System.arraycopy(a, 0, elementData, size, numNew);
  13.     size += numNew;
  14.     //只要集合不为空，则返回true
  15.     return numNew != 0;
  16. }
  18. /**
  19.  *向容器的指定位置添加集合c里所有的元素，同理
  20.  *@param index 待插入数组的位置
  21.  *@param c 待插入元素的集合
  22.  */
  23. public boolean addAll(int index, Collection<? extends E> c) {
  24.     rangeCheckForAdd(index);
  26.     Object[] a = c.toArray();
  27.     int numNew = a.length;
  28.     ensureCapacityInternal(size + numNew);  // Increments modCount
  30.     int numMoved = size - index;
  31.     if (numMoved > 0)
  32.         System.arraycopy(elementData, index, elementData, index + numNew,
  33.                          numMoved);
  35.     System.arraycopy(a, 0, elementData, index, numNew);
  36.     size += numNew;
  37.     return numNew != 0;
  38. }

扩容机制

从上面的添加元素方法里我们都会看到有扩容的方法，目的是为了让数组始终可以装得下所需要的元素。这里讨论一下ArrayList的扩容机制，主要有以下几个方法：

private void ensureCapacityInternal(int minCapacity)；
private void ensureExplicitCapacity(int minCapacity)；
private void grow(int minCapacity)；

  1. /**
  2.  *用于确认内部容量
  3.  *@param minCapacity 所需最小容量
  4.  */
  5. private void ensureCapacityInternal(int minCapacity) {
  6.     //如果容器是默认空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA，则取所需最小容量和默认容量两者最大值
  7.     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
  8.         minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
  9.     }
  11.     ensureExplicitCapacity(minCapacity);
  12. }
  14. /**
  15.  *判断是否需要扩容
  16.  *@param minCapacity 所需最小容量
  17.  */
  18. private void ensureExplicitCapacity(int minCapacity) {
  19.     modCount++;
  21.     // 如果所需最小容量 大于 当前数组长度，则表明需要扩容
  22.     if (minCapacity - elementData.length > 0)
  23.         //进行扩容
  24.         grow(minCapacity);
  25. }
  27. /**
  28.  *扩容方法
  29.  *@param minCapacity 所需最小容量
  30.  */
  31. private void grow(int minCapacity) {
  32.     //记录旧容量值，即现数组长度
  33.     int oldCapacity = elementData.length;
  34.     //计算新容量值，右移1位即乘2，newCapacity = oldCapacity * 1.5
  35.     int newCapacity = oldCapacity + (oldCapacity >> 1);
  36.     //判断，假如新容量比所需最小容量小，则直接将最小容量当作新容量
  37.     if (newCapacity - minCapacity < 0)
  38.         newCapacity = minCapacity;
  39.     //如果新容量比数组最大大小大，则调用hugeCapacity()方法计算新容量
  40.     if (newCapacity - MAX_ARRAY_SIZE > 0)
  41.         newCapacity = hugeCapacity(minCapacity);
  42.     //数组复制扩容
  43.     elementData = Arrays.copyOf(elementData, newCapacity);
  44. }
  46. /**
  47.  *计算新容量
  48.  *@param minCapacity 所需最小容量
  49.  */
  50. private static int hugeCapacity(int minCapacity) {
  51.     //判断数值是否合法，溢出抛错误
  52.     if (minCapacity < 0)
  53.         throw new OutOfMemoryError();
  54.     //若所需最小容量大于数组最大长度，返回Integer.MAX_VALUE，否则直接给数组最大长度
  55.     //MAX_VALUE = 0x7fffffff
  56.     //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
  57.     return (minCapacity > MAX_ARRAY_SIZE) ?
  58.         Integer.MAX_VALUE :
  59.         MAX_ARRAY_SIZE;
  60. }

删除元素

ArrayList里的删除元素主要有下面3个方法：

public E remove(int index)；
public boolean remove(Object o)；
public boolean removeAll(Collection<?> c)；

  1. /**
  2.  *删除指定下标的元素
  3.  *@param index 待删除元素的下标
  4.  */
  5. public E remove(int index) {
  6.     //下标范围检测
  7.     rangeCheck(index);
  9.     modCount++;
  10.     //获取要删除的元素
  11.     E oldValue = elementData(index);
  12.     //计算所需要移动的元素个数
  13.     int numMoved = size - index - 1;
  14.     //如果移除的不是最后一位元素
  15.     if (numMoved > 0)
  16.         //数组移动（复制）
  17.         System.arraycopy(elementData, index+1, elementData, index,
  18.                          numMoved);
  19.     //数组待删除元素置为null，size-1，交给GC自动垃圾回收
  20.     elementData[--size] = null; 
  21.     return oldValue;
  22. }
  24. /**
  25.  *移除此列表中首次出现的指定元素（如果存在）
  26.  *@param o 待删除元素
  27.  */
  28. public boolean remove(Object o) {
  29.     //元素判空，如果输入null，则删除数组里第一个为null的元素
  30.     if (o == null) {
  31.         for (int index = 0; index < size; index++)
  32.             if (elementData[index] == null) {
  33.                 fastRemove(index);
  34.                 return true;
  35.             }
  36.     } else {
  37.         //否则，删除第一个匹配的元素
  38.         for (int index = 0; index < size; index++)
  39.             if (o.equals(elementData[index])) {
  40.                 fastRemove(index);
  41.                 return true;
  42.             }
  43.     }
  44.     return false;
  45. }
  47. /**
  48.  *私有的快速删除方法
  49.  *@param index 待删除元素的下标
  50.  */
  51. private void fastRemove(int index) {
  52.     modCount++;
  53.     //计算删除后所需移动的元素个数
  54.     int numMoved = size - index - 1;
  55.     if (numMoved > 0)
  56.         //数组移动
  57.         System.arraycopy(elementData, index+1, elementData, index,
  58.                          numMoved);
  59.     //数组待删除元素置为null，size-1，交给GC自动垃圾回收
  60.     elementData[--size] = null; 
  61. }
  63. /**
  64.  *删除集合内所有匹配的元素
  65.  *@param c 待删除元素集合
  66.  */
  67. public boolean removeAll(Collection<?> c) {
  68.     //判断c集合是否为空
  69.     Objects.requireNonNull(c);
  70.     //调用batchRemove()方法
  71.     return batchRemove(c, false);
  72. }
  74. /**
  75.  *删除集合内所有匹配的元素
  76.  *@param c 待删除元素集合
  77.  *@param complement 为false时，删除集合内匹配元素，true时，保存匹配元素
  78.  */
  79. private boolean batchRemove(Collection<?> c, boolean complement) {
  80.     //获取当前元素数组
  81.     final Object[] elementData = this.elementData;
  82.     int r = 0, w = 0;
  83.     //标志域
  84.     boolean modified = false;
  85.     try {
  86.         //遍历数组内所有元素，判断集合内是否有相同元素
  87.         for (; r < size; r++)
  88.             //当complement为false时，表示把数组内不包含集合内元素的元素覆盖到原数组里，顺便前移
  89.             if (c.contains(elementData[r]) == complement)
  90.                 elementData[w++] = elementData[r];
  91.     } finally {
  92.         //当遍历完时，r一定会等于size，这一步判断主要是为了避免一些意外情况
  93.         //1.上面的for循环抛出了异常
  94.         //2.并发问题，其他的线程添加了元素
  95.         if (r != size) {
  96.             //进行数组调整，复原
  97.             System.arraycopy(elementData, r,
  98.                              elementData, w,
  99.                              size - r);
  100.             w += size - r;
  101.         }
  102.         //如果w ！= size，意思是上面的循环里存在重复元素被删除了
  103.         if (w != size) {
  104.             //因为以及将元素前移了（替换了），所以将数组后面的元素循环置null，交给GC垃圾回收
  105.             for (int i = w; i < size; i++)
  106.                 elementData[i] = null;
  107.             //记录集合修改次数
  108.             modCount += size - w;
  109.             size = w;
  110.             modified = true;
  111.         }
  112.     }
  113.     return modified;
  114. }
  116. /**
  117.  *删除指定下标范围内的元素
  118.  *@param fromIndex 起始下标
  119.  *@param toIndex 结束下标
  120.  */
  121. protected void removeRange(int fromIndex, int toIndex) {
  122.     modCount++;
  123.     int numMoved = size - toIndex;
  124.     System.arraycopy(elementData, toIndex, elementData, fromIndex,
  125.                      numMoved);
  127.         // clear to let GC do its work
  128.     int newSize = size - (toIndex-fromIndex);
  129.     for (int i = newSize; i < size; i++) {
  130.         elementData[i] = null;
  131.     }
  132.     size = newSize;
  133. }

优点

  • ArrayList底层是基于动态数组实现的，对于随机访问的get和set方法，ArrayList的性能很高
  • 对于直接向尾部添加元素的add()方法，ArrayList的性能也是非常高的

缺点

  • 对于向容器中间添加和删除元素操作，ArrayList的需要对数组元素进行移动，调用System.arraycopy()方法对数组进行复制，这会大大降低性能
  • ArrayList是非线程安全的
  • ArrayList会有预留的空余内存空间，会造成内存空间浪费