前言

  在我的日常开发中，ArrayList这个类几乎是我天天都会用到的一个类，简单又好用，不知大家是不是也经常用它？虽然经常都用到它，但是我却从来都没有看过ArrayList的源码实现，突然意识到如果一直只停留在“会用就好”的这种阶段，会导致自己在技术深度上陷入瓶颈，于是才有了这篇文章。
  我会在看ArrayList源码的同时，把那些需要记录下来的点，写到这篇文章当中，以防自己忘记，也可以给大家做下参考。该文章包含较多源码，请耐心食用哦！ps:在文章的左边会有目录可以点击跳转到想看的API

文章目录

• 前言
• 一、ArrayList的简单使用
• 二、常用API源码分析
• • 全局变量
  • 构造方法
  • add
  • addAll
  • set
  • get
  • indexOf
  • lastIndexOf
  • contains
  • remove
  • removeAll
  • retainAll
  • clear
  • sort
  • toArray
• 总结

一、ArrayList的简单使用

  虽然大部分同学都对ArrayList的使用了如指掌，但这里还是简单介绍一下使用步骤，照顾一下小白们。

//使用之前先new一个ArrayList  //大部分时候都是用的无参构造方法 因为我们不知道会存多少数据//如果要存int、double的话 记得使用它们的包装类 至于为什么下面会讲List<Integer> list = new ArrayList<>();//添加数据不传index默认添加到末尾list.add(1);list.add(2);list.add(3);list.add(1);list.add(0, 4);//当传入index  这个数据就会插到指定位置//遍历数据 : 4, 1, 2, 3, 1for (int i = 0; i < list.size(); i++) Log.d(TAG, i + " : " + list.get(i));//查找数据 找到返index 没有返-1list.indexOf(new Integer(0));//return -1list.indexOf(new Integer(1));//return 1list.lastIndexOf(new Integer(1));//return 4//删除数据list.remove(0);//删除第一个元素list.remove(new Integer(2));//如果传入的是一个Object的话 将会删除数组内与它相同的元素//清除数据list.clear();

  这是对ArrayList的简单使用，如果有不懂的地方，请接着往下面的api源码看。

二、常用API源码分析

全局变量

 //版本号 private static final long serialVersionUID = 8683452581122892189L;    //默认的初始化尺寸    private static final int DEFAULT_CAPACITY = 10;    //默认的空数组    private static final Object[] EMPTY_ELEMENTDATA = {};    //也是一个空数组 当调用无参构造函数时 就会将这个数组赋值给实例的elementData     private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};    //实际存储数据的数组 上面说的int、double要用他们的包装类初始化 就是因为这里用的Object数组实现    transient Object[] elementData;    //数组实际长度    private int size;    //默认的数组最大长度 若超过这个值有可能导致OOM    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

  这里顺带一提transient关键字，因为ArrayList实现了Serializable接口，它的作用就是在序列化的时候，被该关键字修饰的属性不会进行序列化，但是跟这篇文章没多大关系。

构造方法

1、无参构造函数

//一眼看完 将上面的静态空数组赋值给elementData public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;    }

2、传入初始化大小initialCapacity

public ArrayList(int initialCapacity) { if (initialCapacity > 0) {//大于0则初始化数组     this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) {//为0则用上面的全局变量直接赋值     this.elementData = EMPTY_ELEMENTDATA; } else {//小于0则抛出异常     throw new IllegalArgumentException("Illegal Capacity: "+     initialCapacity); }    }

3、传入一个Collection对象

public ArrayList(Collection<? extends E> c) {//调用Collection对象的toArray方法 这里就不跟了 elementData = c.toArray(); if ((size = elementData.length) != 0) {     //如果转出来的数组类型不是Object的 则进行转换     if (elementData.getClass() != Object[].class)  elementData = Arrays.copyOf(elementData, size, Object[].class); } else {     //当Collection对象长度为0时 将elementData覆盖为EMPTY_ELEMENTDATA     this.elementData = EMPTY_ELEMENTDATA; }    }

add

1、传入一个泛型e

public boolean add(E e) { ensureCapacityInternal(size + 1);  // Increments modCount!! elementData[size++] = e; return true;    }

  在源码中可以看到，一个参数的add方法只是把数据放入数组，而size可以理解成数组的index，在赋值的同时将index指向下一个。而最重要的应该就是ensureCapacityInternal方法了，该方法保证数组有足够的容量添加数据，即ArrayList的扩容策略，具体内容请看代码，传入size+1。↓↓↓

private void ensureCapacityInternal(int minCapacity) {//如果使用无参的构造方法初始化，则这里条件成立 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //即minCapacity的最小值起码是DEFAULT_CAPACITY，也就是10     minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } //将minCapacity传入ensureExplicitCapacity ensureExplicitCapacity(minCapacity);//↓↓↓    }private void ensureExplicitCapacity(int minCapacity) {//modCount为父类的变量 可简单理解成数组的修改次数 modCount++; //当minCapacity大于elementData数组的当前长度 则进行扩容 if (minCapacity - elementData.length > 0)     grow(minCapacity);//↓↓↓    }private void grow(int minCapacity) { //newCapacity先赋值为1.5倍oldCapacity， int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); //若newCapacity小于minCapacity，则将minCapacity设置为newCapacity if (newCapacity - minCapacity < 0)     newCapacity = minCapacity; //新的数组长度超过MAX_ARRAY_SIZE，则进入hugeCapacity if (newCapacity - MAX_ARRAY_SIZE > 0)     newCapacity = hugeCapacity(minCapacity); //然后将elementData的数据拷贝到新长度的数组中 elementData = Arrays.copyOf(elementData, newCapacity);    }    private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) //事实上不可能小于0     throw new OutOfMemoryError(); //这里可以看出最大值为Integer.MAX_VALUE，超过这个值应该就会有问题 return (minCapacity > MAX_ARRAY_SIZE) ?     Integer.MAX_VALUE :     MAX_ARRAY_SIZE;    }

2、传入数据索引和数据

public void add(int index, E element) { if (index > size || index < 0)     throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); ensureCapacityInternal(size + 1); //把index及它后面的数据全部后移一位，空出index这个位置 System.arraycopy(elementData, index, elementData, index + 1,    size - index); //填充index索引的数据 elementData[index] = element; size++;    }

  我们在上面的源码中可以看到两个参数的add方法实现与上面的比较相似，不同点是由于传入了index，对index做了一个校验之后再进入ensureCapacityInternal，然后再对index后的数据进行后移，再填入数据。

addAll

1、传入一个collection对象

    public boolean addAll(Collection<? extends E> c) {    //没有对c进行校验 可能出现空指针 Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); //把数据拷贝到elementData数组后面 System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0;    }

2、传入起始index与collection对象

    public boolean addAll(int index, Collection<? extends E> c) { if (index > size || index < 0)     throw new IndexOutOfBoundsException(outOfBoundsMsg(index));    //没有对c进行校验 可能出现空指针 Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); //如果index小于size则需要先移动index后面的数据，将空间腾出来给插入的数据 int numMoved = size - index; if (numMoved > 0)     System.arraycopy(elementData, index, elementData, index + numNew, numMoved); //把数据拷贝到elementData数组的指定位置 System.arraycopy(a, 0, elementData, index, numNew); size += numNew; return numNew != 0;    }

  addAll方法跟add方法并没有什么本质区别，只是当传入的collection对象为null时会导致空指针异常，其他的我也在代码里面注释了，感兴趣的话可以看看，也可以直接往下走。

set

    public E set(int index, E element) { if (index >= size)     throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); E oldValue = (E) elementData[index]; elementData[index] = element; return oldValue;    }

  set方法对传入的index有一个校验，若在此之前未add该元素，则会抛出异常，下面就是简单的数据交换，返回该位置原始的数据。

get

    public E get(int index) { if (index >= size)     throw new IndexOutOfBoundsException(outOfBoundsMsg(index));  return (E) elementData[index];    }

  get方法简单校验传入的index是否有效之后便直接返回数组元素。

indexOf

    public int indexOf(Object o) { if (o == null) {     for (int i = 0; i < size; i++)  if (elementData[i]==null)      return i; } else {     for (int i = 0; i < size; i++)  if (o.equals(elementData[i]))      return i; } /* for (int i = 0; i < size; i++)  if (elementData[i].equals(o))      return i; */ return -1;    }

  indexOf也是非常常用的一个API，在实现上也非常的简单易懂，第一眼看到这个实现的时候，我是觉得代码有点冗余的，为什么不用我注释里面的那种写法去实现呢？仔细一想，不仅o可能为null，而且ArrayLIst存储的数据也允许为null，如果按注释的写法可能出现空指针，所以这个源码这样写也有它的道理，如果不细心一点，在日常的开发中就可能会掉进这种坑里。。。

lastIndexOf

    public int lastIndexOf(Object o) { if (o == null) {     for (int i = size-1; i >= 0; i--)  if (elementData[i]==null)      return i; } else {     for (int i = size-1; i >= 0; i--)  if (o.equals(elementData[i]))      return i; } return -1;    }

  lastIndexOf的实现与上面的indexOf基本一致，只是改变了遍历顺序，这里不再多说。

contains

public boolean contains(Object o) { return indexOf(o) >= 0;    }

  在没看源码之前，我总以为contains方法用不知道多厉害多高大上的方式去判断List里面是否存在该元素，没想到contains的源码只有一行，就是对indexOf方法的一个封装，所以看源码还是非常必要的，它能够解除我们心中的疑惑。

remove

1、传入元素index

    public E remove(int index) {    //这里对index的校验为什么不加上 < 0呢? if (index >= size)     throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); modCount++; E oldValue = (E) elementData[index]; //如果index不等于size - 1，也就是不为最后一个元素时 int numMoved = size - index - 1; //将index后面的所有数据前移一位，覆盖前面的数据 if (numMoved > 0)     System.arraycopy(elementData, index+1, elementData, index, numMoved); //将末尾的元素置空，并将size-- elementData[--size] = null; // clear to let GC do its work //返回被删除的元素 return oldValue;    }

2、传入实际要删除的对象

    public boolean remove(Object o) { if (o == null) {     for (int index = 0; index < size; index++)  if (elementData[index] == null) {      fastRemove(index);//↓↓↓      return true;  } } else {     for (int index = 0; index < size; index++)  if (o.equals(elementData[index])) {      fastRemove(index);//↓↓↓      return true;  } } return false;    }private void fastRemove(int index) { modCount++; int numMoved = size - index - 1; if (numMoved > 0)     System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null;    }

  在上面的源码中，我们可以看到remove方法传入index时会返回被删除的元素，传入实际元素则会返回删除是否成功。而两个方法实际的删除操作是一样的，1方法是在方法内先移动index后面的元素，然后删除末尾元素，而2方法先遍历数组，找到index后调用fastRemove方法进行删除元素，实现方式就是1方法掐头去尾，核心逻辑一模一样。

removeAll

    public boolean removeAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, false);//↓↓↓    }private boolean batchRemove(Collection<?> c, boolean complement) {//初始化数据 final Object[] elementData = this.elementData; int r = 0, w = 0; boolean modified = false; try { //这里用了双指针去遍历数组，指针r遍历整个数组，指针w指向存储位置     for (; r < size; r++)     //因为complement为false，所以当c不包含当前r指向的元素时条件成立  if (c.contains(elementData[r]) == complement)  //将该元素放到w指向的位置，同时w指向下一位置      elementData[w++] = elementData[r]; } finally { //理论上到这里r等于size，不等则代表上面有异常     if (r != size) {     //将后面还没遍历到的元素拷贝到w指针后面  System.arraycopy(elementData, r,     elementData, w,     size - r); //将w指针指向数据末端  w += size - r;     }     //w不等于size则代表有元素需要被移除     //(上面的操作只是把需要保留的元素移到数组前面，而没有删除无用的元素)     if (w != size) {     //遍历将w指针后面的元素置空，并更新相关变量  for (int i = w; i < size; i++)      elementData[i] = null;  modCount += size - w;  size = w;  modified = true;     } } //该返回值代表数组是否被更新 return modified;    }

  在代码中我们可以看到，removeAll方法的功能实际上是由batchRemove方法实现的。batchRemove方法使用双指针的方式处理数据，r指针遍历数组，将符合条件的元素放置到w指针的位置上，并将w指针指向下一位置，若循环中出现异常，则会将未遍历到的元素直接附加在w指针后面的位置，最后：如果w指针不是指向数组的末尾(也就是w != szie)，代表数组中有元素被删除，则需要将w指针后面的元素置空，再更新对象的相关变量，方法结束。

retainAll

    public boolean retainAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, true);    }

retainAll方法的实现也是依赖上面的batchRemove方法，retainAll与removeAll方法唯一的区别就是传入batchRemove的第二个参数相反，也就是retainAll保存的数据跟removeAll的完全相反。

clear

    public void clear() { modCount++; for (int i = 0; i < size; i++)     elementData[i] = null; size = 0;    }

  clear方法的实现方式与我们常用的元素清除方式一致，直接遍历清除，然后将size置为0。

sort

    public void sort(Comparator<? super E> c) {    //将modCount备份 final int expectedModCount = modCount; //排序 Arrays.sort((E[]) elementData, 0, size, c); //如果modCount跟expectedModCount不相等，则代表对该对象进行了并发操作 if (modCount != expectedModCount) { //并发操作的结果是不可预料的，抛出ConcurrentModificationException     throw new ConcurrentModificationException(); } modCount++;    }

  sort方法就是根据传参的排序方式进行排序，其中我们需要注意的是modCount这个参数，在排序之前modCount赋值给了expectedModCount，在排序之后将expectedModCount与modCount进行比较，如果二者不相等则代表modCount在别的地方进行了操作，会抛出一个ConcurrentModificationException，如果二者相等，则将modCount++，方法结束。

toArray

1、无参调用：直接拷贝一份返回

public Object[] toArray() { return Arrays.copyOf(elementData, size);    }

2、传入泛型数组

    public <T> T[] toArray(T[] a) { //如果入参数组的长度不足以放下ArrayList所有元素，则拷贝出一个新的数组返回 if (a.length < size)     return (T[]) Arrays.copyOf(elementData, size, a.getClass()); //当入参数组可以放下所有元素时，将ArrayList的元素全部拷贝至该数组 System.arraycopy(elementData, 0, a, 0, size); //如果入参数组的长度比ArrayList的长度更长，则置空a数组中ArrayList元素的后一位 if (a.length > size)     a[size] = null; return a;    }

  这个toArray方法根据数组长度和ArrayList长度的小于、等于、大于三种情况来处理，其实小于和等于的情况都很好理解，但是也许会有人不理解，为什么在大于的情况下，置空ArrayList元素后一位，源码的注释是这样写的：当开发者在知道ArrayList不包含空数据的情况下，这个置空的元素对开发者确定list的终点很有用。。。如果我没翻译错的话，应该就是这样的。

总结

  一下子ArrayList常用API的源码就看完了啊，除了这些源码，还有一些内部类的源码，内容比较多就不塞进来了，主要是跟迭代器相关的，感兴趣的同学可以自己去研究一下，如果上面我有什么写得不对，记得在下面告诉我一下，我一定尽快改正。码字不易，如果觉得不错的话，也可以来个一键三连支持一下哈，谢谢大家！