ArrayList源码分析

1、概述

　　ArrayList是我们最常用的集合类，它支持随机访问，查询速度非常快，插入，删除则耗时较多，ArrayList支持存储重复性的数据，空数据；ArrayList是变长集合，它基于定长数组实现，在集合中数据达到数组的最大限，他会重新创建一个更大容量的数组，把原先数组中的数据复制到新的数组，arrayList有这些特性都是源于它的底层实现，下面我们就一起看看arrayList的常用功能的底层实现。

2、源码分析

　　2.1 构造方法

　　ArrayList有三个构造方法，一个是无参构造方法(一般都选用此构造方法创建对象)，还有一个可以指定初始容器大小的构造方法,第三个是用某个集合初始化容器的构造方法，相关代码如下：

ArrayList 构造方法
 1         private static final int DEFAULT_CAPACITY = 10;
 2         private static final Object[] EMPTY_ELEMENTDATA = {};
 3         private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
 4         transient Object[] elementData; // non-private to simplify nested class access
 5         private int size;
 6         /**
 7          * 参数为容量大小
 8          * @param initialCapacity
 9          */
10         public ArrayList(int initialCapacity) {
11             if (initialCapacity > 0) {
12                 this.elementData = new Object[initialCapacity];
13             } else if (initialCapacity == 0) {
14                 this.elementData = EMPTY_ELEMENTDATA;
15             } else {
16                 throw new IllegalArgumentException("Illegal Capacity: "+
17                                                    initialCapacity);
18             }
19         }
20         /**
21          * 无参构造函数
22          */
23         public ArrayList() {
24             this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
25         }
26         /**
27          * 参数是某个集合类
28          * @param c
29          */
30         public ArrayList(Collection<? extends E> c) {
31             elementData = c.toArray();
32             if ((size = elementData.length) != 0) {
33                 if (elementData.getClass() != Object[].class)
34                     elementData = Arrays.copyOf(elementData, size, Object[].class);
35             } else {
36                 this.elementData = EMPTY_ELEMENTDATA;
37             }
38 
39         }

　　构造函数比较简单，无参的构造函数，初始化时直接置为空数组，有参的构造函数初始化时new 一个指定大小的数组对象；如果能事先判断出需要多大容量，那么在创建容器对象时可以选择用有参构造函数初始化一个合适容量的对象，这样能避免空间浪费，也能省去在容量不够时需要重新创建更大容量数组，并且搬迁在原始数组中数据到新数组的所花费时间，第三个是用一个集合初始化新建容器，初始化时先对入参集合做转化elementData = c.toArray()，转化的结果是一个实际集合类型数组对象，由于elementData定义为object类型数组对象，所以要对实际的数组对象做判断，判断结果如不是object类型，则用elementData=Arrays.copyOf(elementData, size, Object[].class)赋值，具体赋值实现如下：

copyof 方法
1    public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
2         @SuppressWarnings("unchecked")
3         T[] copy = ((Object)newType == (Object)Object[].class)
4             ? (T[]) new Object[newLength]
5             : (T[]) Array.newInstance(newType.getComponentType(), newLength);
6         System.arraycopy(original, 0, copy, 0,
7                          Math.min(original.length, newLength));
8         return copy;
9     }

　　根据第三个构造函数传入的第三个参数时Object[].class，所以在copyof 方法中选择创建的是第四行中的object类型数组，然后调用 System.arraycopy将原始的数组对象中的值复制到新创建的object数组中，这就是ArrayList 第三个构造方法，稍显复杂！

　　2.2 插入add方法

对于数组结构的线性容器来说，插入方法分两种情况，第一种在数组尾部插入数据，这种比较简单，另一种是在数组中指定索引位置插入元素，具体代码如下：