LinkedList、ArrayList各自的使用場景，如何確認(rèn)應(yīng)該用哪一個呢？

一言以蔽之，在大部分情況下，使用ArrayList會好一些。

耗時上各有優(yōu)缺點。ArrayList稍有優(yōu)勢 List只是一個接口，而LinkedList、ArrayList是List的不同實現(xiàn)。LinkedList的模型是雙向鏈表，而ArrayList則是動態(tài)數(shù)組

首先對比下常用操作的算法復(fù)雜度 

LinkedList

get(int index) : O(n)  
add(E element) : O(1)  
add(int index, E element) : O(n)  
remove(int index) : O(n)  
Iterator.remove() : O(1) <--- LinkedList的主要優(yōu)點  
ListIterator.add(E element) is O(1) <--- LinkedList的主要優(yōu)點 

ArrayList

get(int index) : O(1) <--- ArrayList的主要優(yōu)點  
add(E element) : 基本是O(1) , 因為動態(tài)擴容的關(guān)系，最差時是 O(n)  
add(int index, E element) : 基本是O( n - index) , 因為動態(tài)擴容的關(guān)系，最差時是 O(n)  
remove(int index) : O(n - index) (例如，移除最后一個元素，是 O(1))  
Iterator.remove() : O(n - index)  
ListIterator.add(E element) : O(n - index)

LinkedList，因為本質(zhì)是個鏈表，所以通過Iterator來插入和移除操作的耗時，都是個恒量，但如果要獲取某個位置的元素，則要做指針遍歷。因此，get操作的耗時會跟List長度有關(guān)。

對于ArrayList來說，得益于快速隨機訪問的特性，獲取任意位置元素的耗時，是常量的。但是，如果是add或者remove操作，要分兩種情況，如果是在尾部做add，也就是執(zhí)行add方法（沒有index參數(shù)），此時不需要移動其他元素，耗時是O(1),但如果不是在尾部做add，也就是執(zhí)行add(int index, E element),這時候在插入新元素的同時，也要移動該位置后面的所有元素，以為新元素騰出位置，此時耗時是O(n-index)。另外，當(dāng)List長度超過初始化容量時，會自動生成一個新的array(長度是之前的1.5倍),此時會將舊的array移動到新的array上，這種情況下的耗時是O(n)。

總之，get操作，ArrayList快一些。而add操作，兩者差不多。（除非是你希望在List中間插入節(jié)點，且維護了一個Iterator指向指定位置，這時候linkedList能快一些，但是，我們更多時候是直接在尾部插入節(jié)點，這種特例的情況并不多） 

空間占用上，ArrayList完勝 看下兩者的內(nèi)存占用圖

這三個圖，橫軸是list長度，縱軸是內(nèi)存占用值。兩條藍(lán)線是LinkedList，兩條紅線是ArrayList

可以看到，LinkedList的空間占用，要遠(yuǎn)超ArrayList。LinkedList的線更陡，隨著List長度的擴大，所占用的空間要比同長度的ArrayList大得多。 

注：從mid JDK6之后，默認(rèn)啟用了CompressedOops ，因此64位及32位下的結(jié)果沒有差異，LinkedList x64和LinkedList x32的線是一樣的。