LinkedList和ArrayList的區(qū)別
LinkedeList和ArrayList都實(shí)現(xiàn)了List接口纵穿，但是它們的工作原理卻不一樣诀拭。它們之間最主要的區(qū)別在于ArrayList是可改變大小的數(shù)組簸呈，而LinkedList是雙向鏈接串列(doubly LinkedList)额港。ArrayList更受歡迎样屠，很多場(chǎng)景下ArrayList比LinkedList更為適用。這篇文章中我們將會(huì)看看LinkedeList和ArrayList的不同哀托，而且我們?cè)噲D來看看什么場(chǎng)景下更適宜使用LinkedList惦辛，而不用ArrayList。
arrayList_linkedList-300x151 (1).jpeg
LinkedList和ArrayList的區(qū)別
LinkedList和ArrayList的差別主要來自于Array和LinkedList數(shù)據(jù)結(jié)構(gòu)的不同仓手。如果你很熟悉Array和LinkedList胖齐，你很容易得出下面的結(jié)論：
- 因?yàn)锳rray是基于索引(index)的數(shù)據(jù)結(jié)構(gòu)，它使用索引在數(shù)組中搜索和讀取數(shù)據(jù)是很快的嗽冒。Array獲取數(shù)據(jù)的時(shí)間復(fù)雜度是O(1),但是要?jiǎng)h除數(shù)據(jù)卻是開銷很大的呀伙，因?yàn)檫@需要重排數(shù)組中的所有數(shù)據(jù)。
- 相對(duì)于ArrayList添坊，LinkedList插入是更快的剿另。因?yàn)長inkedList不像ArrayList一樣，不需要改變數(shù)組的大小贬蛙，也不需要在數(shù)組裝滿的時(shí)候要將所有的數(shù)據(jù)重新裝入一個(gè)新的數(shù)組雨女，這是ArrayList最壞的一種情況，時(shí)間復(fù)雜度是O(n)阳准，而LinkedList中插入或刪除的時(shí)間復(fù)雜度僅為O(1)氛堕。ArrayList在插入數(shù)據(jù)時(shí)還需要更新索引（除了插入數(shù)組的尾部）。
- 類似于插入數(shù)據(jù)野蝇，刪除數(shù)據(jù)時(shí)讼稚，LinkedList也優(yōu)于ArrayList。
- LinkedList需要更多的內(nèi)存浪耘，因?yàn)锳rrayList的每個(gè)索引的位置是實(shí)際的數(shù)據(jù)乱灵，而LinkedList中的每個(gè)節(jié)點(diǎn)中存儲(chǔ)的是實(shí)際的數(shù)據(jù)和前后節(jié)點(diǎn)的位置。
什么場(chǎng)景下更適宜使用LinkedList七冲，而不用ArrayList
我前面已經(jīng)提到，很多場(chǎng)景下ArrayList更受歡迎规婆，但是還有些情況下LinkedList更為合適澜躺。譬如：
- 你的應(yīng)用不會(huì)隨機(jī)訪問數(shù)據(jù)。因?yàn)槿绻阈枰狶inkedList中的第n個(gè)元素的時(shí)候抒蚜，你需要從第一個(gè)元素順序數(shù)到第n個(gè)數(shù)據(jù)掘鄙，然后讀取數(shù)據(jù)。
- 你的應(yīng)用更多的插入和刪除元素嗡髓，更少的讀取數(shù)據(jù)操漠。因?yàn)椴迦牒蛣h除元素不涉及重排數(shù)據(jù)，所以它要比ArrayList要快。
以上就是關(guān)于ArrayList和LinkedList的差別浊伙。你需要一個(gè)不同步的基于索引的數(shù)據(jù)訪問時(shí)撞秋，請(qǐng)盡量使用ArrayList。ArrayList很快嚣鄙，也很容易使用吻贿。但是要記得要給定一個(gè)合適的初始大小，盡可能的減少更改數(shù)組的大小哑子。
