JDK源码阅读—ArrayList的实现
1 继承结构图
ArrayList继承AbstractList，实现了List接口
2 构造函数
transient Object[] elementData; // 数组保存元素
private int size; // 记录长度
size记录ArrayList的长度，elementData记录元素的值
transient是Java语言的关键字，用来表示一个域不是该对象串行化的一部分。当一个对象被串行化的时候，transient型变量的值不包括在串行化的表示中，然而非transient型的变量是被包括进去的。transient详细介绍如链接：transient关键字介绍
三种构造方法
public ArrayList(int initialCapacity)
参数为长度，必须为大于等于0整数，如果传入0，与第二种构造方法结果相同，都是建立一个空的Object数组
Public ArrayList()
创建一个空的Object数组
Public ArrayList(Collection <?extendsE> c)
如果参数不为空，则使用Collection的toArray方法，把c转为对象数组，否则创建一个空的Object数组
3 需要注意的方法
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
常使用的是set(E element)这个方法 set方法如果使用set(int index, E element)这个方法，index对应的位置如果已经有值，该值会被新set的对象替换，并且返回旧值
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
平时使用都是使用add(E element)，如果使用了add(int index, E element)这个方法，从上图的实现来看，它会先把记录元素的数组长度加1，然后把index之后的元素全部都后移一位，然后把新插入的元素放在索引为index的位置
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
remove(int index)的删除方法是把index之后的元素都往前移动一个位置，所以如果你用for循环遍历ArrayList并且在循环中满足某个条件就remove掉一个元素，那么就会抛出IndexOutOfBoundsException
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;
}
Remove(Object o)会从前往后查找，找到第一个相等的对象进行删除，删除的原理也是后面的元素前移一位，所以遍历ArrayList最好用迭代器进行遍历。
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
addAll(int index, Collection c)如果当前ArrayList的长度小于index，直接从index开始，把c的元素按顺序摆放，如果当前ArrayList的长度大于Index，则把c插入到当前ArrayList的index 到index+c.length的位置，再把原ArrayList的剩余元素接到后面
4 不常用方法
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
batchRemove不常用方法，可以批量删除当前list中包含（complement == true）或不包含（complement == false）某个集合c中所有元素。并返回操作的结果。
备注
上面说到了，直接使用ArrayList的remove在遍历中很容易出错，下面看看它的迭代器是怎么实现remove的
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
Itr() {}
public boolean hasNext() {
return cursor != size;
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
cursor记录要访问的下一个index,lastRet记录当前已经读到的index，迭代器在remove的时候，先调用ArrayList的remove方法删除对应元素，同时，会把cursor和lastRet都减1，自动帮我们完成了元素的重新定位。
2 构造函数
transient Object[] elementData; // 数组保存元素
private int size; // 记录长度
size记录ArrayList的长度，elementData记录元素的值
transient是Java语言的关键字，用来表示一个域不是该对象串行化的一部分。当一个对象被串行化的时候，transient型变量的值不包括在串行化的表示中，然而非transient型的变量是被包括进去的。transient详细介绍如链接：transient关键字介绍
三种构造方法
public ArrayList(int initialCapacity)
参数为长度，必须为大于等于0整数，如果传入0，与第二种构造方法结果相同，都是建立一个空的Object数组
Public ArrayList()
创建一个空的Object数组
Public ArrayList(Collection <?extendsE> c)
如果参数不为空，则使用Collection的toArray方法，把c转为对象数组，否则创建一个空的Object数组
3 需要注意的方法
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
常使用的是set(E element)这个方法 set方法如果使用set(int index, E element)这个方法，index对应的位置如果已经有值，该值会被新set的对象替换，并且返回旧值
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
平时使用都是使用add(E element)，如果使用了add(int index, E element)这个方法，从上图的实现来看，它会先把记录元素的数组长度加1，然后把index之后的元素全部都后移一位，然后把新插入的元素放在索引为index的位置
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
remove(int index)的删除方法是把index之后的元素都往前移动一个位置，所以如果你用for循环遍历ArrayList并且在循环中满足某个条件就remove掉一个元素，那么就会抛出IndexOutOfBoundsException
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;
}
Remove(Object o)会从前往后查找，找到第一个相等的对象进行删除，删除的原理也是后面的元素前移一位，所以遍历ArrayList最好用迭代器进行遍历。
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
addAll(int index, Collection c)如果当前ArrayList的长度小于index，直接从index开始，把c的元素按顺序摆放，如果当前ArrayList的长度大于Index，则把c插入到当前ArrayList的index 到index+c.length的位置，再把原ArrayList的剩余元素接到后面
4 不常用方法
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
batchRemove不常用方法，可以批量删除当前list中包含（complement == true）或不包含（complement == false）某个集合c中所有元素。并返回操作的结果。
备注
上面说到了，直接使用ArrayList的remove在遍历中很容易出错，下面看看它的迭代器是怎么实现remove的
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
Itr() {}
public boolean hasNext() {
return cursor != size;
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
cursor记录要访问的下一个index,lastRet记录当前已经读到的index，迭代器在remove的时候，先调用ArrayList的remove方法删除对应元素，同时，会把cursor和lastRet都减1，自动帮我们完成了元素的重新定位。
