幾乎所有Java面試都會問到的問題：說ArrayList和LinkedList的差別

前言

大家好，我是你們的老朋友青戈，知道你們想我了，所以我又來了?

Java的資料結構是面試考察的重點，只要參與過Java面試的同學相信都有所體會。面試官問這類問題的時候往往是想檢視你是否研究過Java中常用資料類型的底層結構，而不是只是簡單的停留在"會使用"的層次。那麼在面試的過程中我們要如何把這個問題說好，讓面試官滿意呢？

本期我將針對Java高頻考點ArrayList和LinkedList的原理進行分析，希望能幫助你。

ArrayList和LinkedList簡介

ArrayList底層是一個Object類型的數組，初始容量是10，支援動態擴容，擴容後的容量是目前容量的1.5倍，它的最大容量是Integer.MAX_VALUE - 8（但是仍可以擴容到Integer.MAX_VALUE），對於空出的8位，目前的解釋是避免一些機器記憶體溢出，減少出錯幾率。

LinkedList底層是雙向鍊錶，初始容量是0，擴容只需新建節點進行指標指向即可。

為了簡化成口頭可表述的語言，方便同學們在面試的時候向面試官解釋，我這裡就不貼源碼輔助說明了，有興趣的同學可以自己翻源碼看看內部的構造和方法，加深對這塊的理解。

區別

• # ArrayList隨機存取效率很高，因為元素的儲存是有序的，透過下標index可以知道所查詢資料在記憶體中的位置，尋址快，時間複雜度O(1)；
• #LinkedList查詢效率較低，它在查詢指定資料的時候需要遍歷鍊錶逐一查詢，時間複雜度O(n)。

插入

• ArrayList在尾部插入的效率比較高，時間複雜度O(1)，但在其他位置插入效率則比較低，需要進行大量的資料移動，時間複雜度O(n)；
• #LinkedList在頭部和尾部插入元素的效率比較高，時間複雜度為O(1)，但在中間指定位置插入元素，需要先遍歷找到元素的位置，再插入，時間複雜度O(n)。

刪除

• #ArrayList移除元素除了結尾節點之外都伴隨著需要進行大量的資料移動，時間複雜度O(n)；
• LinkedList刪除元素效率相對較高，只需要改變指標的指向，但是刪除元素需要遍歷查詢出資料的位置，時間複雜度O (n)。

記憶體空間

• #ArrayList基於數組實現，每次擴容後容量是固定的，所以在尾部會預留一部分的空間；
• LinkedList是基於雙向鍊錶實現，所以每個節點除了保存資料之外還需要保存前後節點的指針，會消耗一部分空間。

擴充機制

• #ArrayList每次擴容需要把原數組的元素複製到新的陣列裡面去；
• LinkedList是鍊錶，不存在擴容的說法。

相同點

執行緒安全性

ArrayList和LinkedList都是線程不安全的，多線程環境下容易造成髒讀的問題，可以使用Collections.synchronizedList()方法保證線程的安全性

#儲存特點

儲存的元素都是有順序的，都是可以重複的，新增元素都是儲存到List的結尾處。

以上是幾乎所有Java面試都會問到的問題：說ArrayList和LinkedList的差別的詳細內容。更多資訊請關注PHP中文網其他相關文章！