简体中文ArrayList
ArrayList是Java集合框架中使用最为频繁的实现，其本质是一个有序的可自由扩容的对象数组。它实现了RandomAccess这个标记接口，意味着其在随机访问性能上有一定优势。
ArrayList继承关系
初始化及扩容机制 #
ArrayList初始化为一个空的对象数组，如果不在构造对象时指定初始容量大小，那么ArrayList的默认初始化一个容量为10的对象数组，其扩容规则是每当新增加对象超出对象数组的容量时，将对象数组的容量增加当前容量的1/2。
参考如下示例：
1static void initializeTest()
2throws NoSuchFieldException, IllegalAccessException {
3 List<Integer> list = new ArrayList<>();
4 // initial size = 10
5
6 for (int i = 0; i <16; i++){
7 list.add(new Random().nextInt(100));
8 // 本体是elementData
9 Field field = list.getClass().getDeclaredField("elementData");
10 field.setAccessible(true);
11 // 获取list的“elementData”
12 Object[] o = (Object[]) field.get(list);
13 // size是ArrayList的长度，length是elementData的长度
14 System.out.println("size = " + (i+1) + ",
15 length = " + o.length + " ,
16 element = " + Arrays.toString(o));
17 }
18}
19/* output:
20size = 1, length = 10 ,element = [15, ...]
21size = 2, length = 10 ,element = [15, ...]
22size = 3, length = 10 ,element = [15, ...]
23size = 4, length = 10 ,element = [15, ...]
24size = 5, length = 10 ,element = [15, ...]
25size = 6, length = 10 ,element = [15, ...]
26size = 7, length = 10 ,element = [15, ...]
27size = 8, length = 10 ,element = [15, ...]
28size = 9, length = 10 ,element = [15, ...]
29size = 10, length = 10 ,element = [15, ...]
30size = 11, length = 15 ,element = [15, ...]
31size = 12, length = 15 ,element = [15, ...]
32size = 13, length = 15 ,element = [15, ...]
33size = 14, length = 15 ,element = [15, ...]
34size = 15, length = 15 ,element = [15, ...]
35size = 16, length = 22 ,element = [15, ...]
36*///:~
ArrayList的内容存储在elementData对象数组中，通过在运行时获取对象信息，能够窥视ArrayList的初始化过程：
elementData初始化为容量默认为10，内容为空的对象数组new Object[10] = {}添加第10个元素时，此时
elementData的容量也是10，无法容纳更多元素，需扩容，源码如下：1if (minCapacity - elementData.length > 0){ 2 int oldCapacity = elementData.length; 3 // 扩容 扩容方式为将容量增加一半 4 int newCapacity = oldCapacity + (oldCapacity >> 1); 5 if (newCapacity - minCapacity < 0) 6 newCapacity = minCapacity; 7 if (newCapacity - MAX_ARRAY_SIZE > 0) 8 newCapacity = hugeCapacity(minCapacity); 9 // minCapacity is usually close to size, so this is a win: 10 elementData = Arrays.copyOf(elementData, newCapacity); 11}使用
Arrays.copyOf()方法将elementData重新引用至新的拷贝数组——这一过程去尾。数组扩容也有一定的开销，实际使用过程中最好预估并定义ArrayList的初始容量，避免因数据增长频繁扩容。
迭代器 #
集合框架的继承关系图显示，Collection接口继承了 Iterable 接口，这意味着所有的集合实现都可以使用迭代器操作集合。
作为使用最广的集合实现，ArrayList可以获取 Iterator 和 ListIterator 的实现，后者继承了前者，在前者的基础上新增了一些用于可逆迭代（ cursor在集合中来回穿梭 ）的特性，如previous()，previousIndex()等方法。
迭代器方法表
下面代码简单展示了迭代器的使用：
1static void iteratorTest() {
2 List<String> a = new ArrayList<String>() {{
3 add("apple");
4 add("google");
5 add("amazon");
6 add("cisco");
7 add("facebook");
8 add("twitter");
9 }};
10 Iterator<String> iterator = a.iterator();
11 a.remove(2);
12 // throw ConcurrentModificationException
13 // System.out.println(iterator.next());
14 // 重新获取迭代器，避免上述异常
15 Iterator<String> newIterator = a.iterator();
16 newIterator.next();
17 // Java 8新增方法，迭代剩余元素
18 newIterator.forEachRemaining(s -> {
19 s= s.replaceFirst("g","G");
20 System.out.println(s);
21 });
22}
23/* output:
24Google
25cisco
26facebook
27twitter
28*///:~
1static void listIteratorTest() {
2 ListIterator<String> listIterator = a.listIterator();
3 listIterator.next();
4 // do not change cursor
5 listIterator.set("Apple");
6 listIterator.previous();
7 while (listIterator.hasNext()) {
8 System.out.println(listIterator.next());
9 }
10 System.out.println("-------");
11 // cursor changed
12 listIterator.remove();
13 listIterator.add("TWITTER"); // cursor in the end
14 // reverse output
15 while (listIterator.hasPrevious()) {
16 System.out.println(listIterator.previous());
17 }
18}
19/* output:
20Apple
21google
22twitter
23-------
24TWITTER
25google
26Apple
27*///:~
关于集合的迭代器1，作如下说明：
当集合和迭代器持有的“计数器”不一致时，迭代器的 ConcurrentModificationException 出现：
计数器：记录发生集合结构性变化的次数，一般指集合元素增删，更新集合元素值一般不会被视作结构性变化2；迭代器也维护一个计数器，此数字初始化为原集合计数器的值。
需要记住的是，迭代器的计数器只能通过迭代器维护（ 调用迭代器的add()，remove()等方法会更新计数器 ，因此不会抛出上述异常），而集合的计数器却可以通过迭代器和集合维护，亦即通过迭代器更新的计数器会同步更新集合的计数器（ 因为迭代器方法也是通过集合方法实现的 ）；反之不亦然，记住，在获取迭代器之后，在使用集合而非迭代器的方法修改集合结构，那么迭代器会发生异常（ 2个计数器值不一致 ）
参考
ArrayList.Itr.remove()3源码：1public void remove() { 2 if (lastRet < 0) 3 throw new IllegalStateException(); 4 checkForComodification(); 5 6 try { 7 ArrayList.this.remove(lastRet); 8 cursor = lastRet; 9 lastRet = -1; 10 // 更新计数器 11 expectedModCount = modCount; 12 } catch (IndexOutOfBoundsException ex) { 13 throw new ConcurrentModificationException(); 14 } 15} 16final void checkForComodification() { 17 // 一致性检查 18 if (modCount != expectedModCount) 19 throw new ConcurrentModificationException(); 20}不论是 Iterator 或 ListIterator 接口在Java集合框架中都没有独立的实现类，都是作为集合具体实现的内部类存在的，这种机制使得不同的集合类型，拥有“定制”的迭代器类型，这意味着方法表并不是一成不变的，如
ArrayList.ListIterator就缺失hasNext()方法。
LinkedList(左)和ArrayList(右)内部ListIterator的实现差异
这种只定义接口而使用内部类实现的现象在Java集合框架中非常常见，理解这一点有利于理解集合视图( Collection view )，接下来这个概念将多次出现。
按照理论，
ListItr实现了ListIterator接口应该覆盖所有方法，Intellij IDEA编译器对于ArrayList的内部类ListItr给出了 method should be defined since the class is not abstract的批注，这或许是Java源码的豁免权。实际上，
ArrayList.ListItr同时也继承了ArrayList.Itr，因此，ListItr缺失的方法由Itr实现了。Java 8的改进
Java 8 新增的函数式接口，在集合框架中得到广泛使用，关于Java 8对集合框架的优化，后文将单独说明（挖坑？）。
例如在迭代器 Iterator 接口中，新增了一个方法：
1default void forEachRemaining(Consumer<? super E> action) { 2Objects.requireNonNull(action); 3while (hasNext()) 4 action.accept(next()); 5}这是一 默认方法，其接受一个 Consumer 参数，用来对元素执行操作，需要注意的是此迭代器的指针( cursor )并不是0，而是当前实际的指针，亦即此法用于迭代还未被此迭代器迭代的元素
SubList(集合视图) #
SubList是ArrayList的内部类，是方法subList(int fromIndex, int toIndex)的返回对象，也就是说，ArrayList.subList()的返回不是一个ArrayList实例，而是一个视图。
1public List<E> subList(int fromIndex, int toIndex) {
2 subListRangeCheck(fromIndex, toIndex, size);
3 return new SubList<>(this, fromIndex, toIndex);
4}
所谓集合视图，可以通俗的理解为集合的内部类4，如Sublist，其一个主要的特点是可以更改原集合（作用可以理解为原集合的一个代理）。
1private class SubList extends AbstractList<E> implements RandomAccess {
2 //...
3}
SubList可以看作一个"类ArrayList"，方法也有很多共性，而往往只需要注意差异即可。
参考下例：
1static void subListTest(){
2 List<String> a = new ArrayList<String>() {{
3 add("apple");
4 add("google");
5 add("amazon");
6 add("cisco");
7 }};
8 List<String> strings = a.subList(1, 2); // [google]
9 System.out.println("Is subList instance of ArrayList? "
10 + (strings instanceof ArrayList)
11 + "\n-------");
12 // a.add("Java") // ERROR! cause ConcurrentModificationException for subList
13 ListIterator<String> subIterator = strings.listIterator();
14 while (subIterator.hasNext()){
15 subIterator.set(subIterator.next().toUpperCase() + " revised by subList");
16 }
17 // 增加元素
18 subIterator.add("foobar added by subList");
19 a.forEach(System.out::println);
20 // 删除子集，父集也删除元素
21 strings.clear();
22 System.out.println("-------");
23 a.forEach(System.out::println);
24}
25/* output:
26Is subList instance of ArrayList? false
27-------
28apple
29GOOGLE revised by subList
30foobar added by subList
31amazon
32cisco
33-------
34apple
35amazon
36cisco
37*///:~
之所以将其称为视图，一个很重要的原因就是，这个类所有有利数据全部来自外围类(ArrayList)，其能够修改外围类的能力来自于直接对外围类方法的调用5：
1public void add(int index, E e) {
2 rangeCheckForAdd(index);
3 checkForComodification();
4 // 实际上调用的就是外围类的方法
5 parent.add(parentOffset + index, e);
6 this.modCount = parent.modCount;
7 this.size++;
8}
实际上，可以将SubList理解为ArrayList实用工具的巧妙封装。
和迭代器一样，获取SubList之后，对原集合进行结构性改变，也会引起ConcurrentModificationException。
插入与删除 #
前文提到，尽管ArrayList因实现了Random接口而具有很好的随机读取性，但是ArrayList也有一些缺点，比如差强人意的插入和删除。
ArrayList方法：
1public void add(int index, E e) {...}
2public E remove(int index) {...}
3public boolean remove(Object o) {...}
4...
实现了从插入集合到指定索引为止或从集合中删除（指定索引）元素，但这些操作并不是ArrayList的强项，以add(int index, E e)为例：
1public void add(int index, E element) {
2 rangeCheckForAdd(index);
3
4 ensureCapacityInternal(size + 1); // Increments modCount!!
5 // 拷贝数组--实际上是将数组index位置以后的所有元素”后移一位“
6 System.arraycopy(elementData, index, elementData, index + 1,
7 size - index);
8 elementData[index] = element;
9 size++;
10}
同理，从ArrayList的删除相关方法中也可以看到类似的操作，这意味着在操作大量数据的时候，ArrayList可能会遇到性能问题。在对象数组长度很小时，这种影响一般可以忽略。
