ArrayList继承于 AbstractList，实现了 List, RandomAccess, Cloneable, java.io.Serializable 这些接口，其中RandomAccess代表了其拥有随机快速访问的能力。
他的实现是数组，但是我们知道数组都要指定长度，很显然我们平时在使用的时候并没有指定长度，这是因为代码在帮我们自动做扩容操作！由于底层数据结构是数组，所以可想而知，它是占据一块连续的内存空间（容量就是数组的length），所以它也有数组的缺点，空间效率不高。
add,delete元素的时间复杂度为O（n）,size, isEmpty, get, set, iterator, and listIterator 等操作的复杂度为 O(1)。
另外要十分注意的是它是线程不安全的！允许元素为 null。
成员变量
//默认的初始容量 10
private static final int DEFAULT_CAPACITY = 10;
//空数组（用于空实例）。
private static final Object[] EMPTY_ELEMENTDATA = {};
//默认构造函数里的空数组
//我们把它从EMPTY_ELEMENTDATA数组中区分出来，以知道在添加第一个元素时容量需要增加多少。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//存储集合元素的底层实现：真正存放元素的数组
transient Object[] elementData;
//ArrayList 所包含的元素个数
private int size;构造方法
//带初始容量的构造方法
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//如果初始容量大于0，则新建一个长度为initialCapacity的Object数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//容量为0返回空数组
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
// 无参构造方法，默认初始容量10
//注意：初始化的时候是空数组 当添加第一个元素的时候数组容量才变成10
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(Collection<? extends E> c) {
////直接利用Collection.toArray()方法得到一个对象数组，并赋值给elementData
elementData = c.toArray();
// //因为size代表的是集合元素数量，所以通过别的集合来构造ArrayList时，要给size赋值
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
////这里是当c.toArray出错，可能返回的不是Object类型的数组所以加上下面的语句用于判断，利用Arrays.copyOf 来复制集合c中的元素到elementData数组中
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 用空数组代替
this.elementData = EMPTY_ELEMENTDATA;
}
}添加元素与扩容
boolean add(E e)
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
//在数组末尾追加一个元素，并修改size
elementData[size++] = e;
return true;
} private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
} private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//默认的空实例第一次添加元素时，使用默认的容量大小与minCapacity的最大值
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
} //判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
//已对该List进行结构修改的次数。
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
//调用grow方法进行扩容，调用此方法代表已经开始扩容了
grow(minCapacity);
} //需要扩容的话，默认扩容一半
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//将oldCapacity 右移一位，其效果相当于oldCapacity /2，
int newCapacity = oldCapacity + (oldCapacity >> 1);
//然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//再检查新容量是否超出了ArrayList所定义的最大容量，
//若超出了，则调用hugeCapacity()来比较minCapacity和 MAX_ARRAY_SIZE，
//如果minCapacity大于MAX_ARRAY_SIZE，则新容量则为Interger.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE。
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//调用 Arrays.copyOf 复制原数组，将 elementData 赋值为得到的新数组
elementData = Arrays.copyOf(elementData, newCapacity);
} //最大数组长度，有些虚拟机需要一些头字段，如果超过可能报oom
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}从上面的代码我们大概可以知道数组复制代价较高，所以建议在创建 ArrayList 对象时就指定大概的容量大小，减少扩容操作的次数。
void add(int index, E element)
public void add(int index, E element) {
//检测数组是否越界
rangeCheckForAdd(index);
//保证capacity足够大,因为下面要复制数组
ensureCapacityInternal(size + 1); // Increments modCount!!
//将index开始的数据 向后移动一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
} private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}native复制方法
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);src:源数组;
srcPos:源数组要复制的起始位置;
dest:目的数组;
destPos:目的数组放置的起始位置;
length:复制的长度.
我们简单解释一下，我们先将当前的数组index后面的数据复制到index+1后，就形成了我们将数组后挪一位的错觉，那么原来的index坑位留出来了，所以这时候再将index位置为新的数据，完成新增。
boolean addAll(Collection<? extends E> c)
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
// 复制元素到原数组尾部
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}boolean addAll(int index, Collection<? extends E> c)
添加到指定位置
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;
}同样也是把原来的数组从index开始向后挪出a.length的长度，再将需要插入的数据复制放入。
删除元素
切记：不能在循环中删除调用以下的方法！！！动态删除元素应该使用迭代器！
E remove(int 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);
//置空原尾部数据 不再强引用， 可以GC掉
elementData[--size] = null; // clear to let GC do its work
//返回被删除的值
return oldValue;
}boolean remove(Object o)
分两步，o为null和不为null，因为要用到o.equal()。循环遍历数组找到相同值的index，然后执行复制覆盖原来的值，同上。
//删除该元素在数组中第一次出现的位置上的数据。 如果有该元素返回true，如果false。
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
//根据index删除元素
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}private void fastRemove(int index) {
modCount++;
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
}boolean removeAll(Collection<?> c
// 删除在指定集合中的所有元素
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
// 删除不在指定集合中的所有元素，也就是只保留指定集合中的元素，其它的都删除掉,取交集
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
// r为当前下标，w为当前需要保留的元素的数量（或者说是下一个需保留元素的下标）
int r = 0, w = 0;
boolean modified = false;
try {
//保存两个集合公有元素的算法,可以学习一下
for (; r < size; r++)
// 判断元素 elementData[r] 是否需要删除
if (c.contains(elementData[r]) == complement)
//保留
elementData[w++] = elementData[r];
} finally {
// r != size 的情况可能是 c.contains() 抛出了异常，则将出现异常处后面的数据全部复制覆盖到数组里。
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
//修改 w数量
w += size - r;
}
if (w != size) {
//置空数组后面的元素
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
// 修改size
size = w;
modified = true;
}
}
return modified;
}原理是当前的数组，如果不需要删除，则将循环的当前值赋予到当前的数组的第一个，由于r一定是大于等于w的情况，所以elementData[w++]的数据一定是遍历过的，可以进行直接替换。当遍历结束肯定会出现r>=w的情况，这时候需要把数组进行缩减，将w之后到size的值全部置为null，等到GC进行回收。
修改元素
public E set(int index, E element) {
//越界检查
rangeCheck(index);
//下标取数据
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}清空元素
public void clear() {
modCount++;
//全部元素置为 null，去除强引用，等待GC
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}是否包含
public boolean contains(Object o) {
return indexOf(o) >= 0;
}public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}同样在判断是否包含的时候，是采用了遍历的形式，所以在性能上是较为差劲的，如果你循环一个大的数组那么性能开销是十分大的，就需要考虑是否用HashSet来处理，在项目中也遇到相关的问题，两个循环来进行判断contains时间复杂度直接指数上升，性能降低！
获取元素
public E get(int index) {
rangeCheck(index);
return elementData(index);
}遍历
ArrayList 三种遍历方式：
- for循环下标遍历
- 迭代器(Iterator和ListIterator)
- foreach 语句
- ListIterator 有 add() 方法，可以向List中添加对象，而 Iterator 不能
- ListIterator 和 Iterator 都有 hasNext() 和 next() 方法，可以实现顺序向后遍历，但是 ListIterator 有 hasPrevious() 和 previous() 方法，可以实现逆向（顺序向前）遍历。Iterator 就不可以。
- ListIterator 可以定位当前的索引位置，nextIndex() 和 previousIndex() 可以实现。Iterator 没有此功能。
- 都可实现删除对象，但是 ListIterator 可以实现对象的修改，set() 方法可以实现。Iierator 仅能遍历，不能修改
forEach
这是Java 8 新增的方法，使用函数式接口Consumer进行执行相应的内容，内部循环，代码会更加美观一点。
关于forEach和for循环哪一个性能好呢可以看这篇博文：【java8】为java8的foreach正名
测试的结果是在JVM预热之后相差无几。
@Override
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}动态删除元素
Iterator
我们在上文提到无法通过remove直接在循环中删除元素，所以我们可以借鉴于迭代器进行删除：
List<String> list=new ArrayList<>();
list.add("abc");
list.add("bbc");
list.add("123");
Iterator iterator =list.iterator();
while(iterator.hasNext()){
if(iterator.next().equals("123")) {
iterator.remove();
}
}removeIf
既然现在是Java 8的时代，那就康康Java 8有没有给我们带来惊喜！我们找到了removeIf()方法。
default boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
boolean removed = false;
final Iterator<E> each = iterator();
while (each.hasNext()) {
if (filter.test(each.next())) {
each.remove();
removed = true;
}
}
return removed;
}我们可以看到在方法内部用迭代器帮我们实现了第一种方式的删除！隐藏了迭代细节。所以我们只需要写一行代码了！
list.removeIf(o -> o.equals("123"));序列化
为什么ArrayList的elementData使用transient修饰
我们注意到ArrayList 有两个属性被 transient 关键字修饰，transient 关键字 的作用：让某些被修饰的成员属性变量不被序列化
transient Object[] elementData;
protected transient int modCount = 0;这要从Java序列化机制说起了
- 当某个字段被声明为transient后，默认序列化机制就会忽略该字段，反序列化后自动获得0或者null值
- 每个类可以实现readObject、writeObject方法实现自己的序列化策略，即使是transient修饰的成员变量也可以手动调用ObjectOutputStream的writeInt等方法将这个成员变量序列化。
所以ArrayList 不想用Java序列化机制的默认处理来序列化 elementData 数组，而是通过 readObject、writeObject 方法自定义序列化和反序列化策略。
问题又来了，为什么不用Java序列化机制的默认处理来序列化 elementData 数组呢？
- elementData不总是满的，每次都序列化，会浪费时间和空间
- 重写了writeObject 保证序列化的时候虽然不序列化全部，但是有的元素都序列化
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
// 默认的序列化策略，序列化其它的字段
s.defaultWriteObject();
// 实际用的长度，而不是容量
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
int capacity = calculateCapacity(elementData, size);
SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
ensureCapacityInternal(size);
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}modeCount
modCount 用来记录 ArrayList 结构发生变化的次数，如果一个动作前后 modCount 的值不相等，说明 ArrayList 被其它线程修改了。
如果在创建迭代器之后的任何时候以任何方式修改了列表（增加、删除、修改），除了通过迭代器自己的remove 或 add方法，迭代器将抛出 ConcurrentModificationException 异常
需要注意的是：这里异常的抛出条件是检测到 modCount != expectedmodCount，如果并发场景下一个线程修改了modCount值时另一个线程又 “及时地” 修改了expectedmodCount值，则异常不会抛出。所以不能依赖于这个异常来检测程序的正确性。