List 是重要的數(shù)據(jù)結(jié)構(gòu)之一。最常用的的便是： ArrayList、Vector 和 LinkedList 三種了，他們類圖如下圖所示：
由上圖可知，這三種 List 都實(shí)現(xiàn)了 Collection 和 List 接口。
這三種不同的實(shí)現(xiàn)中，ArrayList 和 Vector 使用了數(shù)組實(shí)現(xiàn)，封裝了對(duì)內(nèi)部數(shù)組的操作。它們倆唯一的區(qū)別是 ArrayList 沒有任何一個(gè)方法是同步的，而 Vector 則是做了線程同步。我們之后均以 ArrayList 為例進(jìn)行講解。
LinkList 使用了雙向鏈表數(shù)據(jù)結(jié)構(gòu)，并且維護(hù)了 first 和 last 兩個(gè)成員變量來指示鏈表的頭和尾。這和 ArrayList 是截然不同的實(shí)現(xiàn)技術(shù)，也決定了它們適用于不同的場(chǎng)景中。
LinkedList 是由一系列表項(xiàng)連接而成的。一個(gè)表項(xiàng)總是分為三個(gè)部分，分別是：元素內(nèi)容，前驅(qū)表項(xiàng) 和 后驅(qū)表項(xiàng)，如下圖所示：
在 JDK 的視線中，不管 LinkedList 是否為空，鏈表中總是有一個(gè)** header** 表項(xiàng)，它即表示鏈表的開始，也表示鏈表的結(jié)尾。
下面以增加和刪除為例，比較 ArrayList 和 LinkList 的不同之處。
1、增加元素到列表尾端
在 ArrayList 中增加元素到隊(duì)列端尾的代碼如下：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 確保內(nèi)部數(shù)組有足夠的空間
elementData[size++] = e;
return true;
}
ArrayList 中 add() 方法的性能取決于 ensureCapacity() 方法。ensureCapacity() 的實(shí)現(xiàn)如下：
/**
* 分配的最大內(nèi)存。
* 有些虛擬機(jī)會(huì)為數(shù)組保留了一些頭部?jī)?nèi)容，試圖分配更多的空間會(huì)引起內(nèi)存溢出
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void ensureCapacityInternal(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); //計(jì)劃擴(kuò)容到現(xiàn)在容量的1.5倍
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); //進(jìn)行新舊數(shù)組的復(fù)制
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
可以看到，只要 ArrayList 的當(dāng)前容量很大，add() 操作的效率是非常高的。只有當(dāng) ArrayList 對(duì)容量的需求超過當(dāng)前數(shù)組的大小時(shí)，才需要擴(kuò)容。擴(kuò)容過程中，會(huì)進(jìn)行大量的數(shù)組復(fù)制操作。當(dāng)數(shù)組復(fù)制時(shí)，最終調(diào)用 Arrays.copyof() 方法。
LinkedList 的 add() 操作實(shí)現(xiàn)如下，它將任意元素增加到隊(duì)列的尾端：
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
linkLast() 方法將 e 插入到鏈表的末尾?？梢姡琇inkedList 由于使用了鏈表的結(jié)構(gòu)，因此不需要維護(hù)容量的大小。從這點(diǎn)上，它比 ArrayList 有一定的性能優(yōu)勢(shì)，然而每次元素增加都要新建一個(gè) Entry 對(duì)象，并進(jìn)行更多的賦值操作。在頻繁的系統(tǒng)調(diào)用中，對(duì)性能有一定的影響。
分別使用 ArrayList 和 LinkedList 運(yùn)行以下代碼：
public class ListTest {
public static void testArrayList() {
Object obj = new Object();
List list = new ArrayList<>();
for (int i = 0; i < 500000; i++) {
list.add(obj);
}
}
public static void testLinkedList() {
Object obj = new Object();
List list = new LinkedList<>();
for (int i = 0; i < 500000; i++) {
list.add(obj);
}
}
public static void main(String[] args){
testArrayList();
testLinkedList();
}
}
使用 TPTP 分析運(yùn)行結(jié)果為：
可以看到，ArrayList 的性能比 LinkedList 性能高出 4 倍左右。
2、增加元素到列表任意位置
在 ArrayList 中，任意位置插入的實(shí)現(xiàn)代碼如下：
public void add(int index, E element) {
rangeCheckForAdd(index); //數(shù)組越界檢查
ensureCapacityInternal(size + 1); // 增加modCount值
System.arraycopy(elementData, index, elementData, index + 1,
size - index); //index 之后的元素都需要后移一個(gè)單位
elementData[index] = element;
size++;
}
可以看到，每次插入操作，都會(huì)進(jìn)行一次數(shù)組的復(fù)制。而這個(gè)操作在增加元素到 List 尾端的時(shí)候是不存在的。大量的數(shù)組重組操作會(huì)導(dǎo)致系統(tǒng)性能低下。并且，插入的元素在 List 中的位置越靠前，數(shù)組重組的開銷也越大。
而LinkedList 此時(shí)就顯示出了優(yōu)勢(shì)：
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
可見，對(duì)于 LinkedList 來說，在 List 尾端插入數(shù)據(jù)與在任意位置插入數(shù)據(jù)是一樣的。并不會(huì)因?yàn)椴迦氲奈恢每壳岸鴮?dǎo)致插入方法的性能降低?，F(xiàn)在在極端情況下對(duì)他們的這個(gè)方法進(jìn)行測(cè)試，每次都將元素插入到 List 的最前端。
public class ListTest {
public static void testArrayList() {
Object obj = new Object();
List list = new ArrayList<>();
for (int i = 0; i < 50000; i++) {
list.add(0, obj);
}
}
public static void testLinkedList() {
Object obj = new Object();
List list = new LinkedList<>();
for (int i = 0; i < 50000; i++) {
list.add(0, obj);
}
}
public static void main(String[] args) {
testArrayList();
testLinkedList();
}
}
運(yùn)行以上代碼，執(zhí)行時(shí)間如下：
可以看出，兩者性能有天差地壤的差別。
然后每次都插入中間位置：
list.add(list.size()>>1, obj);
性能結(jié)果如下：
可以看到，此時(shí) LinkedList 的性能反而滿了好幾倍。
我們?cè)俨迦肽┪参恢茫?/p>
list.add(list.size(), obj);
性能結(jié)果如下：
我們可以看到，依然是 LinkedList 的性能較慢。
因此通過對(duì)比以上三種情況下的插入操作，我們得到如下結(jié)論：當(dāng)插入的位置靠前的時(shí)候，ArrayList 的性能是由于 LinkedList 的。而當(dāng)插入的位置越來越靠后， ArrayList 的性能變得比 LinkedList 越來越好。
這是因?yàn)椋?ArrayList 的性能損耗主要在于每次插入需要復(fù)制數(shù)組，LinkedList 的性能損耗則在循環(huán)遍歷鏈表找插入位置元素的上面。當(dāng)插入位置靠前的時(shí)候，ArrayList 會(huì)花費(fèi)大量的時(shí)間在復(fù)制數(shù)組上面，而 LinkedList 遍歷鏈表找插入位置的時(shí)間消耗確是最少的。隨著插入位置越來越靠后， ArrayList 需要復(fù)制的數(shù)組越來越小，消耗的時(shí)間越來越少。而 LinkedList 尋找的時(shí)間越來越多（確切的說，當(dāng)插入位置為中間的時(shí)候，LinkedList 尋找的時(shí)間是最多的 ）或者說是比不上 ArrayList 復(fù)制數(shù)組時(shí)間的減少速度。
3、刪除任意位置元素
對(duì)于 ArrayList 來說， remove() 方法和 add() 方法雷同。在任意位置移除元素后，都要進(jìn)行數(shù)組的重組。實(shí)現(xiàn)如下：
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; // Let gc do its work
return oldValue;
}
可以看到，在 ArrayList 的每一次有效地元素刪除操作后，都要進(jìn)行數(shù)組的重組。并且刪除的位置越靠前，數(shù)組重組時(shí)的開銷也越大；要?jiǎng)h除的元素越靠后，開銷越小。
對(duì)于 LinkedList ，刪除操作的實(shí)現(xiàn)如下：
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
主要的時(shí)間消耗也是在尋找刪除位置元素上面。
刪除的性能對(duì)比和增加的性能對(duì)比可以參照插入操作的性能對(duì)比。
4、容量參數(shù)
容量參數(shù)是ArrayList 和 Vector 等基于數(shù)組的 List 的特有性能參數(shù)，它表示初始化數(shù)組大小。每一次數(shù)組元素?cái)?shù)量超過其現(xiàn)有大小的時(shí)候，它表會(huì)進(jìn)行一次擴(kuò)容，數(shù)組的擴(kuò)容會(huì)導(dǎo)致整個(gè)數(shù)組進(jìn)行一次內(nèi)存復(fù)制。因此合理的數(shù)組大小有助于減少數(shù)組擴(kuò)容的次數(shù)，從而提高系統(tǒng)性能。
默認(rèn)情況下， ArrayList 的數(shù)組初始大小為10，每次進(jìn)行擴(kuò)容將新的數(shù)組大小設(shè)置為原來的1.5倍。
