本節探討Java中的容器類ArrayList，它有哪些方法？內部是如何實現的？有什麼特點？與數組如何轉換？迭代是什麼？為什麼要有它？內部是如何實現的？有哪些易犯的錯誤？Collection/List/RandomAccess都用於什麼目的? ...
從本節開始，我們探討Java中的容器類，所謂容器，顧名思義就是容納其他數據的，電腦課程中有一門課叫數據結構，可以粗略對應於Java中的容器類，我們不會介紹所有數據結構的內容，但會介紹Java中的主要實現，並分析其基本原理和主要實現代碼。
前幾節在介紹泛型的時候，我們自己實現了一個簡單的動態數組容器類DynaArray，本節，我們介紹Java中真正的動態數組容器類ArrayList。
我們先來看它的基本用法。
基本用法
新建ArrayList
ArrayList是一個泛型容器，新建ArrayList需要實例化泛型參數，比如：
ArrayList<Integer> intList = new ArrayList<Integer>(); ArrayList<String> strList = new ArrayList<String>();
添加元素
add方法添加元素到末尾
ArrayList<Integer> intList = new ArrayList<Integer>(); intList.add(123); intList.add(456); ArrayList<String> strList = new ArrayList<String>(); strList.add("老馬"); strList.add("編程");
長度方法
判斷是否為空
public boolean isEmpty()
獲取長度
public int size()
訪問指定位置的元素
public E get(int index)
如：
ArrayList<String> strList = new ArrayList<String>(); strList.add("老馬"); strList.add("編程"); for(int i=0; i<strList.size(); i++){ System.out.println(strList.get(i)); }
查找元素
public int indexOf(Object o)
如果找到，返回索引位置，否則返回-1。
從後往前找
public int lastIndexOf(Object o)
是否包含指定元素
public boolean contains(Object o)
相同的依據是equals方法返回true。如果傳入的元素為null，則找null的元素。
刪除元素
刪除指定位置的元素
public E remove(int index)
返回值為被刪對象。
刪除指定對象
public boolean remove(Object o)
與indexOf一樣，比較的依據的是equals方法，如果o為null，則刪除值為null的元素。另外，remove只刪除第一個相同的對象，也就是說，即使ArrayList中有多個與o相同的元素，也只會刪除第一個。返回值為boolean類型，表示是否刪除了元素。
刪除所有元素
public void clear()
插入元素
在指定位置插入元素
public void add(int index, E element)
index為0表示插入最前面，index為ArrayList的長度表示插到最後面。
修改元素
修改指定位置的元素內容
public E set(int index, E element)
基本原理
內部組成
可以看出，ArrayList的基本用法是比較簡單的，它的基本原理也是比較簡單的，原理與我們在前面幾節介紹的DynaArray類似，內部有一個數組elementData，一般會有一些預留的空間，有一個整數size記錄實際的元素個數，如下所示：
private transient Object[] elementData; private int size;
我們暫時可以忽略transient這個關鍵字。各種public方法內部操作的基本都是這個數組和這個整數，elementData會隨著實際元素個數的增多而重新分配，而size則始終記錄實際的元素個數。
Add方法
雖然基本思路是簡單的，但內部代碼有一些比較晦澀，我們來看下add方法的代碼：
public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }
它首先調用ensureCapacityInternal確保數組容量是夠的，ensureCapacityInternal的代碼是：
private void ensureCapacityInternal(int minCapacity) { if (elementData == EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); }
它先判斷數組是不是空的，如果是空的，則首次至少要分配的大小為DEFAULT_CAPACITY，DEFAULT_CAPACITY的值為10，接下來調用ensureExplicitCapacity，代碼為：
private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); }
modCount++是什麼意思呢？modCount表示內部的修改次數，modCount++當然就是增加修改次數，為什麼要記錄修改次數呢？我們待會解釋。
如果需要的長度大於當前數組的長度，則調用grow方法。這段代碼前面有個註釋：overflow-conscious code，翻譯一下，大意就是代碼考慮了溢出這種情況，溢出是什麼意思呢？我們解釋下，假設a,b都是int，下麵兩行代碼是不一樣的：
1 if(a>b) 2 if(a-b>0)
為什麼呢？考慮a=Integer.MAX_VALUE, b=Integer.MIN_VALUE：
a>b為true
但由於溢出，a-b的結果為-1
反之，再考慮a=Integer.MIN_VALUE, b=Integer.MAX_VALUE:
a>b為false
但由於溢出，a-b的結果為1。
不過，在a, b都為正數且數值沒有那麼大的情況下，一般也沒有溢出問題，為便於理解，在後續的分析中，我們將忽略溢出問題。
接下來，看grow方法：
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); }
排除邊緣情況，長度增長的主要代碼為：
int newCapacity = oldCapacity + (oldCapacity >> 1);
右移一位相當於除2，所以，newCapacity相當於oldCapacity的1.5倍。
Remove方法
我們再來看Remove方法的代碼：
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; }
它也增加了modCount，然後計算要移動的元素個數，從index往後的元素都往前移動一位，實際調用System.arraycopy方法移動元素。elementData[--size] = null;這行代碼將size減一，同時將最後一個位置設為null，設為null後就不再引用原來對象，如果原來對象也不再被其他對象引用，就可以被垃圾回收。
基本原理小結
其他方法大多是比較簡單的，我們就不贅述了。總體而言，內部操作要考慮各種情況，代碼有一些晦澀複雜，但介面一般都是簡單直接的，這就是使用容器類的好處了，這也是電腦程式中的基本思維方式，封裝複雜操作，提供簡單介面。
迭代
foreach用法
理解了ArrayList的基本用法和原理，接下來，我們來看一個常見的操作 - 迭代，比如說，迴圈列印ArrayList中的每個元素，ArrayList支持foreach語法，比如：
ArrayList<Integer> intList = new ArrayList<Integer>(); intList.add(123); intList.add(456); intList.add(789); for(Integer a : intList){ System.out.println(a); }
當然，這種迴圈也可以使用如下代碼實現：
for(int i=0; i<intList.size(); i++){ System.out.println(intList.get(i)); }
不過，foreach看上去更為簡潔，而且，它適用於各種容器，更為通用。
這種foreach語法背後是怎麼實現的呢？其實，編譯器會將它轉換為類似如下代碼：
Iterator<Integer> it = intList.iterator(); while(it.hasNext()){ System.out.println(it.next()); }
接來下，我們解釋一下其中的代碼。
迭代器介面
ArrayList實現了Iterable介面，Iterable表示可迭代，它的定義為：
public interface Iterable<T> { Iterator<T> iterator(); }
定義很簡單，就是要求實現iterator方法。iterator方法的聲明為：
public Iterator<E> iterator()
它返回一個實現了Iterator介面的對象，Iterator介面的定義為：
public interface Iterator<E> { boolean hasNext(); E next(); void remove(); }
hasNext()判斷是否還有元素未訪問，next()返回下一個元素，remove()刪除最後返回的元素，只讀訪問的基本模式就類似於：
Iterator<Integer> it = intList.iterator(); while(it.hasNext()){ System.out.println(it.next()); }
我們待會再看迭代中間要刪除元素的情況。
只要對象實現了Iterable介面，就可以使用foreach語法，編譯器會轉換為調用Iterable和Iterator介面的方法。
初次見到Iterable和Iterator，可能會比較容易混淆，我們再澄清一下：
- Iterable表示對象可以被迭代，它有一個方法iterator()，返回Iterator對象，實際通過Iterator介面的方法進行遍歷。
- 如果對象實現了Iterable，就可以使用foreach語法。
- 類可以不實現Iterable，也可以創建Iterator對象。
ListIterator
除了iterator()，ArrayList還提供了兩個返回Iterator介面的方法：
public ListIterator<E> listIterator() public ListIterator<E> listIterator(int index)
ListIterator擴展了Iterator介面，增加了一些方法，向前遍歷、添加元素、修改元素、返回索引位置等，添加的方法有：
public interface ListIterator<E> extends Iterator<E> { boolean hasPrevious(); E previous(); int nextIndex(); int previousIndex(); void set(E e); void add(E e); }
listIterator()方法返回的迭代器從0開始，而listIterator(int index)方法返回的迭代器從指定位置index開始，比如，從末尾往前遍歷，代碼為：
public void reverseTraverse(List<Integer> list){ ListIterator<Integer> it = list.listIterator(list.size()); while(it.hasPrevious()){ System.out.println(it.previous()); } }
迭代的陷阱
關於迭代器，有一種常見的誤用，就是在迭代的中間調用容器的刪除方法，比如要刪除一個整數ArrayList中所有小於100的數，直覺上，代碼可以這麼寫：
public void remove(ArrayList<Integer> list){ for(Integer a : list){ if(a<=100){ list.remove(a); } } }
但，運行時會拋出異常：
java.util.ConcurrentModificationException
發生了併發修改異常，為什麼呢？迭代器內部會維護一些索引位置相關的數據，要求在迭代過程中，容器不能發生結構性變化，否則這些索引位置就失效了。所謂結構性變化就是添加、插入和刪除元素，只是修改元素內容不算結構性變化。
如何避免異常呢？可以使用迭代器的remove方法，如下所示：
public static void remove(ArrayList<Integer> list){ Iterator<Integer> it = list.iterator(); while(it.hasNext()){ if(it.next()<=100){ it.remove(); } } }
迭代器如何知道發生了結構性變化，並拋出異常？它自己的remove方法為何又可以使用呢？我們需要看下迭代器的工作原理。
迭代器實現的原理
我們來看下ArrayList中iterator方法的實現，代碼為：
public Iterator<E> iterator() { return new Itr(); }
新建了一個Itr對象，Itr是一個成員內部類，實現了Iterator介面，聲明為：
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;
cursor表示下一個要返回的元素位置，lastRet表示最後一個返回的索引位置，expectedModCount表示期望的修改次數，初始化為外部類當前的修改次數modCount，回顧一下，成員內部類可以直接訪問外部類的實例變數。
每次發生結構性變化的時候modCount都會增加，而每次迭代器操作的時候都會檢查expectedModCount是否與modCount相同，這樣就能檢測出結構性變化。
我們來具體看下，它是如何實現Iterator介面中的每個方法的，先看hasNext()，代碼為：
public boolean hasNext() { return cursor != size; }
cursor與size比較，比較直接，看next()方法：
public E next() { checkForComodification(); int i = cursor; if (i >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i + 1; return (E) elementData[lastRet = i]; }
首先調用了checkForComodification，它的代碼為：
final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); }
所以，next()前面部分主要就是在檢查是否發生了結構性變化，如果沒有變化，就更新cursor和lastRet的值，以保持其語義，然後返回對應的元素。
remove的代碼為：
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(); } }
它調用了ArrayList的remove方法，但同時更新了cursor, lastRet和expectedModCount的值，所以它可以正確刪除。
不過，需要註意的是，調用remove方法前必須先調用next，比如，通過迭代器刪除所有元素，直覺上，可以這麼寫：
public static void removeAll(ArrayList<Integer> list){ Iterator<Integer> it = list.iterator(); while(it.hasNext()){ it.remove(); } }
實際運行，會拋出異常：
java.lang.IllegalStateException
正確寫法是：
public static void removeAll(ArrayList<Integer> list){ Iterator<Integer> it = list.iterator(); while(it.hasNext()){ it.next(); it.remove(); } }
當然，如果只是要刪除所有元素，ArrayList有現成的方法clear()。
listIterator()的實現使用了另一個內部類ListItr，它繼承自Itr，基本思路類似，我們就不贅述了。
迭代器的好處
為什麼要通過迭代器這種方式訪問元素呢？直接使用size()/get(index)語法不也可以嗎？在一些場景下，確實沒有什麼差別，兩者都可以。不過，foreach語法更為簡潔一些，更重要的是，迭代器語法更為通用，它適用於各種容器類。
此外，迭代器表示的是一種關註點分離的思想，將數據的實際組織方式與數據的迭代遍歷相分離，是一種常見的設計模式。需要訪問容器元素的代碼只需要一個Iterator介面的引用，不需要關註數據的實際組織方式，可以使用一致和統一的方式進行訪問。
而提供Iterator介面的代碼瞭解數據的組織方式，可以提供高效的實現。在ArrayList中, size/get(index)語法與迭代器性能是差不多的，但在後續介紹的其他容器中，則不一定，比如LinkedList，迭代器性能就要高很多。
從封裝的思路上講，迭代器封裝了各種數據組織方式的迭代操作，提供了簡單和一致的介面。
ArrayList實現的介面
Java的各種容器類有一些共性的操作，這些共性以介面的方式體現，我們剛剛介紹的Iterable介面就是，此外，ArrayList還實現了三個主要的介面Collection, List和RandomAccess，我們逐個來看下。
Collection
Collection表示一個數據集合，數據間沒有位置或順序的概念，介面定義為：
public interface Collection<E> extends Iterable<E> { int size(); boolean isEmpty(); boolean contains(Object o); Iterator<E> iterator(); Object[] toArray(); <T> T[] toArray(T[] a); boolean add(E e); boolean remove(Object o); boolean containsAll(Collection<?> c); boolean addAll(Collection<? extends E> c); boolean removeAll(Collection<?> c); boolean retainAll(Collection<?> c); void clear(); boolean equals(Object o); int hashCode(); }
這些方法中，除了兩個toArray方法和幾個xxxAll()方法外，其他我們已經介紹過了。
這幾個xxxAll()方法的含義基本也是可以顧名思義的，addAll添加，removeAll刪除，containsAll檢查是否包含了參數容器中的所有元素，只有全包含才返回true，retainAll只保留參數容器中的元素，其他元素會進行刪除。
有一個抽象類AbstractCollection對這幾個方法都提供了預設實現，實現的方式就是利用迭代器方法逐個操作，比如說，我們看removeAll方法，代碼為：
public boolean removeAll(Collection<?> c) { boolean modified = false; Iterator<?> it = iterator(); while (it.hasNext()) { if (c.contains(it.next())) { it.remove(); modified = true; } } return modified; }
代碼比較簡單，就不解釋了。ArrayList繼承了AbstractList，而AbstractList又繼承了AbstractCollection，ArrayList對其中一些方法進行了重寫，以提供更為高效的實現，具體我們就不介紹了。
關於toArray方法，我們待會再介紹。
List
List表示有順序或位置的數據集合，它擴展了Collection，增加的主要方法有：
boolean addAll(int index, Collection<? extends E> c); E get(int index); E set(int index, E element); void add(int index, E element); E remove(int index); int indexOf(Object o); int lastIndexOf(Object o); ListIterator<E> listIterator(); ListIterator<E> listIterator(int index); List<E> subList(int fromIndex, int toIndex);
這些方法都與位置有關，容易理解，就不介紹了。
RandomAccess
RandomAccess的定義為：
public interface RandomAccess { }
沒有定義任何代碼。這有什麼用呢？這種沒有任何代碼的介面在Java中被稱之為標記介面，用於聲明類的一種屬性。
這裡，實現了RandomAccess介面的類表示可以隨機訪問，可隨機訪問就是具備類似數組那樣的特性，數據在記憶體是連續存放的，根據索引值就可以直接定位到具體的元素，訪問效率很高。下節我們會介紹LinkedList，它就不能隨機訪問。
有沒有聲明RandomAccess有什麼關係呢？主要用於一些通用的演算法代碼中，它可以根據這個聲明而選擇效率更高的實現。比如說，Collections類中有一個方法binarySearch，在List中進行二分查找，它的實現代碼就根據list是否實現了RandomAccess而採用不同的實現機制，如下所示：
public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) { if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD) return Collections.indexedBinarySearch(list, key); else return Collections.iteratorBinarySearch(list, key); }
ArrayList的其他方法
構造方法
ArrayList還有兩個構造方法
public ArrayList(int initialCapacity) public ArrayList(Collection<? extends E> c)
第一個方法以指定的大小initialCapacity初始化內部的數組大小，代碼為：
this.elementData = new Object[initialCapacity];
在事先知道元素長度的情況下，或者，預先知道長度上限的情況下，使用這個構造方法可以避免重新分配和拷貝數組。
第二個構造方法以一個已有的Collection構建，數據會新拷貝一份。
與數組的相互轉換
ArrayList中有兩個方法可以返回數組
public Object[] toArray() public <T> T[] toArray(T[] a)
第一個方法返回是Object數組，代碼為：
public Object[] toArray() { return Arrays.copyOf(elementData, size); }
第二個方法返回對應類型的數組，如果參數數組長度足以容納所有元素，就使用該數組，否則就新建一個數組，比如：
ArrayList<Integer> intList = new ArrayList<Integer>(); intList.add(123); intList.add(456); intList.add(789); Integer[] arrA = new Integer[3]; intList.toArray(arrA); Integer[] arrB = intList.toArray(new Integer[0]); System.out.println(Arrays.equals(arrA, arrB));
輸出為true，表示兩種方式都是可以的。
Arrays中有一個靜態方法asList可以返回對應的List，如下所示：
Integer[] a = {1,2,3};
List<Integer> list = Arrays.asList(a);
需要註意的是，這個方法返回的List，它的實現類並不是本節介紹的ArrayList，而是Arrays類的一個內部類，在這個內部類的實現中，內部用的的數組就是傳入的數組，沒有拷貝，也不會動態改變大小，所以對數組的修改也會反映到List中，對List調用add/remove方法會拋出異常。
要使用ArrayList完整的方法，應該新建一個ArrayList，如下所示：
List<Integer> list = new ArrayList<Integer>(Arrays.asList(a));
容量大小控制
ArrayList還提供了兩個public方法，可以控制內部使用的數組大小，一個是：
public void ensureCapacity(int minCapacity)
它可以確保數組的大小至少為minCapacity，如果不夠，會進行擴展。如果已經預知ArrayList需要比較大的容量，調用這個方法可以減少ArrayList內部分配和擴展的次數。
另一個方法是：
public void trimToSize()
它會重新分配一個數組，大小剛好為實際內容的長度。調用這個方法可以節省數組占用的空間。
ArrayList特點分析
後續我們會介紹各種容器類和數據組織方式，之所以有各種不同的方式，是因為不同方式有不同特點，而不同特點有不同適用場合。考慮特點時，性能是其中一個很重要的部分，但性能不是一個簡單的高低之分，對於一種數據結構，有的操作性能高，有的操作性能可能就比較低。
作為程式員，就是要理解每種數據結構的特點，根據場合的不同，選擇不同的數據結構。
對於ArrayList，它的特點是：內部採用動態數組實現，這決定了：
- 可以隨機訪問，按照索引位置進行訪問效率很高，用演算法描述中的術語，效率是O(1)，簡單說就是可以一步到位。
- 除非數組已排序，否則按照內容查找元素效率比較低，具體是O(N)，N為數組內容長度，也就是說，性能與數組長度成正比。
- 添加元素的效率還可以，重新分配和拷貝數組的開銷被平攤了，具體來說，添加N個元素的效率為O(N)。
- 插入和刪除元素的效率比較低，因為需要移動元素，具體為O(N)。
小結
本文詳細介紹了ArrayList，ArrayList是日常開發中最常用的類之一。我們介紹了ArrayList的用法、基本實現原理、迭代器及其實現、Collection/List/RandomAccess介面、ArrayList與數組的相互轉換，最後我們分析了ArrayList的特點。
ArrayList的插入和刪除的性能比較低，下一節，我們來看另一個同樣實現了List介面的容器類，LinkedList，它的特點可以說與ArrayList正好相反。
----------------
未完待續，查看最新文章，敬請關註微信公眾號“老馬說編程”(掃描下方二維碼)，從入門到高級，深入淺出，老馬和你一起探索Java編程及電腦技術的本質。用心原創，保留所有版權。
