前言

?ArrayList和LinkedList的主要區(qū)別在于它們的底層數(shù)據(jù)結(jié)構(gòu)、性能特點以及適用場景。?ArrayList和LinkedList從名字分析，他們一個是Array（動態(tài)數(shù)組）的數(shù)據(jù)結(jié)構(gòu)，一個是Linked（鏈表）的數(shù)據(jù)結(jié)構(gòu)，此外，他們兩個都是對List接口的實現(xiàn)。前者是數(shù)組隊列，相當(dāng)于動態(tài)數(shù)組；后者為雙向鏈表結(jié)構(gòu)，也可當(dāng)作堆棧、隊列、雙端隊列。

一、底層數(shù)據(jù)結(jié)構(gòu)

?ArrayList?：基于動態(tài)數(shù)組實現(xiàn)。它維護一個Object類型的數(shù)組來存儲元素，可以根據(jù)需要自動擴展容量。當(dāng)元素數(shù)量超過當(dāng)前容量時，ArrayList會進行擴容操作，通常是將現(xiàn)有元素復(fù)制到一個新的更大數(shù)組中?。?

?LinkedList?：基于雙向鏈表實現(xiàn)。每個節(jié)點包含存儲的元素、指向前一個節(jié)點的引用和指向下一個節(jié)點的引用。LinkedList不需要預(yù)先分配固定大小的空間，可以在鏈表的頭部或尾部靈活地添加或刪除元素?。

二、性能特點

2?.1?查詢性能?：

ArrayList?：通過索引直接訪問元素，查詢速度非常快，時間復(fù)雜度為O(1)。適合需要頻繁訪問特定?位置數(shù)據(jù)的場景?。

LinkedList?：由于需要遍歷鏈表來找到指定索引的元素，查詢速度較慢，時間復(fù)雜度為O(n)?。

2.2?添加和刪除性能?：

?ArrayList?：在列表中間插入或刪除元素時，需要移動后續(xù)的所有元素，時間復(fù)雜度為O(n)。因此，在列表中間進行添加或刪除操作時，LinkedList通常更快?。

LinkedList?：在頭部或尾部添加或刪除元素時，只需更改指針引用，時間復(fù)雜度為O(1)，因此在這些位置進行操作時更快?。

三、空間和耗時效率對比

從利用效率來看，ArrayList自由性較低，因為它需要手動的設(shè)置固定大小的變化，但是他的使用比較方便，只需要創(chuàng)建，然后添加數(shù)據(jù)，通過調(diào)用下標(biāo)進行使用；而LinkedList自由性較高，能夠動態(tài)的數(shù)據(jù)量的變化而變化，但是他不便于使用。

ArrayList主要的空間開銷在于需要在IList列表預(yù)留一定空間；而LinkedList主要空間開銷在于需要存儲節(jié)點信息以及結(jié)點指針信息。

ArrayList想要在指定位置插入或刪除元素時，主要耗時的是?System.arraycopy?動作，會移動 index 后面所有的元素；LinkedList 主耗時的是要先通過 for 循環(huán)找到 index，然后直接插入或刪除。這就導(dǎo)致了兩者并非一定誰快誰慢。?主要有兩個因素決定他們的效率，插入的數(shù)據(jù)量和插入的位置。

LinkedList需要更多的內(nèi)存，因為ArrayList的每個索引的位置是實際的數(shù)據(jù)，而LinkedList中的每個節(jié)點中存儲的是實際的數(shù)據(jù)和前后節(jié)點的位置。

四、ArrayList 擴容問題

ArrayList 使用一個內(nèi)置的數(shù)組來存儲元素，這個數(shù)組的起始容量是 10，當(dāng)數(shù)組需要增長時，新的容量按如下公式獲得：新容量=(舊容量*3)/2+1，也就是說每一次容量大概會增長50%。這就意味著，如果你有一個包含大量元素的 ArrayList 對象，那么最終將有很大的空間會被浪費掉，這個浪費是由ArrayList的工作方式本身造成的。如果沒有足夠的空間來存放新的元素，數(shù)組將不得不被重新進行分配以便能夠增加新的元素。對數(shù)組進行重新分配，將會導(dǎo)致性能急劇下降。

五、ArrayList隨機訪問比LinkedList快的原因

ArrayList從原理上就是數(shù)據(jù)結(jié)構(gòu)中的數(shù)組，也就是內(nèi)存中的一片空間，這意味著，當(dāng)我get(index)的時候，我可以根據(jù)數(shù)組的首地址+偏移量，直接計算出我想訪問的第index元素在內(nèi)存中的位置；而LinkedList可以簡單理解為數(shù)據(jù)結(jié)構(gòu)中的鏈表，在內(nèi)存中開辟的不是一段連續(xù)的空間，而是每個元素有一個元素和下一個元素地址這樣的內(nèi)存結(jié)構(gòu)，當(dāng)get(index)時，只能從首元素開始，依次獲取下一個元素的地址。上面已經(jīng)說過，用時間復(fù)雜度來表示的話，ArrayList的get(index)是O(1)，而LinkedList是O(n)。

我們編寫代碼對比測試，說明兩者的性能：

1. 定義抽象類，作為List接口的測試，并定義有測試方法

//定義內(nèi)部抽象類，作為List測試。
private abstract static class Tester {String name;int size;Tester(String name, int size) {this.name = name;this.size = size;}//定義抽象方法abstract void test(List a);}

2. 定義一個測試的數(shù)組,分別存儲獲取、遍歷、插入和刪除的方法

private static final int LOOP_COUNTS = 1000;private static Tester[] tests = {//一個測試數(shù)組，存儲get(隨機取)、iteration(順序遍歷)、insert(中間插入)、remove(隨機刪除)new Tester("get", 500) {void test(List a) {for (int i = 0; i < LOOP_COUNTS; i++) {for (int j = 0; j < a.size(); j++) {a.get(j);}}}},new Tester("iteration", 500) {void test(List a) {for (int i = 0; i < LOOP_COUNTS; i++) {Iterator it = a.iterator();while (it.hasNext()) {it.next();}}}},new Tester("insert", 2000) {void test(List a) {int half = a.size() / 2;String s = "test";ListIterator it = a.listIterator(half);for (int i = 0; i < size * 10; i++) {it.add(s);}}},new Tester("remove", 5000) {void test(List a) {ListIterator it = a.listIterator(3);while (it.hasNext()) {it.next();it.remove();}}}};

?3. 編寫測試方法

public static void test(List a) {//輸出測試的類名稱System.out.println("Testing for --" + a.getClass().getName());for (int i = 0; i < tests.length; i++) {fill(a, tests[i].size);//填充空集合System.out.print(tests[i].name);long t1 = System.currentTimeMillis();tests[i].test(a);//進行測試long t2 = System.currentTimeMillis();System.out.print("花費時間:" + (t2 - t1) + " ms ，");}}public static Collection fill(Collection c, int size) {for (int i = 0; i < size; i++) {c.add(Integer.toString(i));}return c;}

4. 調(diào)用ArrayList和LinkedList的方法

public static void main(String[] args) {test(new ArrayList());System.out.println();test(new LinkedList());}

?5. 運行結(jié)果

六、適用場景

?ArrayList?：適合需要頻繁訪問特定位置數(shù)據(jù)的場景，如排行榜、購物車列表等。由于擴容機制的存在，建議在創(chuàng)建時指定初始容量以減少擴容次數(shù)?。

?LinkedList?：適合需要頻繁在列表開頭、中間或末尾進行添加和刪除操作的場景。由于其鏈表結(jié)構(gòu)，插入和刪除操作更為高效?。

總之， 它們的適用場景：Array數(shù)組，查找快，插入刪除慢。 適用于頻繁查找和修改的場景。Linked鏈表，插入刪除快，查找修改慢。適用于頻繁添加和刪除的場景。