關于 JDK 的集合類的整體介紹可以看 這張圖 ，本篇部落格我們不系統的介紹整個集合的構造，重點是介紹 ArrayList 類是如何實作的。
1、ArrayList 定義
ArrayList 是一個用數組實作的集合，支援随機通路，元素有序且可以重複。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
①、實作 RandomAccess 接口
這是一個标記接口，一般此标記接口用于 List 實作，以表明它們支援快速（通常是恒定時間）的随機通路。該接口的主要目的是允許通用算法改變其行為，以便在應用于随機或順序通路清單時提供良好的性能。
比如在工具類 Collections(這個工具類後面會詳細講解)中，應用二分查找方法時判斷是否實作了 RandomAccess 接口：
1 int binarySearch(List<? extends Comparable<? super T>> list, T key) {
2 if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
3 return Collections.indexedBinarySearch(list, key);
4 else
5 return Collections.iteratorBinarySearch(list, key);
6 } View Code
②、實作 Cloneable 接口
這個類是 java.lang.Cloneable，前面我們講解
深拷貝和淺拷貝的原理時，我們介紹了淺拷貝可以通過調用 Object.clone() 方法來實作，但是調用該方法的對象必須要實作 Cloneable 接口，否則會抛出 CloneNoSupportException
異常。
Cloneable 和 RandomAccess 接口一樣也是一個标記接口，接口内無任何方法體和常量的聲明，也就是說如果想克隆對象，必須要實作 Cloneable 接口，表明該類是可以被克隆的。
③、實作 Serializable 接口
這個沒什麼好說的，也是标記接口，表示能被序列化。
④、實作 List 接口
這個接口是 List 類集合的上層接口，定義了實作該接口的類都必須要實作的一組方法，如下所示，下面我們會對這一系列方法的實作做詳細介紹。
2、字段屬性
//集合的預設大小
private static final int DEFAULT_CAPACITY = 10;
//空的數組執行個體
private static final Object[] EMPTY_ELEMENTDATA = {};
//這也是一個空的數組執行個體，和EMPTY_ELEMENTDATA空數組相比是用于了解添加元素時數組膨脹多少
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//存儲 ArrayList集合的元素，集合的長度即這個數組的長度
//1、當 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 時将會清空 ArrayList
//2、當添加第一個元素時，elementData 長度會擴充為 DEFAULT_CAPACITY=10
transient Object[] elementData;
//表示集合的長度
private int size; 3、構造函數
1 public ArrayList() {
2 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
3 } 此無參構造函數将建立一個 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 聲明的數組，注意此時初始容量是0，而不是大家以為的 10。
注意：根據預設構造函數建立的集合，ArrayList list = new ArrayList();此時集合長度是0.
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
} 初始化集合大小建立 ArrayList 集合。當大于0時，給定多少那就建立多大的數組；當等于0時，建立一個空數組；當小于0時，抛出異常。
1 public ArrayList(Collection<? extends E> c) {
2 elementData = c.toArray();
3 if ((size = elementData.length) != 0) {
4 // c.toArray might (incorrectly) not return Object[] (see 6260652)
5 if (elementData.getClass() != Object[].class)
6 elementData = Arrays.copyOf(elementData, size, Object[].class);
7 } else {
8 // replace with empty array.
9 this.elementData = EMPTY_ELEMENTDATA;
10 }
11 } 這是将已有的集合複制到 ArrayList 集合中去。
4、添加元素
通過前面的字段屬性和構造函數，我們知道 ArrayList 集合是由數組構成的，那麼向 ArrayList 中添加元素，也就是向數組指派。我們知道一個數組的聲明是能确定大小的，而使用 ArrayList 時，好像是能添加任意多個元素，這就涉及到數組的擴容。
擴容的核心方法就是調用前面我們講過的Arrays.copyOf 方法，建立一個更大的數組，然後将原數組元素拷貝過去即可。下面我們看看具體實作：
public boolean add(E e) {
ensureCapacityInternal(size + 1); //添加元素之前，首先要确定集合的大小
elementData[size++] = e;
return true;
} 如上所示，在通過調用 add 方法添加元素之前，我們要首先調用 ensureCapacityInternal 方法來确定集合的大小，如果集合滿了，則要進行擴容操作。
1 private void ensureCapacityInternal(int minCapacity) {//這裡的minCapacity 是集合目前大小+1
2 //elementData 是實際用來存儲元素的數組，注意數組的大小和集合的大小不是相等的，前面的size是指集合大小
3 ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
4 }
5 private static int calculateCapacity(Object[] elementData, int minCapacity) {
6 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//如果數組為空，則從size+1的值和預設值10中取最大的
7 return Math.max(DEFAULT_CAPACITY, minCapacity);
8 }
9 return minCapacity;//不為空，則傳回size+1
10 }
11 private void ensureExplicitCapacity(int minCapacity) {
12 modCount++;
13
14 // overflow-conscious code
15 if (minCapacity - elementData.length > 0)
16 grow(minCapacity);
17 } 在 ensureExplicitCapacity 方法中，首先對修改次數modCount加一，這裡的modCount給ArrayList的疊代器使用的，在并發操作被修改時，提供快速失敗行為（保證modCount在疊代期間不變，否則抛出ConcurrentModificationException異常，可以檢視源碼865行），接着判斷minCapacity是否大于目前ArrayList内部數組長度，大于的話調用grow方法對内部數組elementData擴容，grow方法代碼如下：
1 private void grow(int minCapacity) {
2 int oldCapacity = elementData.length;//得到原始數組的長度
3 int newCapacity = oldCapacity + (oldCapacity >> 1);//新數組的長度等于原數組長度的1.5倍
4 if (newCapacity - minCapacity < 0)//當新數組長度仍然比minCapacity小，則為保證最小長度，新數組等于minCapacity
5 newCapacity = minCapacity;
6 //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 = 2147483639
7 if (newCapacity - MAX_ARRAY_SIZE > 0)//當得到的新數組長度比 MAX_ARRAY_SIZE 大時，調用 hugeCapacity 處理大數組
8 newCapacity = hugeCapacity(minCapacity);
9 //調用 Arrays.copyOf 将原數組拷貝到一個大小為newCapacity的新數組（注意是拷貝引用）
10 elementData = Arrays.copyOf(elementData, newCapacity);
11 }
12
13 private static int hugeCapacity(int minCapacity) {
14 if (minCapacity < 0) //
15 throw new OutOfMemoryError();
16 return (minCapacity > MAX_ARRAY_SIZE) ? //minCapacity > MAX_ARRAY_SIZE,則新數組大小為Integer.MAX_VALUE
17 Integer.MAX_VALUE :
18 MAX_ARRAY_SIZE;
19 } 對于 ArrayList 集合添加元素，我們總結一下：
①、當通過 ArrayList() 構造一個空集合，初始長度是為0的，第 1 次添加元素，會建立一個長度為10的數組，并将該元素指派到數組的第一個位置。
②、第 2 次添加元素，集合不為空，而且由于集合的長度size+1是小于數組的長度10，是以直接添加元素到數組的第二個位置，不用擴容。
③、第 11 次添加元素，此時 size+1 = 11，而數組長度是10，這時候建立一個長度為10+10*0.5 = 15 的數組（擴容1.5倍），然後将原數組元素引用拷貝到新數組。并将第 11 次添加的元素指派到新數組下标為10的位置。
④、第 Integer.MAX_VALUE - 8 = 2147483639，然後 2147483639%1.5=1431655759（這個數是要進行擴容） 次添加元素，為了防止溢出，此時會直接建立一個 1431655759+1 大小的數組，這樣一直，每次添加一個元素，都隻擴大一個範圍。
⑤、第 Integer.MAX_VALUE - 7 次添加元素時，建立一個大小為 Integer.MAX_VALUE 的數組，在進行元素添加。
⑥、第 Integer.MAX_VALUE + 1 次添加元素時，抛出 OutOfMemoryError 異常。
注意：能向集合中添加 null 的，因為數組可以有 null 值存在。
1 Object[] obj = {null,1};
2
3 ArrayList list = new ArrayList();
4 list.add(null);
5 list.add(1);
6 System.out.println(list.size());//2 5、删除元素
①、根據索引删除元素
1 public E remove(int index) {
2 rangeCheck(index);//判斷給定索引的範圍，超過集合大小則抛出異常
3
4 modCount++;
5 E oldValue = elementData(index);//得到索引處的删除元素
6
7 int numMoved = size - index - 1;
8 if (numMoved > 0)//size-index-1 > 0 表示 0<= index < (size-1),即索引不是最後一個元素
9 //通過 System.arraycopy()将數組elementData 的下标index+1之後長度為 numMoved的元素拷貝到從index開始的位置
10 System.arraycopy(elementData, index+1, elementData, index,
11 numMoved);
12 elementData[--size] = null; //将數組最後一個元素置為 null，便于垃圾回收
13
14 return oldValue;
15 } remove(int index) 方法表示删除索引index處的元素，首先通過 rangeCheck(index) 方法判斷給定索引的範圍，超過集合大小則抛出異常；接着通過 System.arraycopy 方法對數組進行自身拷貝。關于這個方法的用法可以參考
這篇部落格。
②、直接删除指定元素
1 public boolean remove(Object o) {
2 if (o == null) {//如果删除的元素為null
3 for (int index = 0; index < size; index++)
4 if (elementData[index] == null) {
5 fastRemove(index);
6 return true;
7 }
8 } else {//不為null，通過equals方法判斷對象是否相等
9 for (int index = 0; index < size; index++)
10 if (o.equals(elementData[index])) {
11 fastRemove(index);
12 return true;
13 }
14 }
15 return false;
16 }
17
18
19 private void fastRemove(int index) {
20 modCount++;
21 int numMoved = size - index - 1;
22 if (numMoved > 0)
23 System.arraycopy(elementData, index+1, elementData, index,
24 numMoved);
25 elementData[--size] = null; //
26 } remove(Object o)方法是删除第一次出現的該元素。然後通過System.arraycopy進行數組自身拷貝。
6、修改元素
通過調用 set(int index, E element) 方法在指定索引 index 處的元素替換為 element。并傳回原數組的元素。
1 public E set(int index, E element) {
2 rangeCheck(index);//判斷索引合法性
3
4 E oldValue = elementData(index);//獲得原數組指定索引的元素
5 elementData[index] = element;//将指定所引處的元素替換為 element
6 return oldValue;//傳回原數組索引元素
7 } 通過調用 rangeCheck(index) 來檢查索引合法性。
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
} 當索引為負數時，會抛出 java.lang.ArrayIndexOutOfBoundsException 異常。當索引大于集合長度時，會抛出 IndexOutOfBoundsException 異常。
7、查找元素
①、根據索引查找元素
1 public E get(int index) {
2 rangeCheck(index);
3
4 return elementData(index);
5 } 同理，首先還是判斷給定索引的合理性，然後直接傳回處于該下标位置的數組元素。
②、根據元素查找索引
1 public int indexOf(Object o) {
2 if (o == null) {
3 for (int i = 0; i < size; i++)
4 if (elementData[i]==null)
5 return i;
6 } else {
7 for (int i = 0; i < size; i++)
8 if (o.equals(elementData[i]))
9 return i;
10 }
11 return -1;
12 } 注意：indexOf(Object o) 方法是傳回第一次出現該元素的下标，如果沒有則傳回 -1。
還有 lastIndexOf(Object o) 方法是傳回最後一次出現該元素的下标。
8、周遊集合
①、普通 for 循環周遊
前面我們介紹查找元素時，知道可以通過get(int index)方法，根據索引查找元素，那麼周遊同理：
1 ArrayList list = new ArrayList();
2 list.add("a");
3 list.add("b");
4 list.add("c");
5 for(int i = 0 ; i < list.size() ; i++){
6 System.out.print(list.get(i)+" ");
7 } ②、疊代器 iterator
先看看具體用法：
1 ArrayList<String> list = new ArrayList<>();
2 list.add("a");
3 list.add("b");
4 list.add("c");
5 Iterator<String> it = list.iterator();
6 while(it.hasNext()){
7 String str = it.next();
8 System.out.print(str+" ");
9 } 在介紹 ArrayList 時，我們知道該類實作了 List 接口，而 List 接口又繼承了 Collection 接口，Collection 接口又繼承了 Iterable 接口，該接口有個 Iterator<T> iterator() 方法，能擷取 Iterator 對象，能用該對象進行集合周遊，為什麼能用該對象進行集合周遊？我們再看看 ArrayList 類中的該方法實作：
1 public Iterator<E> iterator() {
2 return new Itr();
3 } 該方法是傳回一個 Itr 對象，這個類是 ArrayList 的内部類。
1 private class Itr implements Iterator<E> {
2 int cursor; //遊标， 下一個要傳回的元素的索引
3 int lastRet = -1; // 傳回最後一個元素的索引; 如果沒有這樣的話傳回-1.
4 int expectedModCount = modCount;
5
6 //通過 cursor ！= size 判斷是否還有下一個元素
7 public boolean hasNext() {
8 return cursor != size;
9 }
10
11 @SuppressWarnings("unchecked")
12 public E next() {
13 checkForComodification();//疊代器進行元素疊代時同時進行增加和删除操作，會抛出異常
14 int i = cursor;
15 if (i >= size)
16 throw new NoSuchElementException();
17 Object[] elementData = ArrayList.this.elementData;
18 if (i >= elementData.length)
19 throw new ConcurrentModificationException();
20 cursor = i + 1;//遊标向後移動一位
21 return (E) elementData[lastRet = i];//傳回索引為i處的元素，并将 lastRet指派為i
22 }
23
24 public void remove() {
25 if (lastRet < 0)
26 throw new IllegalStateException();
27 checkForComodification();
28
29 try {
30 ArrayList.this.remove(lastRet);//調用ArrayList的remove方法删除元素
31 cursor = lastRet;//遊标指向删除元素的位置，本來是lastRet+1的，這裡删除一個元素，然後遊标就不變了
32 lastRet = -1;//lastRet恢複預設值-1
33 expectedModCount = modCount;//expectedModCount值和modCount同步，因為進行add和remove操作，modCount會加1
34 } catch (IndexOutOfBoundsException ex) {
35 throw new ConcurrentModificationException();
36 }
37 }
38
39 @Override
40 @SuppressWarnings("unchecked")
41 public void forEachRemaining(Consumer<? super E> consumer) {//便于進行forEach循環
42 Objects.requireNonNull(consumer);
43 final int size = ArrayList.this.size;
44 int i = cursor;
45 if (i >= size) {
46 return;
47 }
48 final Object[] elementData = ArrayList.this.elementData;
49 if (i >= elementData.length) {
50 throw new ConcurrentModificationException();
51 }
52 while (i != size && modCount == expectedModCount) {
53 consumer.accept((E) elementData[i++]);
54 }
55 // update once at end of iteration to reduce heap write traffic
56 cursor = i;
57 lastRet = i - 1;
58 checkForComodification();
59 }
60
61 //前面在新增元素add() 和 删除元素 remove() 時，我們可以看到 modCount++。修改set() 是沒有的
62 //也就是說不能在疊代器進行元素疊代時進行增加和删除操作，否則抛出異常
63 final void checkForComodification() {
64 if (modCount != expectedModCount)
65 throw new ConcurrentModificationException();
66 }
67 } 注意在進行 next() 方法調用的時候，會進行 checkForComodification() 調用，該方法表示疊代器進行元素疊代時，如果同時進行增加和删除操作，會抛出 ConcurrentModificationException 異常。比如：
1 ArrayList<String> list = new ArrayList<>();
2 list.add("a");
3 list.add("b");
4 list.add("c");
5 Iterator<String> it = list.iterator();
6 while(it.hasNext()){
7 String str = it.next();
8 System.out.print(str+" ");
9 list.remove(str);//集合周遊時進行删除或者新增操作，都會抛出 ConcurrentModificationException 異常
10 //list.add(str);
11 list.set(0, str);//修改操作不會造成異常
12 } 解決辦法是不調用 ArrayList.remove() 方法，轉而調用 疊代器的 remove() 方法：
1 Iterator<String> it = list.iterator();
2 while(it.hasNext()){
3 String str = it.next();
4 System.out.print(str+" ");
5 //list.remove(str);//集合周遊時進行删除或者新增操作，都會抛出 ConcurrentModificationException 異常
6 it.remove();
7 } 注意：疊代器隻能向後周遊，不能向前周遊，能夠删除元素，但是不能新增元素。
③、疊代器的變種 forEach
1 ArrayList<String> list = new ArrayList<>();
2 list.add("a");
3 list.add("b");
4 list.add("c");
5 for(String str : list){
6 System.out.print(str + " ");
7 } 這種文法可以看成是 JDK 的一種文法糖，通過反編譯 class 檔案，我們可以看到生成的 java 檔案，其具體實作還是通過調用 Iterator 疊代器進行周遊的。如下：
1 ArrayList list = new ArrayList();
2 list.add("a");
3 list.add("b");
4 list.add("c");
5 String str;
6 for (Iterator iterator1 = list.iterator(); iterator1.hasNext(); System.out.print((new StringBuilder(String.valueOf(str))).append(" ").toString()))
7 str = (String)iterator1.next(); ④、疊代器 ListIterator
還是先看看具體用法：
1 ArrayList<String> list = new ArrayList<>();
2 list.add("a");
3 list.add("b");
4 list.add("c");
5 ListIterator<String> listIt = list.listIterator();
6
7 //向後周遊
8 while(listIt.hasNext()){
9 System.out.print(listIt.next()+" ");//a b c
10 }
11
12 //向後前周遊,此時由于上面進行了向後周遊，遊标已經指向了最後一個元素，是以此處向前周遊能有值
13 while(listIt.hasPrevious()){
14 System.out.print(listIt.previous()+" ");//c b a
15 } 還能一邊周遊，一邊進行新增或者删除操作：
1 ArrayList<String> list = new ArrayList<>();
2 list.add("a");
3 list.add("b");
4 list.add("c");
5 ListIterator<String> listIt = list.listIterator();
6
7 //向後周遊
8 while(listIt.hasNext()){
9 System.out.print(listIt.next()+" ");//a b c
10 listIt.add("1");//在每一個元素後面增加一個元素 "1"
11 }
12
13 //向後前周遊,此時由于上面進行了向後周遊，遊标已經指向了最後一個元素，是以此處向前周遊能有值
14 while(listIt.hasPrevious()){
15 System.out.print(listIt.previous()+" ");//1 c 1 b 1 a
16 } 也就是說相比于 Iterator 疊代器，這裡的 ListIterator 多出了能向前疊代，以及能夠新增元素。下面我們看看具體實作：
對于 Iterator 疊代器，我們檢視 JDK 源碼，發現還有 ListIterator 接口繼承了 Iterator:
public interface ListIterator<E> extends Iterator<E> 該接口有如下方法：
我們看在 ArrayList 類中，有如下方法可以獲得 ListIterator 接口：
public ListIterator<E> listIterator() {
return new ListItr(0);
} 這裡的 ListItr 也是一個内部類。
1 //注意 内部類 ListItr 繼承了另一個内部類 Itr
2 private class ListItr extends Itr implements ListIterator<E> {
3 ListItr(int index) {//構造函數，進行遊标初始化
4 super();
5 cursor = index;
6 }
7
8 public boolean hasPrevious() {//判斷是否有上一個元素
9 return cursor != 0;
10 }
11
12 public int nextIndex() {//傳回下一個元素的索引
13 return cursor;
14 }
15
16 public int previousIndex() {//傳回上一個元素的索引
17 return cursor - 1;
18 }
19
20 //該方法擷取目前索引的上一個元素
21 @SuppressWarnings("unchecked")
22 public E previous() {
23 checkForComodification();//疊代器進行元素疊代時同時進行增加和删除操作，會抛出異常
24 int i = cursor - 1;
25 if (i < 0)
26 throw new NoSuchElementException();
27 Object[] elementData = ArrayList.this.elementData;
28 if (i >= elementData.length)
29 throw new ConcurrentModificationException();
30 cursor = i;//遊标指向上一個元素
31 return (E) elementData[lastRet = i];//傳回上一個元素的值
32 }
33
34
35 public void set(E e) {
36 if (lastRet < 0)
37 throw new IllegalStateException();
38 checkForComodification();
39
40 try {
41 ArrayList.this.set(lastRet, e);
42 } catch (IndexOutOfBoundsException ex) {
43 throw new ConcurrentModificationException();
44 }
45 }
46
47 //相比于疊代器 Iterator ，這裡多了一個新增操作
48 public void add(E e) {
49 checkForComodification();
50
51 try {
52 int i = cursor;
53 ArrayList.this.add(i, e);
54 cursor = i + 1;
55 lastRet = -1;
56 expectedModCount = modCount;
57 } catch (IndexOutOfBoundsException ex) {
58 throw new ConcurrentModificationException();
59 }
60 }
61 } 9、SubList
在 ArrayList 中有這樣一個方法：
1 public List<E> subList(int fromIndex, int toIndex) {
2 subListRangeCheck(fromIndex, toIndex, size);
3 return new SubList(this, 0, fromIndex, toIndex);
4 } 作用是傳回從 fromIndex(包括) 開始的下标，到 toIndex(不包括) 結束的下标之間的元素視圖。如下：
1 ArrayList<String> list = new ArrayList<>();
2 list.add("a");
3 list.add("b");
4 list.add("c");
5
6 List<String> subList = list.subList(0, 1);
7 for(String str : subList){
8 System.out.print(str + " ");//a
9 } 這裡出現了 SubList 類，這也是 ArrayList 中的一個内部類。
注意：傳回的是原集合的視圖，也就是說，如果對 subList 出來的集合進行修改或新增操作，那麼原始集合也會發生同樣的操作。
1 ArrayList<String> list = new ArrayList<>();
2 list.add("a");
3 list.add("b");
4 list.add("c");
5
6 List<String> subList = list.subList(0, 1);
7 for(String str : subList){
8 System.out.print(str + " ");//a
9 }
10 subList.add("d");
11 System.out.println(subList.size());//2
12 System.out.println(list.size());//4,原始集合長度也增加了 想要獨立出來一個集合，解決辦法如下：
List<String> subList = new ArrayList<>(list.subList(0, 1)); 10、size()
public int size() {
return size;
} 注意：傳回集合的長度，而不是數組的長度，這裡的 size 就是定義的全局變量。
11、isEmpty()
1 public boolean isEmpty() {
2 return size == 0;
3 } 傳回 size == 0 的結果。
12、trimToSize()
1 public void trimToSize() {
2 modCount++;
3 if (size < elementData.length) {
4 elementData = Arrays.copyOf(elementData, size);
5 }
6 } 該方法用于回收多餘的記憶體。也就是說一旦我們确定集合不在添加多餘的元素之後，調用 trimToSize() 方法會将實作集合的數組大小剛好調整為集合元素的大小。
注意：該方法會花時間來複制數組元素，是以應該在确定不會添加元素之後在調用。
參考文檔：https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html#
作者：
YSOcean出處：
http://www.cnblogs.com/ysocean/本文版權歸作者所有，歡迎轉載，但未經作者同意不能轉載，否則保留追究法律責任的權利。