點擊上方“朱小廝的博客”，選擇“設(shè)為星標(biāo)”

后臺回復(fù)”加群“加入公眾號專屬技術(shù)群

來源：uee.me/cFyW6

問題：

通常我會這么定義列表：

List<String> names = new ArrayList<>();

names類型使用List接口，那么具體實現(xiàn)該如何選擇。?

什么時候應(yīng)該用LinkedList替代ArrayList，反之亦然？

總結(jié)：

大多數(shù)情況下，相比LinkedList更推薦使用ArrayList或ArrayDeque。如果不確定，可以直接選用ArrayList。

LinkedList和ArrayList是List接口的兩種不同實現(xiàn)。LinkedList采用雙向鏈表實現(xiàn)。ArrayList通過動態(tài)調(diào)整數(shù)組大小實現(xiàn)。

與標(biāo)準(zhǔn)鏈表和數(shù)組操作一樣，不同的實現(xiàn)方法算法運(yùn)行時也不同。

對于LinkedList<E>

• get(int index)復(fù)雜度為O（n）（平均步長n/4）

• add(E element)復(fù)雜度為O（1）

• add(int index, E element)復(fù)雜度為O（n）（平均步長n/4）。但是當(dāng)index = 0時復(fù)雜度為O（1）<--- LinkedList<E>的主要優(yōu)點。

• remove(int index)復(fù)雜度為O（n）（平均步長n/4）
  

• Iterator.remove()復(fù)雜度為O（1）。<---LinkedList<E>的主要優(yōu)點

• ListIterator.add(E element)復(fù)雜度為O（1）。這是LinkedList<E>的一個主要優(yōu)點。

注意：許多操作平均需要n/4步長，最好的情況下（例如index= 0）步長為常數(shù)，最壞的情況下需要n/2步（列表中間）。

對于ArrayList<E>

• get(int index)復(fù)雜度為O（1）<--- ArrayList<E>的主要優(yōu)點

• add(E element)分?jǐn)偤蟮膹?fù)雜度為O（1），但最壞的情況是O（n），因為需要調(diào)整數(shù)組大小并進(jìn)行拷貝

• add（int index，E element）復(fù)雜度為O（n）（平均步長n/2）

• remove(int index)復(fù)雜度為O（n）（平均步長n/2）

• Iterator.remove()復(fù)雜度為O（n）（平均步長n/2）

• ListIterator.add(E element)復(fù)雜度為O（n）（平均步長n/2）

注意：許多操作要求平均步長為n/2，最好情況下（列表末尾）步長為常數(shù)，最壞情況下（列表開始）需要n步

LinkedList<E>可以使用iterator實現(xiàn)固定時間插入或刪除，但只能順序訪問元素。換句話說，可以向前或向后遍歷列表，但是在列表中查找固定位置元素花費(fèi)的時間與列表大小成正比。Javadoc中這么寫道：“在列表中建立索引，會從列頭或列尾開始遍歷，從更靠近的位置開始”，這些方法平均復(fù)雜度為O（n）（平均步長n/4），盡管index = 0時復(fù)雜度為O(1)。

另一方面，ArrayList<E>支持快速隨機(jī)讀取訪問，因此獲取任何元素都能在恒定時間內(nèi)完成。但是，除了列尾在其它任何位置添加或刪除元素，都需要把后面的所有元素移位。同樣，如果添加的元素多于底層數(shù)組的容量，則會分配一個新數(shù)組（大小是之前的1.5倍），并把舊數(shù)組復(fù)制到新數(shù)組中。因此在ArrayList中添加元素時間復(fù)雜度最差為O（n），平均情況下為常數(shù)。

因此，根據(jù)您打算執(zhí)行的操作選擇對應(yīng)的實現(xiàn)。遍歷這兩種List開銷都很小。（從技術(shù)上看ArrayList更快，但除非確實對性能要求十分敏感，否則不必?fù)?dān)心。遍歷的復(fù)雜度都是常量）

使用LinkedList其中一個好處可以重用已有iterator插入和刪除元素。然后修改本地列表即可，操作的時間復(fù)雜度為O（1）。在ArrayList中，數(shù)組余下的部分需要移動（即拷貝）。而在LinkedList中執(zhí)行seek操作遍歷，最壞時間復(fù)雜度為O（n）（平均步長n/2），而ArrayList中，可以直接計算位置進(jìn)行訪問，復(fù)雜度為O（1）。

在LinkedList列頭增加或刪除操作時間復(fù)雜度為O（1），而ArrayList需要O（n）。請注意：ArrayDeque可以用來替代LinkedList，適合在列頭添加和刪除元素，但它不是List。

另外，如果列表很大，請記住，內(nèi)存使用情況也有所不同。每個LinkedList元素都有額外開銷，因為里面還存儲了指向下一個和上一個元素的指針。ArrayLists沒有這種開銷。但是，無論是否實際添加了元素，ArrayList都會分配初始容量大小的內(nèi)存。

ArrayList默認(rèn)初始容量很小（Java 1.4-1.8中設(shè)為10）。但是由于底層實現(xiàn)是數(shù)組，因此如果添加很多元素，則必須調(diào)整數(shù)組大小。如果提前知道需要添加很多元素，為避免調(diào)整數(shù)組大小帶來的開銷，在創(chuàng)建ArrayList時需要設(shè)置更大的初始容量。

答案2(案例分析)：

現(xiàn)代計算機(jī)體系結(jié)構(gòu)中，ArrayList性能幾乎在所有情況下都得到大大提升。因此，除非一些非常獨(dú)特和極端的情況，應(yīng)避免使用LinkedList。

從理論上講，LinkedList的add(E element)時間復(fù)雜度為O(1)。

同樣，在列表中間添加元素應(yīng)該非常有效。

實際并非如此，因為LinkedList是一種對緩存不友好的數(shù)據(jù)結(jié)構(gòu)。從性能的角度看，只有在極少數(shù)情況下，LinkedList的性能會優(yōu)于緩存友好的ArrayList。

下面是在隨機(jī)位置插入元素的基準(zhǔn)測試結(jié)果。就像你看到的那樣：ArrayList的效率要高得多。盡管從理論上講，每次向列表中插入元素都需要“移動”數(shù)組中后續(xù)n個后元素（個數(shù)越少越好）：

在緩存更大、速度更快的下一代硬件上運(yùn)行，得出的結(jié)論更明確：

LinkedList完成相同工作所需的時間更長。

有兩個主要原因：

主要原因：LinkedList節(jié)點隨機(jī)分布在整個內(nèi)存中。RAM（“隨機(jī)訪問存儲器”）并不是真正隨機(jī)，需要獲取內(nèi)存塊進(jìn)行緩存。這個操作非常耗時，并且當(dāng)這種操作頻繁發(fā)生時，需要一直替換緩存中的內(nèi)存頁 -> 緩存未命中 -> 緩存效率低下。ArrayList元素存儲在連續(xù)內(nèi)存中，這正是現(xiàn)代CPU架構(gòu)優(yōu)化的內(nèi)容。

其次，LinkedList需要保留指向前一個與后一個元素的指針，這意味著每個元素的內(nèi)存消耗是ArrayList的3倍。

DynamicIntArray是一個自定義ArrayList實現(xiàn)，元素類型為Int（原始類型）而非Object。因此所有數(shù)據(jù)實際上都是相鄰存儲，因此效率更高。

記住一個關(guān)鍵因素，獲取存儲塊比訪問單個存儲單元的開銷更大。這就是為什么讀取器1MB順序內(nèi)存要比從不同內(nèi)存塊中讀取同樣的數(shù)據(jù)量快400倍的原因：

延遲數(shù)據(jù)比較（?2012）
----------------------------------
L1 cache reference 0.5 ns
Branch mispredict 5 ns
L2 cache reference 7 ns 14x L1 cache
Mutex lock/unlock 25 ns
Main memory reference 100 ns 20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy 3,000 ns 3 us
Send 1K bytes over 1 Gbps network 10,000 ns 10 us
Read 4K randomly from SSD* 150,000 ns 150 us ~1GB/sec SSD
Read 1 MB sequentially from memory 250,000 ns 250 us
Round trip within same datacenter 500,000 ns 500 us
Read 1 MB sequentially from SSD* 1,000,000 ns 1,000 us 1 ms ~1GB/sec SSD, 4X memory
Disk seek 10,000,000 ns 10,000 us 10 ms 20x datacenter roundtrip
Read 1 MB sequentially from disk 20,000,000 ns 20,000 us 20 ms 80x memory, 20X SSD
Send packet CA->Netherlands->CA 150,000,000 ns 150,000 us 150 ms

來源：每個程序員都應(yīng)該知道的延遲數(shù)據(jù)

為了讓觀點表達(dá)得更清晰，可以查看列表開頭的add element結(jié)果。從理論上講，這只是一種情況。其實LinkedList應(yīng)該表現(xiàn)得更好，而ArrayList的結(jié)果應(yīng)該不及它：

注意：這是C++ Std庫的基準(zhǔn)測試。但是根據(jù)我之前的經(jīng)驗，C++和Java的結(jié)果非常類似。源代碼

復(fù)制連續(xù)內(nèi)存是現(xiàn)代CPU的一種優(yōu)化：理論在不斷演變，實際上又讓ArrayList和Vector效率變得更高。

參考文中發(fā)布的所有基準(zhǔn)測試均來自KjellHedstr?m。在他的博客上可以找到更多數(shù)據(jù)。博客地址：https://kjellkod.wordpress.com/

想知道更多？掃描下面的二維碼關(guān)注我

【限時推廣1】

極客時間雙十二全場優(yōu)惠，特定申請了一個15元（滿40減15）優(yōu)惠口令：NIUBISIDA（上次的SIDANIUBI用掉了...），有效期截止日期本月月底。

【限時推廣2】

當(dāng)當(dāng)自營圖書百萬品種五折封頂，我這里有個優(yōu)惠碼：SD44VF，實付滿200減30（全場自營圖書可用），記住有效期是 12.9-12.12

朕已閱?

總結(jié)

以上是生活随笔為你收集整理的嗯？那你来说说用 ArrayList 还是 LinkedList的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。