作者：nnngu
GitHub：https://github.com/nnngu
博客園：http://www.cnblogs.com/nnngu
簡書：http://www.itdecent.cn/users/1df20d76ea5c
知乎：https://www.zhihu.com/people/nnngu/posts

一般大家都知道ArrayList和LinkedList的區(qū)別：

1、ArrayList的實現(xiàn)是基于數(shù)組，LinkedList的實現(xiàn)是基于雙向鏈表。

2、對于隨機(jī)訪問，ArrayList優(yōu)于LinkedList

3、對于插入和刪除操作，LinkedList優(yōu)于ArrayList

4、LinkedList比ArrayList更占內(nèi)存，因為LinkedList的節(jié)點(diǎn)除了存儲數(shù)據(jù)，還存儲了兩個引用，一個指向前一個元素，一個指向后一個元素。

一．在時間復(fù)雜度上的區(qū)別

假設(shè)我們有兩個很大的列表，它們里面的元素已經(jīng)排好序了，這兩個列表分別是ArrayList類型和LinkedList類型的，現(xiàn)在我們對這兩個列表來進(jìn)行二分查找(binary search)，比較它們的查找速度。

代碼如下：

 1 package com.demo;
 2 
 3 import java.util.ArrayList;
 4 import java.util.Collections;
 5 import java.util.LinkedList;
 6 import java.util.List;
 7 
 8 public class Demo1 {
 9     static List<Integer> array = new ArrayList<Integer>();
10     static List<Integer> linked = new LinkedList<Integer>();
11 
12     public static void main(String[] args) {
13 
14         for (int i = 0; i < 10000; i++) {
15             array.add(i);
16             linked.add(i);
17         }
18         System.out.println("ArrayList訪問消耗的時間：" + getTime(array));
19         System.out.println("LinkedList訪問消耗的時間：" + getTime(linked));
20     }
21 
22     public static long getTime(List list) {
23         long time = System.currentTimeMillis();
24         for (int i = 0; i < 10000; i++) {
25             int index = Collections.binarySearch(list, list.get(i));
26             if (index != i) {
27                 System.out.println("ERROR!");
28             }
29         }
30         return System.currentTimeMillis() - time;
31     }
32 
33 }

運(yùn)行結(jié)果：

ArrayList訪問消耗的時間：10
LinkedList訪問消耗的時間：383

可以看出，對于隨機(jī)訪問，ArrayList的訪問速度更快。

ArrayList和LinkedList的插入數(shù)據(jù)耗時：

 1 package com.demo;
 2 
 3 import java.util.ArrayList; 
 4 import java.util.LinkedList;
 5 import java.util.List;
 6 
 7 public class Demo2 {
 8     static List<Integer> array = new ArrayList<Integer>();
 9     static List<Integer> linked = new LinkedList<Integer>();
10 
11     public static void main(String[] args) {
12 
13         for (int i = 0; i < 10000; i++) {
14             array.add(i);
15             linked.add(i);
16         }
17         System.out.println("ArrayList插入消耗的時間：" + insertTime(array));
18         System.out.println("LinkedList插入消耗的時間：" + insertTime(linked));
19     }
20 
21     public static long insertTime(List list) {
22         long time = System.currentTimeMillis();
23         for (int i = 100; i < 10000; i++) {
24             list.add(10, i); // 在索引為10的位置插入i
25         }
26         return System.currentTimeMillis() - time;
27     }
28 }

運(yùn)行結(jié)果：

LinkedList插入消耗的時間：4

可以看出，對于插入操作，LinkedList 的速度更快。

二．在空間復(fù)雜度上的區(qū)別

在LinkedList中有一個私有的內(nèi)部類，定義如下：

private static class Entry {   
         Object element;   
         Entry next;   
         Entry previous;   
     }   

LinkedList中的每一個元素中還存儲了它的前一個元素的索引和后一個元素的索引。

ArrayList使用一個內(nèi)置的數(shù)組來存儲元素，這個數(shù)組的起始容量是10，當(dāng)數(shù)組需要增長時，新的容量按如下公式獲得：新容量 = 舊容量×1.5 + 1，也就是說每一次容量大概會增長50%

總結(jié)：

ArrayList和LinkedList的區(qū)別如下：

1. ArrayList的實現(xiàn)是基于數(shù)組，LinkedList的實現(xiàn)是基于雙向鏈表。

2. 對于隨機(jī)訪問，ArrayList優(yōu)于LinkedList，ArrayList可以根據(jù)下標(biāo)以O(shè)(1)時間復(fù)雜度對元素進(jìn)行隨機(jī)訪問。而LinkedList的每一個元素都依靠地址指針和它后一個元素連接在一起，在這種情況下，查找某個元素的時間復(fù)雜度是O(n)

3. 對于插入和刪除操作，LinkedList優(yōu)于ArrayList，因為當(dāng)元素被添加到LinkedList任意位置的時候，不需要像ArrayList那樣重新計算大小或者是更新索引。

4. LinkedList比ArrayList更占內(nèi)存，因為LinkedList的節(jié)點(diǎn)除了存儲數(shù)據(jù)，還存儲了兩個引用，一個指向前一個元素，一個指向后一個元素。