關於ArrayList的實現和原理，原文出處：http://www.cnblogs.com/ITtangtang/p/3948555.html
我覺得他寫的非常好，真的很好.
做一個記錄和總結吧
public class arraylist<E> {
/**
* 存放集合的元素
*
*/
private transient Object[] elementData;
/** 元素的大小 */
private int size;
定義了一個泛型類，一個object的數組和一個私有變量來記錄該集合的元素數量，原文多了一個私有變量，我也不知道干嘛用的，作者也沒解釋也沒提及到，我沒使用也沒事
1 /**
2 * 根據指定大小初始化
3 * @param initialCapacity
4 */
5 public arraylist(int initialCapacity){
6 super();
7 if(initialCapacity<=0){
8 //拋異常
9 throw new IllegalArgumentException("初始化參數不能小於0");
10 }else{
11 //初始化數組
12 this.elementData=new Object[initialCapacity];
13 }
14 }
15 /**
16 * 默認初始化
17 */
18 public arraylist(){
19 this(10);
20 }
21 /**
22 * 根據一個集合類初始化
23 * @param c 一個必須繼承了Collection接口的類
24 */
25 public arraylist(Collection<? extends E> c){
26 //初始化
27 elementData=c.toArray();
28 size=elementData.length;
29 //如果不是任意類型的數組就轉換Objec類型
30 if (elementData.getClass() != Object[].class){
31 elementData=Arrays.copyOf(elementData,size, Object[].class);
32 }
33 }
34
3個初始化方法，根據默認大小進行數組的初始化，給定大小初始化和傳遞一個繼承了Collection集合接口的類進行轉換賦值初始化
1 /**
2 * 擴容集合
3 * @param minCapacity
4 */
5 public void ensureCapacity(int minCapacity){
6 /** 當前數組的大小 */
7 int oldCapacity = elementData.length;
8 if (minCapacity > oldCapacity) {
9 /**
10 * oldData 雖然沒有被使用，但是這是關於內存管理的原因和Arrays.copyOf()方法不是線程安全
11 * oldData在if的生命周期內引用elementData這個變量，所以不會被GC回收掉
12 * 當Arrays.copyOf()方法在把elementData復制到newCapacity時，就可以防止新的內存或是其他線程分配內存是elementData內存被侵占修改
13 * 當結束是離開if，oldData周期就結束被回收
14 */
15 Object oldData[] = elementData;
16 int newCapacity = (oldCapacity * 3)/2 + 1; //增加50%+1
17 if (newCapacity < minCapacity)
18 newCapacity = minCapacity;
19 //使用Arrays.copyOf把集合的元素復制並生成一個新的數組
20 elementData = Arrays.copyOf(elementData, newCapacity);
21 }
22 }
這是一個核心的方法，集合的擴容，其實是對數組的擴容，minCapacity集合的大小，進行對比判斷是否應該進行擴容，使用了Arrays.copyOf()方法進行擴容，
原文有進行詳細的解釋，這個方法把第一個參數的內容復制到一個新的數組中，數組的大小是第二個參數，並返回一個新的數組，關於oldData的變量上文有詳細的注釋
1 /**
2 * 檢查索引是否出界
3 * @param index
4 */
5 private void RangeCheck(int index){
6 if(index > size || index < 0){
7 throw new IndexOutOfBoundsException("下標超出,Index: " + index + ", Size: " +size);
8 }
9 }
一個下標的檢索是否出 1 /**
2 * 添加元素
3 * 將指定的元素添加到集合的末尾
4 * @param e 添加的元素
5 * @return
6 */
7 public boolean add(E e){
8 ensureCapacity(size+1);
9 elementData[size]=e;
10 size++;
11 return true;
12 }
添加元素，先進行擴容，在賦值，然後元素加一，注意 size+1 字段size並沒有加一，這裡進行的是算術的運算，所以在後面才需要進行自增
1 /**
2 * 添加元素
3 * 將元素添加到指定的位置
4 * @param index 指定的索引下標
5 * @param element 元素
6 * @return
7 */
8 public boolean add(int index, E element){
9 RangeCheck(index);
10 ensureCapacity(size+1);
11 // 將 elementData中從Index位置開始、長度為size-index的元素，
12 // 拷貝到從下標為index+1位置開始的新的elementData數組中。
13 // 即將當前位於該位置的元素以及所有後續元素右移一個位置。
14 System.arraycopy(elementData, index, elementData, index+1, size-index);
15 elementData[index]=element;
16 size++;//元素加一
17 return true;
18 }
這裡不同的是 System.arraycopy(elementData, index, elementData, index+1, size-index);
這是一個c的內部方法，詳細的原文有解釋，這裡就不說了，這個也是整個ArrayList的核心所在，也Arrays.copyOf()的內部實現原理
1 /**
2 * 添加全部元素
3 * 按照指定collection的迭代器所返回的元素順序，將該collection中的所有元素添加到此列表的尾部。
4 * @param c
5 * @return
6 */
7 public boolean addAll(Collection < ? extends E>c){
8 Object[] newElement=c.toArray();
9 int elementLength=newElement.length;
10 ensureCapacity(size+elementLength);
11 //從newElement 0的下標開始，elementLength個元素，elementData size的下標
12 System.arraycopy(newElement, 0, elementData, size, elementLength);
13 size+=elementLength;
14 return elementLength!=0;
15 }
基本上其他方法都只是根據不同的情況進行不同的處理，比如通過接口把數據對象傳遞進來然後獲取長度進行擴容，在把數據使用System,arraycopy復制到新的數組中
1 /**
2 * 指定位置，添加全部元素
3 * @param index 插入位置的下標
4 * @param c 插入的元素集合
5 * @return
6 */
7 public boolean addAll(int index, Collection<? extends E> c){
8 if(index > size || index < 0){
9 throw new IndexOutOfBoundsException("Index: " + index + ", Size: " +size);
10 }
11 Object[] newElement=c.toArray();
12 int elementLength=newElement.length;
13 ensureCapacity(size+elementLength);
14 int numMoved=size-index;
15 //判斷插入的位置是否在數組中間
16 if(numMoved>0){
17 //把index插入位置的後面的所有元素往後移
18 //elementData index下標開始的numMoved個元素插入到elementData 的index+elementLength位置
19 System.arraycopy(elementData, index, elementData, index+elementLength, numMoved);
20 }
21 //把newElement裡從0開始的elementLength個元素添加到elementData index開始的位置
22 System.arraycopy(newElement, 0, elementData, index, elementLength);
23 size += elementLength;
24 return elementLength != 0;
25 }
26
27 /**
28 * 指定下標賦值
29 * @param index
30 * @param element
31 * @return
32 */
33 public E set(int index,E element){
34 RangeCheck(index);
35 E oldElement=(E)elementData[index];
36 elementData[index]=element;
37 return oldElement;
38 }
39
40 /**
41 * 根據下標取值
42 * @param index
43 * @return
44 */
45 public E get(int index){
46 RangeCheck(index);
47 return (E)elementData[index];
48 }
49
50 /**
51 * 根據下標移除元素
52 * @param index
53 */
54 public E remove(int index){
55 RangeCheck(index);
56 E oldElement=(E)elementData[index];
57 /** 移除的下標後面的元素數量 */
58 int numMoved=size-index-1;
59 //如果在數組范圍內就進行移動
60 if(numMoved>0)
61 System.arraycopy(elementData, index+1, elementData, index, numMoved);
62 //移除
63 elementData[--size]=null;
64 return oldElement;
65 }
66
67 /**
68 * 根據元素移除
69 * @param obj
70 * @return
71 */
72 public boolean remove(Object obj){
73 //Arraylist允許存放null,所以也要進行判斷處理
74 if(obj==null){
75 for(int index=0;index<size;index++){
76 if(elementData[index]==null){
77 remove(index);
78 return true;
79 }
80 }
81 }else{
82 for(int index=0;index<size;index++){
83 if(obj.equals(elementData[index])){
84 remove(index);
85 return true;
86 }
87 }
88 }
89 return false;
90 }
91
92 /**
93 * 根據下標移除指定范圍內的元素
94 * @param fromIndex 開始
95 * @param toIndex 結束
96 */
97 protected void removeRange(int fromIndex, int toIndex){
98 RangeCheck(fromIndex);
99 RangeCheck(toIndex);
100 //要移動的元素數
101 int numMoved = size - toIndex;
102 //把toIndex後面的元素移動到fromIndex
103 System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved);
104 //要移除的元素數量
105 int newSize=size-(toIndex-fromIndex);
106 while(size!=newSize){
107 elementData[--size]=null;
108 }
109 }
110
111 /**
112 * 把數組容量調整到實際的容量
113 */
114 public void trimToSize(){
115 int leng=elementData.length;
116 if(size<leng){
117 Object[] old=elementData;
118 elementData=Arrays.copyOf(elementData, size);
119 }
120 }
121 /**
122 * 把集合元素轉換成數組
123 * @return
124 */
125 public Object[] toArray(){
126 return Arrays.copyOf(elementData, size);
127 }
128
129 public <T>T[] toArray(T[] a){
130 if(a.length<size){
131 return (T[]) Arrays.copyOf(elementData,size, a.getClass());
132 }
133 //把集合元素復制到a數組中
134 System.arraycopy(elementData, 0, a, 0, size);
135 if (a.length > size){
136 for(int index=size;index<a.length;index++){
137 a[index] = null;
138 }
139 }
140 return a;
141 }
基本上都是對數組進行操作和使用c的方法進行賦值移動等，詳細的可以查看原文，原文中除了那個私有變量外也沒多少問題，代碼可以完美運行，這李要注意的和難點就會是System,arraycopy和Arrayist.copy()這2個方法
和在擴容方法裡oldData這個變量的使用，這個變量真的很好，一開始我也不知道為什麼要這麼使用，在原文的末尾會進行解釋。
