在学习ArraList源码之前，我们应该了解 Java 中整个集合框架的继承关系。 

一、ArrayList概述

 从集合类图可以看出，ArrayList实现List接口。ArrayList是顺序的集合容器，容器中可以存放null元素，而底层则是通过一个可自动增长大小的动态数组实现的。ArrayList不是 线程安全 的，也没有实现同步。 

 每一个ArrayList的实例都有一个容量，用来表示存储数据的数组大小。容器内的元素不能大于当前当前的容器大小。当向容器中添加数据时，若容器的容量不足，容器会自动扩容。而值得关注的是，底层数组是一个Object类型的数组，为了就是能使其容纳任何数据类型的对象。 

 ArrayList底层数组 

Object[] elementData 

1.1数组

数组是n（n>1）个相同数据类型的数据元素a0,a1,a2,.————-,an-1构成的占用一块地址连续的内存空间的有限序列。

n个数据元素的数组

1.2数组操作

访问数组中第 n 个数据的时间花费是 O(1) 但是要在数组中查找一个指定的数据则是 O(N) 。当向数组中插入或者删除数据的时候，最好的情况是在数组的末尾进行操作， 时间复杂度 是 O(1) ，但是最坏情况是插入或者删除第一个数据，时间复杂度是 O(N) 。在数组的任意位置插入或者删除数据的时候，后面的数据全部需要移动，移动的数据还是和数据个数有关所以总体的时间复杂度仍然是 O(N) 。

二、ArrayList实现

2.1私有属性

ArrayList有两个私有属性，一个是实现数据存储的数组，一个是表示数组中元素的个数。值得注意的是关键字transit。

此外还有个保护的属性：modCount

含义；已从结构上修改 此列表的次数。从结构上修改是指更改列表的大小，或者打乱列表，从而使正在进行的迭代产生错误的结果。

transit:首先ArrayList这个类实现了Serializable接口。Java的Serializable提供了一种 持久化 对象实例的机制，当持久化对象时，可能某个特殊的对象数据成员我们不想让其用Serializable机制保存它，这时就用到了Java中的关键字transit来表示。

下面是一个实例：

实体类User：

对属性sanwei添加transit关键字，测试方法：

开始向文件中写数据，然后反 序列化 ，从文件中读取数据。文件中的序列化数据为：

然后，反序列化可以看出属性"sanwei"并没有被序列化 

2.2构造方法

ArrayList中有三个 构造函数 ，一个是默认构造一个容量为10的数组为空的ArrayList，一个指定容量的空列表和一个Collection类型的空列表。

1）构造默认容量大小的构造函数 

2）构造指定大小容量

3）创建一个包含Collection的ArrayList

2.3元素存储的方法

ArrayList类提供了add(E e)，add(int index, E element)，addAll(Collection<? extends E> c)以及set(int index, E element) 方法。

1）set

2）add

指定元素添加到此列表的末尾 

将指定元素添加到列表的特定位置

//如果插入的位置有元素，则向右移动当前元素以及后面的所有元素 

//将elementData从index位置开始，长度为size-index的元素拷贝到 

下标从index+1开始的elementData数组中去。 

按照Collection中的元素顺序将Collection中所有元素添加到列表中 

从指定位置开始，将Collection中所有元素添加到列表中 

小结：从上面的存储元素的方法中都可以观察到，每个add方法都用了ensureCapacity(int minCapacity)方法，方法实现如下： 

扩容过程为：

oldElementData

此外，通过对比jdk1.7的ArrayList源码发现，扩容两个方法是不一样的，jdk1.6中使用的是除法对其容量进行计算，而jdk1.7中则使用的是移位运算。

我们知道，位运算时CPU直接操作的，除法等四则运算都是基于移位运算的，所以当有大量计算的时候，移位运算可以大大节约CPU的时间。

下面是一个小demo：

运行结果如下：

通过运行结果可以看出，在计算大量数据的情况下，移位运算的花费时间比乘除法快很多。

除此之外，还观察到，该ensureCapacity(int minCapacity)中调用的是Arrays的<T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType)方法，而在add方法中，调用的数组复制方法为： 

Arrays的copyOf方法的实现： 

可以观察到，该方法在方法体内部又创建了一个程度为newLength的数组，然后再调用了System.arraycopy方法，该方法有标记native，表明是调用了C/C++代码。 

再看ensureCapacity(int minCapacity)此方法，我注意到，该方法体中有一段代码为：Object oldData[] = elementData;oldData[]数组没有被用到，当时很疑惑，想是否为多余的代码，后来查资料才知道是考虑到了内存的安全性。我们看到这句话是在if的内部，跟elementData = Arrays.copyOf(elementData, newCapacity);这段代码有关系。上面有提及到在实现copyOf的时候会新创建一个大小为newCapcity的数组，然后将旧的elementData放入其中。但是还是没有用到oldData,问题就在于旧内存的引用为旧的elementData，而elementData又指向了新的内存，如果此时用一个局部变量去引用旧的内存块，在复制的过程中就可以避免在还没有复制完的时候有其他 线程分配内存或新的内存去侵占这块旧的内存，既是新的内存被释放的情况。 

2.4元素读取

get（）方法： 

如下实例：

当然，若使用了泛型就不必类型转换了。

2.5元素删除

ArrayList提供了两种删除元素的方法，一个是remove（int index）删除指定位置的元素，一个是remove（Object o）删除满足o.equals(elementData[index]的元素。 

1）remove（int index） 

发现删除操作是add操作的一个逆过程，要将删除点之后的元素向前移动一个位置。 

2）remove(Object o) 

该方法调用了ArrayList的一个私有方法fastRemove（int index） 

该方法与remove（int index）的区别是少了一次小标越界的判断，因为该方法是在一个for循环中调用的，保证了不会越界。同时也不会返回被删除的元素。 

2.6数组转换

ArrayList提供了两个转为数组的方法，一个是调用Arrays的copyOf方法，转换后的数组元素就是size个elementData的元素，方法如下： 

 另外 一个是 传入一个任意类型的数组，当传入的数组的长度小于elementData长度时，返回一个新的数组。若传入数组长度大小和elementData长度大小相等，则将elementData复制到传入数组中并返回传入的数组。若大于，则在复制后还会降返回新数组的第size个元素置为空。 

2.7针对io的方法

1）writeObject 

writeObject方法其实就是写的过程，我们注意到在写的过程中对modCont这个变量进行了判断，其实是很有必要的。因为我们知道ArrayList不是线程安全的，如果在写的过程中有其他线程对ArrayList进行了修改，那么就会抛出ConcurrentModificationException异常，这就是我们所说的fail-fast策略。 

2）readObject 

而读方法是从已有的流中读取数据，就不会存在上述判断和异常了。 

三、总结

1、在看源码是注意三个不同的构造函数，一个是无参数的默认狗找哦函数一个是带有Collection参数的构造函数，一个是指定大小的构造函数。 

2、ArrayList大量调用了Arrays.copyOf和System.arrayCopy的方法，注意这两个方法的区别。 

3、jdk1.6和1.7中数组扩容的方法不一致，注意比较有差异 的地方。