ArrayList底層的實現(xiàn)是Array, 數(shù)組擴容實現(xiàn)
image
-
新增數(shù)據(jù)空間判斷
新增數(shù)據(jù)的時候需要判斷當(dāng)前是否有空閑空間存儲
擴容需要申請新的連續(xù)空間
把老的數(shù)組復(fù)制過去
新加的內(nèi)容
回收老的數(shù)組空間
LinkList是一個雙鏈表,在添加和刪除元素時具有比ArrayList更好的性能.但在get與set方面弱于ArrayList.當(dāng)然,這些對比都是指數(shù)據(jù)量很大或者操作很頻繁。
image
鏈表不需要連續(xù)的空間, 大小不確定
1、底層實現(xiàn)：
ArrayList是實現(xiàn)了基于動態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)，而LinkedList是基于鏈表的數(shù)據(jù)結(jié)構(gòu)；
2、時間復(fù)雜度
操作 數(shù)組 鏈表
隨機訪問 O(1) O(N)
頭部插入 O(N) O(1)
頭部刪除 O(N) O(1)
尾部插入 O(1) O(1)
尾部刪除 O(1) O(1)
查詢對象所在索引 O(n) O(n)
查詢對象所在索引時間復(fù)雜度都是O(N), 但是數(shù)組要比鏈表快
因為數(shù)組的連續(xù)內(nèi)存, 會有一部分或者全部數(shù)據(jù)一起進入到CPU緩存, 而鏈表還需要在去內(nèi)存中根據(jù)上下游標(biāo)查找, CPU緩存比內(nèi)存塊太多
從源碼可以看出，ArrayList想要get(int index)元素時，直接返回index位置上的元素，而LinkedList需要通過for循環(huán)進行查找，雖然LinkedList已經(jīng)在查找方法上做了優(yōu)化，比如index < size / 2，則從左邊開始查找，反之從右邊開始查找，但是還是比ArrayList要慢。這點是毋庸置疑的。
ArrayList想要在指定位置插入或刪除元素時，主要耗時的是System.arraycopy動作，會移動index后面所有的元素；LinkedList主耗時的是要先通過for循環(huán)找到index，然后直接插入或刪除。這就導(dǎo)致了兩者并非一定誰快誰慢
3、空間復(fù)雜度
在LinkedList中有一個私有的內(nèi)部類，定義如下：
private static class Entry {
Object element;
Entry next;
Entry previous;
}
每個Entry對象reference列表中的一個元素，同時還有在LinkedList中它的上一個元素和下一個元素。一個有1000個元素的LinkedList對象將有1000個鏈接在一起的Entry對象，每個對象都對應(yīng)于列表中的一個元素。這樣的話，在一個LinkedList結(jié)構(gòu)中將有一個很大的空間開銷，因為它要存儲這1000個Entity對象的相關(guān)信息。
ArrayList使用一個內(nèi)置的數(shù)組來存儲元素，這個數(shù)組的起始容量是10.當(dāng)數(shù)組需要增長時，新的容量按如下公式獲得：新容量=(舊容量*3)/2+1，也就是說每一次容量大概會增長50%。這就意味著，如果你有一個包含大量元素的ArrayList對象，那么最終將有很大的空間會被浪費掉，這個浪費是由ArrayList的工作方式本身造成的。如果沒有足夠的空間來存放新的元素，數(shù)組將不得不被重新進行分配以便能夠增加新的元素。對數(shù)組進行重新分配，將會導(dǎo)致性能急劇下降。如果我們知道一個ArrayList將會有多少個元素，我們可以通過構(gòu)造方法來指定容量。我們還可以通過trimToSize方法在ArrayList分配完畢之后去掉浪費掉的空間。
ArrayList的空間浪費主要體現(xiàn)在在list列表的結(jié)尾預(yù)留一定的容量空間，而LinkedList的空間花費則體現(xiàn)在它的每一個元素都需要消耗相當(dāng)?shù)目臻g
實際開發(fā)中怎么選擇？
1、如果你十分確定你插入、刪除的元素是在前半段，使用LinkedList
2、如果你十分確定你刪除、刪除的元素后半段，使用ArrayList
3、如果你上面的兩點不確定，建議你使用LinkedList
說明：
其一、LinkedList整體插入、刪除的執(zhí)行效率比較穩(wěn)定，沒有ArrayList這種越往后越快的情況；
其二、插入元素的時候，弄得不好ArrayList就要進行一次擴容，而ArrayList底層數(shù)組擴容是一個既消耗時間又消耗空間的操作，所以綜合來看就知道選擇哪個類型的list
