java jdk是如何实现ArrayList的？
ArrayList的实现很简单，总的来说，就是arraylist内置了一个Object类型的数组，当插入或删除数据时，都操作这个内置数组array。当用户想new的ArrayList大于内置数组时，会在后面串一个数组，具体数组怎么递增看下文。
1. ArrayList中的属性
//数组每次增加长度时最小增量（具体每次增加时，增量不一定是MIN_CAPACITY_INCREMENT，有一定的策略）
private static final int MIN_CAPACITY_INCREMENT = 12;
//ArrayList的长度
int size;
//数组
transient Object[] array;
2. 构造函数
我们先来看看构造函数怎么实现的。
2.1 不指定大小
像这样定义：
ArrayList arrayList = new ArrayList();
直接创建一个大小为0的ArrayList实例。
public ArrayList() {
array = EmptyArray.OBJECT;
}
2.2 指定int类型的大小（容量）
像这样定义：
ArrayList arrayList = new ArrayList(10);
如果指定的容量大小capacity为0，则只创建一个容量为0的ArrayList实例，否则，直接new一个指定大小的Object类型的数组。
public ArrayList(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException("capacity < 0: " + capacity);
}
array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]);
}
2.3 创建一个包含指定Collection的list
像这样定义：
ArrayList arrayList = new ArrayList(Collection collection);
直接把Collection转换为数组，并复制给ArrayList的数组array。具体实现如下：
private static int newCapacity(int currentCapacity) {
int increment = (currentCapacity < (MIN_CAPACITY_INCREMENT / 2) ?
MIN_CAPACITY_INCREMENT : currentCapacity >> 1);
return currentCapacity + increment;
}
3 增量的确定
3.1 插入数据时，ArrayList内置数组增量的确定
ArrayList插入涉及到数组增量的问题，即插入一个数或一组数时，ArrayList内置的数组该如何增长？如果频繁增长，既浪费时间又会使内存碎片化；可如果每次增量很大，如每插入数据内置数组就增加很大的容量值，那么会导致很多空间浪费。 jdk有一个方法提供了具体策略：
private static int newCapacity(int currentCapacity) {
int increment = (currentCapacity < (MIN_CAPACITY_INCREMENT / 2) ?
MIN_CAPACITY_INCREMENT : currentCapacity >> 1);
return currentCapacity + increment;
}
如果指定增量currentCapacity小于12/2=6，则增量为12；否则增量为currentCapacity/2.
注：currentCapacity >> 1 即为currentCapacity/2.如：
0000 0111（7）>> 1 右移一位变为 0000 0011（3）。
0000 1100（12）>> 1 右移一位变为 0000 0110（6）。
3.2 在index位置插入一个数object
我们来看一下方法，add(int index, E object),在index位置插入一个Object类型的数。
@Override
public void add(int index, E object) {
Object[] a = array;
int s = size;
if (index > s || index < 0) {
throwIndexOutOfBoundsException(index, s);
}
if (s < a.length) {
System.arraycopy(a, index, a, index + 1, s - index);
} else {
// assert s == a.length;
Object[] newArray = new Object[newCapacity(s)];
System.arraycopy(a, 0, newArray, 0, index);
System.arraycopy(a, index, newArray, index + 1, s - index);
array = a = newArray;
}
a[index] = object;
size = s + 1;
//父类AbstractList的一个属性，记录list改变了几项
modCount++;
}
其实就是
先根据newCapacity方法获取到数组增量，
然后new一个临时数组newArray，先把当前数组array从[0,index]都copy给newArray的[0,index]，
然后把array从 [index,s]（数组末尾）copy给newArray的[index+1,s+1]，这样全部数组就复制过来了，然后把newArray copy给array；
最后令array[index+1]为新插入的值object，size+1。
3.3 在index位置插入一个collection
这种情况下增量是多少呢？
注意：ArrayList并不是直接增加collection.length()的长度，而是通过newCapacity方法来计算增量，传入的参数是 当前数组的长度(size+newSize).
其中 newSize为新数组newArray(collection.toArray())的长度.
前面我们说过，如果一次增量过小，会造成频繁增加数组，这样既浪费时间，又会损耗性能。
代码如下：
@Override
public boolean addAll(int index, Collection<? extends E> collection) {
int s = size;
if (index > s || index < 0) {
throwIndexOutOfBoundsException(index, s);
}
Object[] newPart = collection.toArray();
int newPartSize = newPart.length;
if (newPartSize == 0) {
return false;
}
Object[] a = array;
int newSize = s + newPartSize; // If add overflows, arraycopy will fail
if (newSize <= a.length) {
System.arraycopy(a, index, a, index + newPartSize, s - index);
} else {
int newCapacity = newCapacity(newSize - 1); // ~33% growth room
Object[] newArray = new Object[newCapacity];
System.arraycopy(a, 0, newArray, 0, index);
System.arraycopy(a, index, newArray, index + newPartSize, s-index);
array = a = newArray;
}
System.arraycopy(newPart, 0, a, index, newPartSize);
size = newSize;
modCount++;
return true;
}
4. remove方法
4.1 remove(int index)
先把index后面的值全部向前移一位，然后把最后一位a[s]置为空。
@Override
public E remove(int index) {
Object[] a = array;
int s = size;
if (index >= s) {
throwIndexOutOfBoundsException(index, s);
}
@SuppressWarnings("unchecked") E result = (E) a[index];
//核心代码
//把数组a[index+1,s]复制给数组a[index,s-1]
System.arraycop
y(a, index + 1, a, index, --s - index);
//数组最后以为置空
a[s] = null; // Prevent memory leak
size = s;
modCount++;
return result;
}
4.2 clean方法
把数组全部置空。
@Override public void clear() {
if (size != 0) {
Arrays.fill(array, 0, size, null);
size = 0;
modCount++;
}
}
public static void fill(Object[] array, int start, int end, Object value) {
Arrays.checkStartAndEnd(array.length, start, end);
for (int i = start; i < end; i++) {
array[i] = value;
}
}