第1部分 List概括
List的框架圖
List 是一個接口，它繼承于Collection的接口。它代表著有序的隊列。
AbstractList 是一個抽象類，它繼承于AbstractCollection。AbstractList實現(xiàn)List接口中除size()、get(int location)之外的函數(shù)。
AbstractSequentialList 是一個抽象類，它繼承于AbstractList。AbstractSequentialList 實現(xiàn)了“鏈表中，根據(jù)index索引值操作鏈表的全部函數(shù)”。
ArrayList, LinkedList, Vector, Stack是List的4個實現(xiàn)類。
ArrayList 是一個數(shù)組隊列，相當(dāng)于動態(tài)數(shù)組。它由數(shù)組實現(xiàn)，隨機訪問效率高，隨機插入、隨機刪除效率低。
LinkedList 是一個雙向鏈表。它也可以被當(dāng)作堆棧、隊列或雙端隊列進行操作。LinkedList隨機訪問效率低，但隨機插入、隨機刪除效率低。
Vector 是矢量隊列，和ArrayList一樣，它也是一個動態(tài)數(shù)組，由數(shù)組實現(xiàn)。但是ArrayList是非線程安全的，而Vector是線程安全的。
Stack 是棧，它繼承于Vector。它的特性是：先進后出(FILO, First In Last Out)。
第2部分 List使用場景
學(xué)東西的最終目的是為了能夠理解、使用它。下面先概括的說明一下各個List的使用場景，后面再分析原因。
如果涉及到“棧”、“隊列”、“鏈表”等操作，應(yīng)該考慮用List，具體的選擇哪個List，根據(jù)下面的標(biāo)準(zhǔn)來取舍。
(01) 對于需要快速插入，刪除元素，應(yīng)該使用LinkedList。
(02) 對于需要快速隨機訪問元素，應(yīng)該使用ArrayList。
(03)
對于“單線程環(huán)境” 或者 “多線程環(huán)境，但List僅僅只會被單個線程操作”，此時應(yīng)該使用非同步的類(如ArrayList)。
對于“多線程環(huán)境，且List可能同時被多個線程操作”，此時，應(yīng)該使用同步的類(如Vector)。
通過下面的測試程序，我們來驗證上面的(01)和(02)結(jié)論。參考代碼如下：
import java.util.*;
import java.lang.Class;
/*
* @desc 對比ArrayList和LinkedList的插入、隨機讀取效率、刪除的效率
*
* @author skywang
*/
public class ListCompareTest {
private static final int COUNT = 100000;
private static LinkedList linkedList = new LinkedList();
private static ArrayList arrayList = new ArrayList();
private static Vector vector = new Vector();
private static Stack stack = new Stack();
public static void main(String[] args) {
// 換行符
System.out.println();
// 插入
insertByPosition(stack) ;
insertByPosition(vector) ;
insertByPosition(linkedList) ;
insertByPosition(arrayList) ;
// 換行符
System.out.println();
// 隨機讀取
readByPosition(stack);
readByPosition(vector);
readByPosition(linkedList);
readByPosition(arrayList);
// 換行符
System.out.println();
// 刪除
deleteByPosition(stack);
deleteByPosition(vector);
deleteByPosition(linkedList);
deleteByPosition(arrayList);
}
// 獲取list的名稱
private static String getListName(List list) {
if (list instanceof LinkedList) {
return "LinkedList";
} else if (list instanceof ArrayList) {
return "ArrayList";
} else if (list instanceof Stack) {
return "Stack";
} else if (list instanceof Vector) {
return "Vector";
} else {
return "List";
}
}
// 向list的指定位置插入COUNT個元素，并統(tǒng)計時間
private static void insertByPosition(List list) {
long startTime = System.currentTimeMillis();
// 向list的位置0插入COUNT個數(shù)
for (int i=0; i<COUNT; i++)
list.add(0, i);
long endTime = System.currentTimeMillis();
long interval = endTime - startTime;
System.out.println(getListName(list) + " : insert "+COUNT+" elements into the 1st position use time：" + interval+" ms");
}
// 從list的指定位置刪除COUNT個元素，并統(tǒng)計時間
private static void deleteByPosition(List list) {
long startTime = System.currentTimeMillis();
// 刪除list第一個位置元素
for (int i=0; i<COUNT; i++)
list.remove(0);
long endTime = System.currentTimeMillis();
long interval = endTime - startTime;
System.out.println(getListName(list) + " : delete "+COUNT+" elements from the 1st position use time：" + interval+" ms");
}
// 根據(jù)position，不斷從list中讀取元素，并統(tǒng)計時間
private static void readByPosition(List list) {
long startTime = System.currentTimeMillis();
// 讀取list元素
for (int i=0; i<COUNT; i++)
list.get(i);
long endTime = System.currentTimeMillis();
long interval = endTime - startTime;
System.out.println(getListName(list) + " : read "+COUNT+" elements by position use time：" + interval+" ms");
}
}
運行結(jié)果如下：
Stack : insert 100000 elements into the 1st position use time：1640 ms
Vector : insert 100000 elements into the 1st position use time：1607 ms
LinkedList : insert 100000 elements into the 1st position use time：29 ms
ArrayList : insert 100000 elements into the 1st position use time：1617 ms
Stack : read 100000 elements by position use time：9 ms
Vector : read 100000 elements by position use time：6 ms
LinkedList : read 100000 elements by position use time：10809 ms
ArrayList : read 100000 elements by position use time：5 ms
Stack : delete 100000 elements from the 1st position use time：1916 ms
Vector : delete 100000 elements from the 1st position use time：1910 ms
LinkedList : delete 100000 elements from the 1st position use time：15 ms
ArrayList : delete 100000 elements from the 1st position use time：1909 ms
從中，我們可以發(fā)現(xiàn)：
插入10萬個元素，LinkedList所花時間最短：29ms。
刪除10萬個元素，LinkedList所花時間最短：15ms。
遍歷10萬個元素，LinkedList所花時間最長：10809 ms；而ArrayList、Stack和Vector則相差不多，都只用了幾秒。
考慮到Vector是支持同步的，而Stack又是繼承于Vector的；因此，得出結(jié)論：
(01) 對于需要快速插入，刪除元素，應(yīng)該使用LinkedList。
(02) 對于需要快速隨機訪問元素，應(yīng)該使用ArrayList。
(03)
對于“單線程環(huán)境” 或者 “多線程環(huán)境，但List僅僅只會被單個線程操作”，此時應(yīng)該使用非同步的類。
第3部分 LinkedList和ArrayList性能差異分析
下面我們看看為什么LinkedList中插入元素很快，而ArrayList中插入元素很慢！
LinkedList.java中向指定位置插入元素的代碼如下：
// 在index前添加節(jié)點，且節(jié)點的值為element
public void add(int index, E element) {
addBefore(element, (index==size ? header : entry(index)));
}
// 獲取雙向鏈表中指定位置的節(jié)點
private Entry<E> entry(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+size);
Entry<E> e = header;
// 獲取index處的節(jié)點。
// 若index < 雙向鏈表長度的1/2,則從前向后查找;
// 否則，從后向前查找。
if (index < (size >> 1)) {
for (int i = 0; i <= index; i++)
e = e.next;
} else {
for (int i = size; i > index; i--)
e = e.previous;
}
return e;
}
// 將節(jié)點(節(jié)點數(shù)據(jù)是e)添加到entry節(jié)點之前。
private Entry<E> addBefore(E e, Entry<E> entry) {
// 新建節(jié)點newEntry，將newEntry插入到節(jié)點e之前；并且設(shè)置newEntry的數(shù)據(jù)是e
Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
// 插入newEntry到鏈表中
newEntry.previous.next = newEntry;
newEntry.next.previous = newEntry;
size++;
modCount++;
return newEntry;
}
從中，我們可以看出：通過add(int index, E element)向LinkedList插入元素時。先是在雙向鏈表中找到要插入節(jié)點的位置index；找到之后，再插入一個新節(jié)點。
雙向鏈表查找index位置的節(jié)點時，有一個加速動作：若index < 雙向鏈表長度的1/2，則從前向后查找; 否則，從后向前查找。
接著，我們看看ArrayList.java中向指定位置插入元素的代碼。如下：
// 將e添加到ArrayList的指定位置
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
ensureCapacity(size+1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
ensureCapacity(size+1) 的作用是“確認(rèn)ArrayList的容量，若容量不夠，則增加容量。”
真正耗時的操作是 System.arraycopy(elementData, index, elementData, index + 1, size - index);
Sun JDK包的java/lang/System.java中的arraycopy()聲明如下：
public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);
arraycopy()是個JNI函數(shù)，它是在JVM中實現(xiàn)的。sunJDK中看不到源碼，不過可以在OpenJDK包中看到的源碼。網(wǎng)上有對arraycopy()的分析說明，請參考：System.arraycopy源碼分析
實際上，我們只需要了解： System.arraycopy(elementData, index, elementData, index + 1, size - index); 會移動index之后所有元素即可。這就意味著，ArrayList的add(int index, E element)函數(shù)，會引起index之后所有元素的改變！
通過上面的分析，我們就能理解為什么LinkedList中插入元素很快，而ArrayList中插入元素很慢。
“刪除元素”與“插入元素”的原理類似，這里就不再過多說明。
接下來，我們看看 “為什么LinkedList中隨機訪問很慢，而ArrayList中隨機訪問很快”。
先看看LinkedList隨機訪問的代碼
// 返回LinkedList指定位置的元素
public E get(int index) {
return entry(index).element;
}
// 獲取雙向鏈表中指定位置的節(jié)點
private Entry<E> entry(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+size);
Entry<E> e = header;
// 獲取index處的節(jié)點。
// 若index < 雙向鏈表長度的1/2,則從前先后查找;
// 否則，從后向前查找。
if (index < (size >> 1)) {
for (int i = 0; i <= index; i++)
e = e.next;
} else {
for (int i = size; i > index; i--)
e = e.previous;
}
return e;
}
從中，我們可以看出：通過get(int index)獲取LinkedList第index個元素時。先是在雙向鏈表中找到要index位置的元素；找到之后再返回。
雙向鏈表查找index位置的節(jié)點時，有一個加速動作：若index < 雙向鏈表長度的1/2，則從前向后查找; 否則，從后向前查找。
下面看看ArrayList隨機訪問的代碼
// 獲取index位置的元素值
public E get(int index) {
RangeCheck(index);
return (E) elementData[index];
}
private void RangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
}
從中，我們可以看出：通過get(int index)獲取ArrayList第index個元素時。直接返回數(shù)組中index位置的元素，而不需要像LinkedList一樣進行查找。
第3部分 Vector和ArrayList比較
相同之處
1 它們都是List
它們都繼承于AbstractList，并且實現(xiàn)List接口。
ArrayList和Vector的類定義如下：
// ArrayList的定義
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
// Vector的定義
public class Vector<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {}
2 它們都實現(xiàn)了RandomAccess和Cloneable接口
實現(xiàn)RandomAccess接口，意味著它們都支持快速隨機訪問；
實現(xiàn)Cloneable接口，意味著它們能克隆自己。
3 它們都是通過數(shù)組實現(xiàn)的，本質(zhì)上都是動態(tài)數(shù)組
ArrayList.java中定義數(shù)組elementData用于保存元素
// 保存ArrayList中數(shù)據(jù)的數(shù)組
private transient Object[] elementData;
Vector.java中也定義了數(shù)組elementData用于保存元素
// 保存Vector中數(shù)據(jù)的數(shù)組
protected Object[] elementData;
4 它們的默認(rèn)數(shù)組容量是10
若創(chuàng)建ArrayList或Vector時，沒指定容量大小；則使用默認(rèn)容量大小10。
ArrayList的默認(rèn)構(gòu)造函數(shù)如下：
// ArrayList構(gòu)造函數(shù)。默認(rèn)容量是10。
public ArrayList() {
this(10);
}
Vector的默認(rèn)構(gòu)造函數(shù)如下：
// Vector構(gòu)造函數(shù)。默認(rèn)容量是10。
public Vector() {
this(10);
}
5 它們都支持Iterator和listIterator遍歷
它們都繼承于AbstractList，而AbstractList中分別實現(xiàn)了 “iterator()接口返回Iterator迭代器” 和 “listIterator()返回ListIterator迭代器”。
不同之處
1 線程安全性不一樣
ArrayList是非線程安全；
而Vector是線程安全的，它的函數(shù)都是synchronized的，即都是支持同步的。
ArrayList適用于單線程，Vector適用于多線程。
2 對序列化支持不同
ArrayList支持序列化，而Vector不支持；即ArrayList有實現(xiàn)java.io.Serializable接口，而Vector沒有實現(xiàn)該接口。
3 構(gòu)造函數(shù)個數(shù)不同
ArrayList有3個構(gòu)造函數(shù)，而Vector有4個構(gòu)造函數(shù)。Vector除了包括和ArrayList類似的3個構(gòu)造函數(shù)之外，另外的一個構(gòu)造函數(shù)可以指定容量增加系數(shù)。
ArrayList的構(gòu)造函數(shù)如下：
// 默認(rèn)構(gòu)造函數(shù)
ArrayList()
// capacity是ArrayList的默認(rèn)容量大小。當(dāng)由于增加數(shù)據(jù)導(dǎo)致容量不足時，容量會添加上一次容量大小的一半。
ArrayList(int capacity)
// 創(chuàng)建一個包含collection的ArrayList
ArrayList(Collection<? extends E> collection)
Vector的構(gòu)造函數(shù)如下：
// 默認(rèn)構(gòu)造函數(shù)
Vector()
// capacity是Vector的默認(rèn)容量大小。當(dāng)由于增加數(shù)據(jù)導(dǎo)致容量增加時，每次容量會增加一倍。
Vector(int capacity)
// 創(chuàng)建一個包含collection的Vector
Vector(Collection<? extends E> collection)
// capacity是Vector的默認(rèn)容量大小，capacityIncrement是每次Vector容量增加時的增量值。
Vector(int capacity, int capacityIncrement)
4 容量增加方式不同
逐個添加元素時，若ArrayList容量不足時，“新的容量”=“(原始容量x3)/2 + 1”。
而Vector的容量增長與“增長系數(shù)有關(guān)”，若指定了“增長系數(shù)”，且“增長系數(shù)有效(即，大于0)”；那么，每次容量不足時，“新的容量”=“原始容量+增長系數(shù)”。若增長系數(shù)無效(即，小于/等于0)，則“新的容量”=“原始容量 x 2”。
ArrayList中容量增長的主要函數(shù)如下：
public void ensureCapacity(int minCapacity) {
// 將“修改統(tǒng)計數(shù)”+1
modCount++;
int oldCapacity = elementData.length;
// 若當(dāng)前容量不足以容納當(dāng)前的元素個數(shù)，設(shè)置 新的容量=“(原始容量x3)/2 + 1”
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
Vector中容量增長的主要函數(shù)如下：
private void ensureCapacityHelper(int minCapacity) {
int oldCapacity = elementData.length;
// 當(dāng)Vector的容量不足以容納當(dāng)前的全部元素，增加容量大小。
// 若 容量增量系數(shù)>0(即capacityIncrement>0)，則將容量增大當(dāng)capacityIncrement
// 否則，將容量增大一倍。
if (minCapacity > oldCapacity) {
Object[] oldData = elementData;
int newCapacity = (capacityIncrement > 0) ?
(oldCapacity + capacityIncrement) : (oldCapacity * 2);
if (newCapacity < minCapacity) {
newCapacity = minCapacity;
}
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
5 對Enumeration的支持不同。Vector支持通過Enumeration去遍歷，而List不支持
Vector中實現(xiàn)Enumeration的代碼如下：
public Enumeration<E> elements() {
// 通過匿名類實現(xiàn)Enumeration
return new Enumeration<E>() {
int count = 0;
// 是否存在下一個元素
public boolean hasMoreElements() {
return count < elementCount;
}
// 獲取下一個元素
public E nextElement() {
synchronized (Vector.this) {
if (count < elementCount) {
return (E)elementData[count++];
}
}
throw new NoSuchElementException("Vector Enumeration");
}
};
}
