java集合類源碼分析之List（一）

　　首先分析一下集合與數組的區別：1.java中的數組一般用於存儲基本數據類型，而且是靜態的，即長度固定不變，這就不適用於元素個數未知的情況；2.集合只能用於存儲引用類型，並且長度可變，適用於大多數情況，可用toArray()方法轉換成數組。

java語言提供了多種集合類的介面，如List、Set、Map等。這裡首先從List開始分析，其實現類有ArrayList、LinkedList、Vector（Stack），下麵就從它們的源代碼開始：

1.ArrayList（數組列表）

顧名思義，這是一種以數組形式進行存儲的列表，所以其優點是便於隨機訪問，而在插入和刪除操作時效率較低。

• 構造方法（三種）：

1.public ArrayList(int initialCapacity)　　指定初始列表的容量，當容量不夠時會自動進行擴容

2.public ArrayList()　　空的構造方法

3.public ArrayList(Collection<? extends E> c)　　初始化列表元素，傳入參數為一個集合類的對象

1         ArrayList<String> arrayList1 = new ArrayList<String>(3);    //初始化ArrayList容量大小
2         arrayList1.add("A");
3         arrayList1.add("B");
4         arrayList1.add("C");
5         ArrayList<String> arrayList2 = new ArrayList<String>(arrayList1);    //初始化ArrayList元素
6         System.out.println(arrayList2);    //[A, B, C]

• 插入元素（add）

1.在列表尾部插入 add(E e)

1  public boolean add(E e) {
2         ensureCapacityInternal(size + 1);  // Increments modCount!!
3         elementData[size++] = e;
4         return true;
5     }

2.在列表指定位置插入 add(int index, E element)

1 public void add(int index, E element) {
2         rangeCheckForAdd(index);
3 
4         ensureCapacityInternal(size + 1);  // Increments modCount!!
5         System.arraycopy(elementData, index, elementData, index + 1,
6                          size - index);
7         elementData[index] = element;
8         size++;
9     }

3.在列表尾部插入一個子集 addAll(Collection<? extends E> c)

1     public boolean addAll(Collection<? extends E> c) {
2         Object[] a = c.toArray();
3         int numNew = a.length;
4         ensureCapacityInternal(size + numNew);  // Increments modCount
5         System.arraycopy(a, 0, elementData, size, numNew);
6         size += numNew;
7         return numNew != 0;
8     }

4.在列表的指定位置插入一個子集 addAll(int index, Collection<? extends E> c)

 1     public boolean addAll(int index, Collection<? extends E> c) {
 2         rangeCheckForAdd(index);
 3 
 4         Object[] a = c.toArray();
 5         int numNew = a.length;
 6         ensureCapacityInternal(size + numNew);  // Increments modCount
 7 
 8         int numMoved = size - index;
 9         if (numMoved > 0)
10             System.arraycopy(elementData, index, elementData, index + numNew,
11                              numMoved);
12 
13         System.arraycopy(a, 0, elementData, index, numNew);
14         size += numNew;
15         return numNew != 0;
16     }

觀察源碼可知，在指定位置插入元素其實是通過arraycopy()方法來實現的，即是將原數組複製到目標數組，因而效率較低。

應用示例：

1         ArrayList<String> arrayList1 = new ArrayList<String>(3);    //初始化ArrayList容量大小
2         arrayList1.add("A");
3         arrayList1.add("B");
4         arrayList1.add("C");
5         arrayList1.add("D");
6         System.out.println(arrayList1);    //[A, B, C, D]
7         arrayList1.add(0, "E");
8         System.out.println(arrayList1); //[E, A, B, C, D]

• 查找元素

1.查找指定位置的元素 get(int index)

2.查找指定元素的位置 indexOf(Object o)、lastIndexOf(Object o)

3.查找列表中是否包含指定元素 contains(Object o)

1  public boolean contains(Object o) {
2         return indexOf(o) >= 0;
3     }

由於ArrayList以數組方式實現，自帶索引，所以便於隨機查找。

• 修改元素

修改指定位置的元素 set(int index, E element)

1         ArrayList<String> arrayList1 = new ArrayList<String>(3);    //初始化ArrayList容量大小
2         arrayList1.add("A");
3         arrayList1.add("B");
4         arrayList1.add("C");
5         arrayList1.add("D");
6         System.out.println(arrayList1); //[A, B, C, D]
7         arrayList1.set(0, "X");
8         System.out.println(arrayList1); //[X, B, C, D]

由於ArrayList以數組方式實現，自帶索引，所以便於隨機修改。

• 刪除元素

1.刪除指定位置的元素 remove(int index)

 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)
 9             System.arraycopy(elementData, index+1, elementData, index,
10                              numMoved);
11         elementData[--size] = null; // clear to let GC do its work
12 
13         return oldValue;
14     }

2.刪除指定元素 remove(Object o)

 1     public boolean remove(Object o) {
 2         if (o == null) {
 3             for (int index = 0; index < size; index++)
 4                 if (elementData[index] == null) {
 5                     fastRemove(index);
 6                     return true;
 7                 }
 8         } else {
 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     }

3.清空列表 clear()

1     public void clear() {
2         modCount++;
3 
4         // clear to let GC do its work
5         for (int i = 0; i < size; i++)
6             elementData[i] = null;
7 
8         size = 0;
9     }

從源碼中我們可以知道，刪除元素時也是通過arraycopy()方法，將原數組複製到目標數組，因而效率較低。

應用示例：

 1         ArrayList<String> arrayList1 = new ArrayList<String>(3);    //初始化ArrayList容量大小
 2         arrayList1.add("A");
 3         arrayList1.add("B");
 4         arrayList1.add("C");
 5         arrayList1.add("D");
 6         arrayList1.remove(0);
 7         System.out.println(arrayList1);    //[B, C, D]
 8         arrayList1.remove("D");
 9         System.out.println(arrayList1);    //[B, C]
10         arrayList1.clear();
11         System.out.println(arrayList1.isEmpty());    //true