实现的接口

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

ArrayList实现了三个接口，这三个接口都是标志性接口（接口中没有任何方法）。

RandomAccess：表示可以随机访问，Collections工具类中许多通用的算法，它们就会通过判断是否实现了该接口来选择不同的实现方式。

Cloneable:表示可克隆的，只有实现了该接口才可以调用Object类中的clone()方法，ArrayList对clone方法进行了重写，但是它仍然需要调用Object中的方法clone()。

Serializable:表示可序列化的，只有实现了该接口的类，它的对象才能被序列化(通过ObjectOutputStream将对象写入文件)

成员变量

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

	/**
	 *序列化编号
	 */
    private static final long serialVersionUID = 8683452581122892189L;

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

    /**
     * 大小为0的数组，当调用有参构造创建初始化容量为0的ArrayList时赋值给elementData
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 大小为0的数组，当调用无参构造创建ArrayList时赋值给elementData
	 * 该数组区别于EMPTY_ELEMENTDATA是为了在第一次添加元素时判断如何扩容
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 用于存放数据元素的数组，Object类型数组，可以接收任何类型的数据
	 * 该数组没有使用private修饰，是为了方便后面迭代器内部类访问
     */
    transient Object[] elementData; 

    /**
	 * 已存放元素的个数
     */
    private int size;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

从成员变量的信息我们主要可以得出：ArrayList是默认初始化容量为10的Object类型数组。

构造方法

ArrayList提供了三个构造方法，分别无参构造，指定初始化容量的构造方法，通过一个集合来构造ArrayList的构造方法。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    /**
     * 指定初始化容量的构造方法
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
			//当参数大于0的时候，直接创建初始化容量为initialCapacity的数组
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
			//将参数等于0的数组赋值给elementData
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
			//参数为负数时
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

    /**
     * 无参构造
     */
    public ArrayList() {
		//默认初始化容量为10，但是在添加元素之前容量一直为0
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
	 * 通过一个集合来构造ArrayList，元素的存放顺序为传入集合迭代器返回的顺序
     */
    public ArrayList(Collection<? extends E> c) {
		//将集合转换为Object数组
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            //JDK老版本的bug，意思就是c.toArray()返回的类型可能不是Object类型，现在已经被修复
            //(see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 传入的集合为空集合
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

从这三个构造方法我们可以知道：调用无参构造创建出来的ArrayList在第一次添加元素之前容量一直为0；我们也知道了EMPTY_ELEMENTDATA、DEFAULTCAPACITY_EMPTY_ELEMENTDATA这两个大小为0的数组什么时候用来赋值。

涉及数组容量的方法

copyOf和arrayCopy

ArrayList在扩容时会调用的copyOf方法，copyOf方法又是使用arrayCopy方法实现的。

我们这里先说arrayCopy方法，arrayCopy底层是使用C语言实现的，实现的功能是将一个数组中的内容拷贝至另外一个数组(浅拷贝)。

copyOf实现功能：通过截断或者填充将原数组转换为指定长度的新数组。

下面我们看一下copyOf的源码，如下：

public static <T> T[] copyOf(T[] original, int newLength) {
        return (T[]) copyOf(original, newLength, original.getClass());
}

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        //判断newType是否是Object类型
        T[] copy = ((Object)newType == (Object)Object[].class)
        	//是Object类型，直接创建长度为newLength的Obejct类型数组
            ? (T[]) new Object[newLength]
            //创建非Object类型数组
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
		//将原数组内容拷贝至新创建的数组，拷贝长度为原先数组长度和新长度中较小的一个
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        //将新数组返回
        return copy;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

数组扩容的方法

public void ensureCapacity(int minCapacity) {
		//排除通过无参构造创建的ArrayList，该ArrayList还未添加元素(为扩容),并且minCapacity小于10这种特殊情况
        if (minCapacity > elementData.length
            && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
                 && minCapacity <= DEFAULT_CAPACITY)) {
            modCount++;
            grow(minCapacity);
        }
    }

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    private Object[] grow(int minCapacity) {
        return elementData = Arrays.copyOf(elementData,
                                           newCapacity(minCapacity));
    }

    private Object[] grow() {
        return grow(size + 1);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

获取扩容后的新容量

 private int newCapacity(int minCapacity) {
        int oldCapacity = elementData.length;
		//新容量为旧容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
		//新容量大于需要的最小容量
        if (newCapacity - minCapacity <= 0) {
			//使用无参构造创建的数组，此时还未添加元素，数组容量为0
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
			//minCapacity太大，超出了整型范围
            if (minCapacity < 0)
                throw new OutOfMemoryError();
            return minCapacity;
        }
		//返回新容量
		//所需最小容量超出了数组的最大容量，返回Integer.MAX_VALUE
		//所需容量小于数组最大容量，返回新容量
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity 
            : hugeCapacity(minCapacity);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE)
            ? Integer.MAX_VALUE
            : MAX_ARRAY_SIZE;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

可能光看上面方法对扩容机制感到十分混乱，下面进行梳理以下：

从扩容的原因分析，有以下两种情况：

1. 调用add方法，数组容量不足，需要扩容。
   1）使用无参构造创建的ArrayList，并且是第一次添加元素，扩容后的新容量为10.
   2) 在添加元素时容量不足，扩容后的新容量为原先容量的1.5倍(除过初始容量为1的ArrayList第一次扩容，它第一次扩容后的容量为2)。
   3)原先容量的1.5倍大于MAX_ARRAY_SIZE，并且小于Integer.MAX_VALUE，扩容后容量为Integer.MAX_VALUE
2. 调用ensureCapacity方法，来保证数组所需的最小容量。
   1)minCapacity小于原先容量的1.5倍，扩容后的新容量为原先容量的1.5倍。
   2)minCapacity大于原先容量的1.5倍，扩容后的新容量为minCapacity。

ArrayList中的Iterator

public Iterator<E> iterator() {
        return new Itr();
    }

    private class Itr implements Iterator<E> {
		// 下一个要返回元素的下标，默认为0
        int cursor;      
		// 最后一次返回元素的下标
        int lastRet = -1;
		//ArrayList预期的修改次数，在获取迭代器之后若再通过非迭代器方法对ArrayList进行增删改操作，
		//修改次数的预期值与实际值就会不同，迭代器不能在继续使用
        int expectedModCount = modCount;

        Itr() {}

		//判断是否还有可获取的元素
        public boolean hasNext() {
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        public E next() {
			//检查expectedModCount是否与modcount相同，若不同抛出ConcurrentModificationException
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
				//将cursor往前挪了一位
                cursor = lastRet;
				//lastRet被重置为-1，这也解释了remove为什么不能连续使用两次
                lastRet = -1;
				//修改预期修改次数为当前的实际修改次数
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

		//对未遍历的全部元素进行指定操作
        @Override
        public void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i < size) {
                final Object[] es = elementData;
                if (i >= es.length)
                    throw new ConcurrentModificationException();
                for (; i < size && modCount == expectedModCount; i++)
                    action.accept(elementAt(es, i));
                //将cursor一次更新到最后一次操作的下一个位置，lastRet移动到最后一次操作的位置
                cursor = i;
                lastRet = i - 1;
                checkForComodification();
            }
        }
		//检查expectedModCount是否与modcount相同，若不同抛出ConcurrentModificationException
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

通过ArrayList中获取迭代器源码源码的学习，我们可以知道：

1. ArrayList的迭代器维护了一个用来遍历集合的下标，next()方法就是通过该下标来获取元素的，每使用一次next，该下标就会往后移一位。
2. ArrayList和它的迭代器都维护了一个集合的修改次数，迭代器的next(),remove()方法在执行之前都会检查两个修改次数书是一致，若不一致就会抛出异常。
3. ArrayList的迭代器维护了一个上一次返回元素的下标，初始值为-1，在使用next方法后，该下标会被更新，remove方法就是以该下标为参数调用ArrayList的remove方法。
4. 在使用一次迭代器的remove方法后，迭代器维护的上一次返回元素的下标会重新置为-1.这就解释了为什么remove()方法不能连续使用。
5. 迭代器的remove方法也是通过调用集合的remove方法来删除上一次遍历的元素，所以集合维护的修改次数在调用remove方法之后也会发生改变，为保证不影响迭代器的继续使用，迭代器的remove方法是会更新迭代器维护的集合修改次数的。