一、 ArrayList概述：
ArrayList是基于數組實作的，是一個動态數組，其容量能自動增長，類似于C語言中的動态申請記憶體，動态增長記憶體。
ArrayList不是線程安全的，隻能用在單線程環境下，多線程環境下可以考慮用Collections.synchronizedList(List l)函數傳回一個線程安全的ArrayList類，也可以使用concurrent并發包下的CopyOnWriteArrayList類。
ArrayList實作了Serializable接口，是以它支援序列化，能夠通過序列化傳輸，實作了RandomAccess接口，支援快速随機通路，實際上就是通過下标序号進行快速通路，實作了Cloneable接口，能被克隆。
每個ArrayList執行個體都有一個容量，該容量是指用來存儲清單元素的數組的大小。它總是至少等于清單的大小。随着向ArrayList中不斷添加元素，其容量也自動增長。自動增長會帶來資料向新數組的重新拷貝，是以，如果可預知資料量的多少，可在構造ArrayList時指定其容量。在添加大量元素前，應用程式也可以使用ensureCapacity操作來增加ArrayList執行個體的容量，這可以減少遞增式再配置設定的數量。
注意，此實作不是同步的。如果多個線程同時通路一個ArrayList執行個體，而其中至少一個線程從結構上修改了清單，那麼它必須保持外部同步。
二、 ArrayList的實作：
對于ArrayList而言，它實作List接口、底層使用數組儲存所有元素。其操作基本上是對數組的操作。下面我們來分析ArrayList的源代碼：
1) 私有屬性：
ArrayList定義隻定義類兩個私有屬性：
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer.
*/
private transient Object[] elementData;
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size; 很容易了解，elementData存儲ArrayList内的元素，size表示它包含的元素的數量。
有個關鍵字需要解釋：transient。
transient。
有點抽象，看個例子應該能明白。
public class UserInfo implements Serializable {
private static final long serialVersionUID = 996890129747019948L;
private String name;
private transient String psw;
public UserInfo(String name, String psw) {
this.name = name;
this.psw = psw;
}
public String toString() {
return "name=" + name + ", psw=" + psw;
}
}
public class TestTransient {
public static void main(String[] args) {
UserInfo userInfo = new UserInfo("張三", "123456");
System.out.println(userInfo);
try {
// 序列化，被設定為transient的屬性沒有被序列化
ObjectOutputStream o = new ObjectOutputStream(new FileOutputStream(
"UserInfo.out"));
o.writeObject(userInfo);
o.close();
} catch (Exception e) {
// TODO: handle exception
e.printStackTrace();
}
try {
// 重新讀取内容
ObjectInputStream in = new ObjectInputStream(new FileInputStream(
"UserInfo.out"));
UserInfo readUserInfo = (UserInfo) in.readObject();
//讀取後psw的内容為null
System.out.println(readUserInfo.toString());
} catch (Exception e) {
// TODO: handle exception
e.printStackTrace();
}
}
} 被标記為transient的屬性在對象被序列化的時候不會被儲存。
接着回到ArrayList的分析中......
2) 構造方法：
ArrayList提供了三種方式的構造器，可以構造一個預設初始容量為10的空清單、構造一個指定初始容量的空清單以及構造一個包含指定collection的元素的清單，這些元素按照該collection的疊代器傳回它們的順序排列的。
// ArrayList帶容量大小的構造函數。
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
// 建立一個數組
this.elementData = new Object[initialCapacity];
}
// ArrayList無參構造函數。預設容量是10。
public ArrayList() {
this(10);
}
// 建立一個包含collection的ArrayList
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} 3) 元素存儲：
ArrayList提供了set(int index, E element)、add(E e)、add(int index, E element)、addAll(Collection<? extends E> c)、addAll(int index, Collection<? extends E> c)這些添加元素的方法。下面我們一一講解：
20 // 用指定的元素替代此清單中指定位置上的元素，并傳回以前位于該位置上的元素。
21 public E set(int index, E element) {
22 RangeCheck(index);
23
24 E oldValue = (E) elementData[index];
25 elementData[index] = element;
26 return oldValue;
27 }
28 // 将指定的元素添加到此清單的尾部。
29 public boolean add(E e) {
30 ensureCapacity(size + 1);
31 elementData[size++] = e;
32 return true;
33 }
34 // 将指定的元素插入此清單中的指定位置。
35 // 如果目前位置有元素，則向右移動目前位于該位置的元素以及所有後續元素（将其索引加1）。
36 public void add(int index, E element) {
37 if (index > size || index < 0)
38 throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
39 // 如果數組長度不足，将進行擴容。
40 ensureCapacity(size+1); // Increments modCount!!
41 // 将 elementData中從Index位置開始、長度為size-index的元素，
42 // 拷貝到從下标為index+1位置開始的新的elementData數組中。
43 // 即将目前位于該位置的元素以及所有後續元素右移一個位置。
44 System.arraycopy(elementData, index, elementData, index + 1, size - index);
45 elementData[index] = element;
46 size++;
47 }
48 // 按照指定collection的疊代器所傳回的元素順序，将該collection中的所有元素添加到此清單的尾部。
49 public boolean addAll(Collection<? extends E> c) {
50 Object[] a = c.toArray();
51 int numNew = a.length;
52 ensureCapacity(size + numNew); // Increments modCount
53 System.arraycopy(a, 0, elementData, size, numNew);
54 size += numNew;
55 return numNew != 0;
56 }
57 // 從指定的位置開始，将指定collection中的所有元素插入到此清單中。
58 public boolean addAll(int index, Collection<? extends E> c) {
59 if (index > size || index < 0)
60 throw new IndexOutOfBoundsException(
61 "Index: " + index + ", Size: " + size);
62
63 Object[] a = c.toArray();
64 int numNew = a.length;
65 ensureCapacity(size + numNew); // Increments modCount
66
67 int numMoved = size - index;
68 if (numMoved > 0)
69 System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
70
71 System.arraycopy(a, 0, elementData, index, numNew);
72 size += numNew;
73 return numNew != 0;
} 書上都說ArrayList是基于數組實作的，屬性中也看到了數組，具體是怎麼實作的呢？比如就這個添加元素的方法，如果數組大，則在将某個位置的值設定為指定元素即可，如果數組容量不夠了呢？
看到add(E e)中先調用了ensureCapacity(size+1)方法，之後将元素的索引賦給elementData[size]，而後size自增。例如初次添加時，size為0，add将elementData[0]指派為e，然後size設定為1（類似執行以下兩條語句elementData[0]=e;size=1）。将元素的索引賦給elementData[size]不是會出現數組越界的情況嗎？這裡關鍵就在ensureCapacity(size+1)中了。
// 傳回此清單中指定位置上的元素。
public E get(int index) {
RangeCheck(index);
return (E) elementData[index];
} 5) 元素删除：
ArrayList提供了根據下标或者指定對象兩種方式的删除功能。如下：
romove(int index):
1 // 移除此清單中指定位置上的元素。
2 public E remove(int index) {
3 RangeCheck(index);
4
5 modCount++;
6 E oldValue = (E) elementData[index];
7
8 int numMoved = size - index - 1;
9 if (numMoved > 0)
10 System.arraycopy(elementData, index+1, elementData, index, numMoved);
11 elementData[--size] = null; // Let gc do its work
12
13 return oldValue;
14 } 首先是檢查範圍，修改modCount，保留将要被移除的元素，将移除位置之後的元素向前挪動一個位置，将list末尾元素置空（null），傳回被移除的元素。
remove(Object o)
1 // 移除此清單中首次出現的指定元素（如果存在）。這是應為ArrayList中允許存放重複的元素。
2 public boolean remove(Object o) {
3 // 由于ArrayList中允許存放null，是以下面通過兩種情況來分别處理。
4 if (o == null) {
5 for (int index = 0; index < size; index++)
6 if (elementData[index] == null) {
7 // 類似remove(int index)，移除清單中指定位置上的元素。
8 fastRemove(index);
9 return true;
10 }
11 } else {
12 for (int index = 0; index < size; index++)
13 if (o.equals(elementData[index])) {
14 fastRemove(index);
15 return true;
16 }
17 }
18 return false;
19 }
20 } 首先通過代碼可以看到，當移除成功後傳回true，否則傳回false。remove(Object o)中通過周遊element尋找是否存在傳入對象，一旦找到就調用fastRemove移除對象。為什麼找到了元素就知道了index，不通過remove(index)來移除元素呢？因為fastRemove跳過了判斷邊界的處理，因為找到元素就相當于确定了index不會超過邊界，而且fastRemove并不傳回被移除的元素。下面是fastRemove的代碼，基本和remove(index)一緻。
1 private void fastRemove(int index) {
2 modCount++;
3 int numMoved = size - index - 1;
4 if (numMoved > 0)
5 System.arraycopy(elementData, index+1, elementData, index,
6 numMoved);
7 elementData[--size] = null; // Let gc do its work
8 } removeRange(int fromIndex,int toIndex)
1 protected void removeRange(int fromIndex, int toIndex) {
2 modCount++;
3 int numMoved = size - toIndex;
4 System.arraycopy(elementData, toIndex, elementData, fromIndex,
5 numMoved);
6
7 // Let gc do its work
8 int newSize = size - (toIndex-fromIndex);
9 while (size != newSize)
10 elementData[--size] = null;
11 } 執行過程是将elementData從toIndex位置開始的元素向前移動到fromIndex，然後将toIndex位置之後的元素全部置空順便修改size。
這個方法是protected，及受保護的方法，為什麼這個方法被定義為protected呢？
這是一個解釋，但是可能不容易看明白。http://stackoverflow.com/questions/2289183/why-is-javas-abstractlists-removerange-method-protected
先看下面這個例子
ArrayList<Integer> ints = new ArrayList<Integer>(Arrays.asList(0, 1, 2,
3, 4, 5, 6));
// fromIndex low endpoint (inclusive) of the subList
// toIndex high endpoint (exclusive) of the subList
ints.subList(2, 4).clear();
System.out.println(ints); 輸出結果是[0, 1, 4, 5, 6]，結果是不是像調用了removeRange(int fromIndex,int toIndex)！哈哈哈，就是這樣的。但是為什麼效果相同呢？是不是調用了removeRange(int fromIndex,int toIndex)呢？
6) 調整數組容量ensureCapacity：
從上面介紹的向ArrayList中存儲元素的代碼中，我們看到，每當向數組中添加元素時，都要去檢查添加後元素的個數是否會超出目前數組的長度，如果超出，數組将會進行擴容，以滿足添加資料的需求。數組擴容通過一個公開的方法ensureCapacity(int minCapacity)來實作。在實際添加大量元素前，我也可以使用ensureCapacity來手動增加ArrayList執行個體的容量，以減少遞增式再配置設定的數量。
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1; //增加50%+1
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
} 從上述代碼中可以看出，數組進行擴容時，會将老數組中的元素重新拷貝一份到新的數組中，每次數組容量的增長大約是其原容量的1.5倍。這種操作的代價是很高的，是以在實際使用時，我們應該盡量避免數組容量的擴張。當我們可預知要儲存的元素的多少時，要在構造ArrayList執行個體時，就指定其容量，以避免數組擴容的發生。或者根據實際需求，通過調用ensureCapacity方法來手動增加ArrayList執行個體的容量。
Object oldData[] = elementData;//為什麼要用到oldData[]
乍一看來後面并沒有用到關于oldData， 這句話顯得多此一舉！但是這是一個牽涉到記憶體管理的類， 是以要了解内部的問題。 而且為什麼這一句還在if的内部，這跟elementData = Arrays.copyOf(elementData, newCapacity); 這句是有關系的，下面這句Arrays.copyOf的實作時新建立了newCapacity大小的記憶體，然後把老的elementData放入。好像也沒有用到oldData，有什麼問題呢。問題就在于舊的記憶體的引用是elementData， elementData指向了新的記憶體塊，如果有一個局部變量oldData變量引用舊的記憶體塊的話，在copy的過程中就會比較安全，因為這樣證明這塊老的記憶體依然有引用，配置設定記憶體的時候就不會被侵占掉，然後copy完成後這個局部變量的生命期也過去了，然後釋放才是安全的。不然在copy的的時候萬一新的記憶體或其他線程的配置設定記憶體侵占了這塊老的記憶體，而copy還沒有結束，這将是個嚴重的事情。
關于ArrayList和Vector差別如下：
- ArrayList在記憶體不夠時預設是擴充50% + 1個，Vector是預設擴充1倍。
- Vector提供indexOf(obj, start)接口，ArrayList沒有。
- Vector屬于線程安全級别的，但是大多數情況下不使用Vector，因為線程安全需要更大的系統開銷。
ArrayList還給我們提供了将底層數組的容量調整為目前清單儲存的實際元素的大小的功能。它可以通過trimToSize方法來實作。代碼如下：
127 public void trimToSize() {
128 modCount++;
129 int oldCapacity = elementData.length;
130 if (size < oldCapacity) {
131 elementData = Arrays.copyOf(elementData, size);
132 }
} 由于elementData的長度會被拓展，size标記的是其中包含的元素的個數。是以會出現size很小但elementData.length很大的情況，将出現空間的浪費。trimToSize将傳回一個新的數組給elementData，元素内容保持不變，length和size相同，節省空間。
7)轉為靜态數組toArray
4、注意ArrayList的兩個轉化為靜态數組的toArray方法。
第一個， 調用Arrays.copyOf将傳回一個數組，數組内容是size個elementData的元素，即拷貝elementData從0至size-1位置的元素到新數組并傳回。
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
} 第二個，如果傳入數組的長度小于size，傳回一個新的數組，大小為size，類型與傳入數組相同。所傳入數組長度與size相等，則将elementData複制到傳入數組中并傳回傳入的數組。若傳入數組長度大于size，除了複制elementData外，還将把傳回數組的第size個元素置為空。
public <T> T[] toArray(T[] a) {
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
} Fail-Fast機制：
ArrayList也采用了快速失敗的機制，通過記錄modCount參數來實作。在面對并發的修改時，疊代器很快就會完全失敗，而不是冒着在将來某個不确定時間發生任意不确定行為的風險。具體介紹請參考這篇文章深入Java集合學習系列：HashMap的實作原理 中的Fail-Fast機制。
總結:
關于ArrayList的源碼，給出幾點比較重要的總結：
1、注意其三個不同的構造方法。無參構造方法構造的ArrayList的容量預設為10，帶有Collection參數的構造方法，将Collection轉化為數組賦給ArrayList的實作數組elementData。
2、注意擴充容量的方法ensureCapacity。ArrayList在每次增加元素（可能是1個，也可能是一組）時，都要調用該方法來確定足夠的容量。當容量不足以容納目前的元素個數時，就設定新的容量為舊的容量的1.5倍加1，如果設定後的新容量還不夠，則直接新容量設定為傳入的參數（也就是所需的容量），而後用Arrays.copyof()方法将元素拷貝到新的數組（詳見下面的第3點）。從中可以看出，當容量不夠時，每次增加元素，都要将原來的元素拷貝到一個新的數組中，非常之耗時，也是以建議在事先能确定元素數量的情況下，才使用ArrayList，否則建議使用LinkedList。
3、ArrayList的實作中大量地調用了Arrays.copyof()和System.arraycopy()方法。我們有必要對這兩個方法的實作做下深入的了解。
首先來看Arrays.copyof()方法。它有很多個重載的方法，但實作思路都是一樣的，我們來看泛型版本的源碼：
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
} 很明顯調用了另一個copyof方法，該方法有三個參數，最後一個參數指明要轉換的資料的類型，其源碼如下：
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
} 這裡可以很明顯地看出，該方法實際上是在其内部又建立了一個長度為newlength的數組，調用System.arraycopy()方法，将原來數組中的元素複制到了新的數組中。
下面來看System.arraycopy()方法。該方法被标記了native，調用了系統的C/C++代碼，在JDK中是看不到的，但在openJDK中可以看到其源碼。該函數實際上最終調用了C語言的memmove()函數，是以它可以保證同一個數組内元素的正确複制和移動，比一般的複制方法的實作效率要高很多，很适合用來批量處理數組。Java強烈推薦在複制大量數組元素時用該方法，以取得更高的效率。
![資料結構之 數組資料結構之 數組[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)