原創於【模稜博客】 www.flammulina.com
1. List概述
List是一個有序的元素序列。當我們談論List時，最好將它與Set進行比較，Set是一組唯一且無序的元素。以下是Collection的類層次結構圖。從層次結構圖中，可以大致瞭解Java集合。
2. ArrayList vs. LinkedList vs. Vector
從層次結構圖中，它們都實現了 List 接口。它們與使用非常相似。它們的主要區別在於它們的實現，這導致不同操作的不同性能。
數組列表實現為可調整大小的數組。隨著向ArrayList添加更多元素，其大小會動態增加。可以使用get和set方法直接訪問它的元素，因為ArrayList本質上是一個數組。
Vector 與ArrayList類似，但它是同步的。
如果您的程序是線程安全的，則ArrayList是更好的選擇。隨著更多元素的添加，Vector和ArrayList需要更多空間。Vector每次將其數組大小加倍，而ArrayList每次增加其大小的50％。然而，LinkedList也實現了Queue， 添加比ArrayList和Vector多了一些方法的接口，例如offer（），peek（），poll（）等。
注意：ArrayList的默認初始容量非常小。構造具有更高初始容量的ArrayList是一個好習慣。這可以避免調整大小的成本。
3. ArrayList示例
ArrayList
al.add(3);
al.add(2);
al.add(1);
al.add(4);
al.add(5);
al.add(6);
al.add(6);
Iterator
while(iter1.hasNext()){
System.out.println(iter1.next());
}
4. LinkedList示例
LinkedList
ll.add(3);
ll.add(2);
ll.add(1);
ll.add(4);
ll.add(5);
ll.add(6);
ll.add(6);
Iterator
while(iter2.hasNext()){
System.out.println(iter2.next());
}
如上面的例子所示，它們與使用類似。真正的區別在於它們的底層實現和它們的操作複雜性。
5. Vector
Vector幾乎與ArrayList相同，不同之處在於Vector是同步的。因此，它的開銷比ArrayList高。通常，大多數Java程序員使用ArrayList而不是Vector，因為它們可以自己顯式同步。
6. ArrayList與LinkedList的性能
時間複雜度比較如下：
1 代表時間快 n 代表時間慢
- ArrayList對於任意添加/刪除索引具有O（n）時間複雜度，但對於列表末尾的操作具有O（1）時間複雜度。
- LinkedList對於任意添加/刪除索引具有O（n）時間複雜度，但對於List的結尾/開始處的操作具有O（1）。
我使用以下代碼來測試它們的性能：
ArrayList
LinkedList
// ArrayList add 方法
long startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
arrayList.add(i);
}
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println("ArrayList add: " + duration);
// LinkedList add 方法
startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
linkedList.add(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedList add: " + duration);
// ArrayList get 方法
startTime = System.nanoTime();
for (int i = 0; i < 10000; i++) {
arrayList.get(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("ArrayList get: " + duration);
// LinkedList get 方法
startTime = System.nanoTime();
for (int i = 0; i < 10000; i++) {
linkedList.get(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedList get: " + duration);
// ArrayList remove 方法
startTime = System.nanoTime();
for (int i = 9999; i >=0; i--) {
arrayList.remove(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("ArrayList remove: " + duration);
// LinkedList remove 方法
startTime = System.nanoTime();
for (int i = 9999; i >=0; i--) {
linkedList.remove(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedList remove: " + duration);
輸出是：(毫秒)
ArrayList add: 13265642
LinkedList add: 9550057
ArrayList get: 1543352
LinkedList get: 85085551
ArrayList remove: 199961301
LinkedList remove: 85768810
總結
他們的表現差異很明顯。LinkedList在添加和刪除方面更快，但在get中更慢。根據複雜性表和測試結果，我們根據使用場景靈活選擇使用ArrayList或LinkedList。簡而言之，沒有大量的隨機訪問，但有大量的添加刪除操作那麼 首選LinkedList ！
閱讀更多 模稜JAVA 的文章
