這是我的第?215?期分享

作者 | 王磊

來源 | Java中文社群（ID：javacn666）

轉(zhuǎn)載請聯(lián)系授權(quán)（微信ID：GG_Stone）

數(shù)組和鏈表是程序中常用的兩種數(shù)據(jù)結(jié)構(gòu)，也是面試中常考的面試題之一。然而對于很多人來說，只是模糊的記得二者的區(qū)別，可能還記得不一定對，并且每次到了面試的時候，都得把這些的概念拿出來背一遍才行，未免有些麻煩。而本文則會從執(zhí)行過程圖以及性能評測等方面入手，讓你更加深入的理解和記憶二者的區(qū)別，有了這次深入的學(xué)習(xí)之后，相信會讓你記憶深刻。

數(shù)組

在開始（性能評測）之前我們先來回顧一下，什么是數(shù)組？

數(shù)組的定義如下：

數(shù)組（Array）是由相同類型的元素（element）的集合所組成的數(shù)據(jù)結(jié)構(gòu)，分配一塊連續(xù)的內(nèi)存來存儲。利用元素的索引（index）可以計算出該元素對應(yīng)的存儲地址。

最簡單的數(shù)據(jù)結(jié)構(gòu)類型是一維數(shù)組。例如，索引為 0 到 9 的 32 位整數(shù)數(shù)組，可作為在存儲器地址 2000，2004，2008，...2036 中，存儲 10個 變量，因此索引為 i 的元素即在存儲器中的 2000+4×i 地址。數(shù)組第一個元素的存儲器地址稱為第一地址或基礎(chǔ)地址。

簡單來說，數(shù)組就是由一塊連續(xù)的內(nèi)存組成的數(shù)據(jù)結(jié)構(gòu)。這個概念中有一個關(guān)鍵詞“連續(xù)”，它反映了數(shù)組的一大特點，就是它必須是由一個連續(xù)的內(nèi)存組成的。

數(shù)組的數(shù)據(jù)結(jié)構(gòu)，如下圖所示：

數(shù)組添加的過程，如下圖所示：

數(shù)組的優(yōu)點

數(shù)組的“連續(xù)”特征決定了它的訪問速度很快，因為它是連續(xù)存儲的，所以這就決定了它的存儲位置就是固定的，因此它的訪問速度就很快。比如現(xiàn)在有 10 個房間是按照年齡順序入住的，當(dāng)我們知道第一房子住的是 20 歲的人之后，那么我們就知道了第二個房子是 21 歲的人，第五個房子是 24 歲的人......等等。

數(shù)組的缺點

禍兮福所倚，福兮禍所伏。數(shù)組的連續(xù)性既有優(yōu)點又有缺點，優(yōu)點上面已經(jīng)說了，而缺點它對內(nèi)存的要求比較高，必須要找到一塊連續(xù)的內(nèi)存才行。

數(shù)組的另一個缺點就是插入和刪除的效率比較慢，假如我們在數(shù)組的非尾部插入或刪除一個數(shù)據(jù)，那么就要移動之后的所有數(shù)據(jù)，這就會帶來一定的性能開銷，刪除的過程如下圖所示：

數(shù)組還有一個缺點，它的大小固定，不能動態(tài)拓展。

鏈表

鏈表是和數(shù)組互補的一種數(shù)據(jù)結(jié)構(gòu)，它的定義如下：

鏈表（Linked list）是一種常見的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是并不會按線性的順序存儲數(shù)據(jù)，而是在每一個節(jié)點里存到下一個節(jié)點的指針（Pointer）。由于不必須按順序存儲，鏈表在插入的時候可以達到 O(1) 的復(fù)雜度，比另一種線性表順序表快得多，但是查找一個節(jié)點或者訪問特定編號的節(jié)點則需要 O(n) 的時間，而順序表相應(yīng)的時間復(fù)雜度分別是 O(logn) 和 O(1)。

也就說鏈表是一個無需連續(xù)內(nèi)存存儲的數(shù)據(jù)結(jié)構(gòu)，鏈表的元素有兩個屬性，一個是元素的值，另一個是指針，此指針標(biāo)記了下一個元素的地址。

鏈表的數(shù)據(jù)結(jié)構(gòu)，如下圖所示：

鏈表添加的過程，如下圖所示：

鏈表刪除的過程，如下圖所示：

鏈表分類

鏈表主要分為以下幾類：

• 單向鏈表

• 雙向鏈表

• 循環(huán)鏈表

單向鏈表

單向鏈表中包含兩個域，一個信息域和一個指針域。這個鏈接指向列表中的下一個節(jié)點，而最后一個節(jié)點則指向一個空值，我們上面所展示的鏈表就是單向鏈表。

雙向鏈表

雙向鏈表也叫雙鏈表，雙向鏈表中不僅有指向后一個節(jié)點的指針，還有指向前一個節(jié)點的指針，這樣可以從任何一個節(jié)點訪問前一個節(jié)點，當(dāng)然也可以訪問后一個節(jié)點，以至整個鏈表。

雙向鏈表的結(jié)構(gòu)如下圖所示：

循環(huán)鏈表

循環(huán)鏈表中第一個節(jié)點之前就是最后一個節(jié)點，反之亦然。循環(huán)鏈表的無邊界使得在這樣的鏈表上設(shè)計算法會比普通鏈表更加容易。

循環(huán)鏈表的結(jié)構(gòu)如下圖所示：

為什么會有單、雙鏈表之分？

有人可能會問，既然已經(jīng)有單向鏈表了，那為什么還要雙向鏈表呢？雙向鏈表有什么優(yōu)勢呢？

這個就要從鏈表的刪除說起了，如果單向鏈表要刪除元素的話，不但要找到刪除的節(jié)點，還要找到刪除節(jié)點的上一個節(jié)點（通常稱之為前驅(qū)），因為需要變更上一個節(jié)點中 next 的指針，但又因為它是單向鏈表，所以在刪除的節(jié)點中并沒有存儲上一個節(jié)點的相關(guān)信息，那么我們就需要再查詢一遍鏈表以找到上一個節(jié)點，這樣就帶來了一定的性能問題，所以就有了雙向鏈表。

鏈表優(yōu)點

鏈表的優(yōu)點大致可分為以下三個：

鏈表對內(nèi)存的利用率比較高，無需連續(xù)的內(nèi)存空間，即使有內(nèi)存碎片，也不影響鏈表的創(chuàng)建；

鏈表的插入和刪除的速度很快，無需像數(shù)組一樣需要移動大量的元素；

鏈表大小不固定，可以很方便的進行動態(tài)擴展。

鏈表缺點

鏈表的主要缺點是不能隨機查找，必須從第一個開始遍歷，查找效率比較低，鏈表查詢的時間復(fù)雜度是 O(n)。

性能評測

了解了數(shù)組和鏈表的基礎(chǔ)知識之后，接下來我們正式進入性能評測環(huán)節(jié)。

在正式開始之前，我們先來明確一下測試目標(biāo)，我們需要測試的點其實只有 6 個：

• 從頭部/中間部分/尾部進行添加操作的性能測試；

• 從頭部/中間部分/尾部開始查詢的性能測試。

因為添加操作和刪除操作在執(zhí)行時間層面基本是一致的，比如數(shù)組添加需要移動后面的元素，刪除也同樣是移動后面的元素；而鏈表也是如此，添加和刪除都是改變自身和相連節(jié)點的信息，因此我們就把添加和刪除的測試合二為一，用添加操作來進行測試。

測試說明：

在 Java 語言中，數(shù)組的代表為 ArrayList，而鏈表的代表為 LinkedList，因此我們就用這兩個對象來進行測試；

本文我們將使用 Oracle 官方推薦 JMH 框架來進行測試，點擊查看更多關(guān)于 JMH 的內(nèi)容；

本文測試環(huán)境是 JDK 1.8、MacMini、Idea 2020.1。

1.頭部添加性能測試

import?org.openjdk.jmh.annotations.*; import?org.openjdk.jmh.infra.Blackhole; import?org.openjdk.jmh.runner.Runner; import?org.openjdk.jmh.runner.RunnerException; import?org.openjdk.jmh.runner.options.Options; import?org.openjdk.jmh.runner.options.OptionsBuilder;import?java.util.ArrayList; import?java.util.LinkedList; import?java.util.concurrent.TimeUnit;@BenchmarkMode(Mode.AverageTime)?//?測試完成時間 @OutputTimeUnit(TimeUnit.NANOSECONDS) @Warmup(iterations?=?2,?time?=?1,?timeUnit?=?TimeUnit.SECONDS)?//?預(yù)熱次數(shù)和時間 @Measurement(iterations?=?5,?time?=?5,?timeUnit?=?TimeUnit.SECONDS)?//?測試次數(shù)和時間 @Fork(1)?//?fork?1?個線程 @State(Scope.Thread) public?class?ArrayOptimizeTest?{private?static?final?int?maxSize?=?1000;?//?測試循環(huán)次數(shù)private?static?final?int?operationSize?=?100;?//?操作次數(shù)private?static?ArrayList<Integer>?arrayList;private?static?LinkedList<Integer>?linkedList;public?static?void?main(String[]?args)?throws?RunnerException?{//?啟動基準(zhǔn)測試Options?opt?=?new?OptionsBuilder().include(ArrayOptimizeTest.class.getSimpleName())?//?要導(dǎo)入的測試類.build();new?Runner(opt).run();?//?執(zhí)行測試}@Setuppublic?void?init()?{//?啟動執(zhí)行事件arrayList?=?new?ArrayList<Integer>();linkedList?=?new?LinkedList<Integer>();for?(int?i?=?0;?i?<?maxSize;?i++)?{arrayList.add(i);linkedList.add(i);}}@Benchmarkpublic?void?addArrayByFirst(Blackhole?blackhole)?{for?(int?i?=?0;?i?<?+operationSize;?i++)?{arrayList.add(i,?i);}//?為了避免?JIT?忽略未被使用的結(jié)果計算blackhole.consume(arrayList);}@Benchmarkpublic?void?addLinkedByFirst(Blackhole?blackhole)?{for?(int?i?=?0;?i?<?+operationSize;?i++)?{linkedList.add(i,?i);}//?為了避免?JIT?忽略未被使用的結(jié)果計算blackhole.consume(linkedList);} }

從以上代碼可以看出，在測試之前，我們先將 ArrayList 和 LinkedList 進行數(shù)據(jù)初始化，再從頭部開始添加 100 個元素，執(zhí)行結(jié)果如下：

從以上結(jié)果可以看出，LinkedList 的平均執(zhí)行（完成）時間比 ArrayList 平均執(zhí)行時間快了約 216 倍。

2.中間添加性能測試

import?org.openjdk.jmh.annotations.*; import?org.openjdk.jmh.infra.Blackhole; import?org.openjdk.jmh.runner.Runner; import?org.openjdk.jmh.runner.RunnerException; import?org.openjdk.jmh.runner.options.Options; import?org.openjdk.jmh.runner.options.OptionsBuilder;import?java.util.ArrayList; import?java.util.LinkedList; import?java.util.concurrent.TimeUnit;@BenchmarkMode(Mode.AverageTime)?//?測試完成時間 @OutputTimeUnit(TimeUnit.NANOSECONDS) @Warmup(iterations?=?2,?time?=?1,?timeUnit?=?TimeUnit.SECONDS)?//?預(yù)熱次數(shù)和時間 @Measurement(iterations?=?5,?time?=?5,?timeUnit?=?TimeUnit.SECONDS)?//?測試次數(shù)和時間 @Fork(1)?//?fork?1?個線程 @State(Scope.Thread) public?class?ArrayOptimizeTest?{private?static?final?int?maxSize?=?1000;?//?測試循環(huán)次數(shù)private?static?final?int?operationSize?=?100;?//?操作次數(shù)private?static?ArrayList<Integer>?arrayList;private?static?LinkedList<Integer>?linkedList;public?static?void?main(String[]?args)?throws?RunnerException?{//?啟動基準(zhǔn)測試Options?opt?=?new?OptionsBuilder().include(ArrayOptimizeTest.class.getSimpleName())?//?要導(dǎo)入的測試類.build();new?Runner(opt).run();?//?執(zhí)行測試}@Setuppublic?void?init()?{//?啟動執(zhí)行事件arrayList?=?new?ArrayList<Integer>();linkedList?=?new?LinkedList<Integer>();for?(int?i?=?0;?i?<?maxSize;?i++)?{arrayList.add(i);linkedList.add(i);}}@Benchmarkpublic?void?addArrayByMiddle(Blackhole?blackhole)?{int?startCount?=?maxSize?/?2;?//?計算中間位置//?中間部分進行插入for?(int?i?=?startCount;?i?<?(startCount?+?operationSize);?i++)?{arrayList.add(i,?i);}//?為了避免?JIT?忽略未被使用的結(jié)果計算blackhole.consume(arrayList);}@Benchmarkpublic?void?addLinkedByMiddle(Blackhole?blackhole)?{int?startCount?=?maxSize?/?2;?//?計算中間位置//?中間部分進行插入for?(int?i?=?startCount;?i?<?(startCount?+?operationSize);?i++)?{linkedList.add(i,?i);}//?為了避免?JIT?忽略未被使用的結(jié)果計算blackhole.consume(linkedList);} }

從以上代碼可以看出，在測試之前，我們先將 ArrayList?和 LinkedList?進行數(shù)據(jù)初始化，再從中間開始添加 100 個元素，執(zhí)行結(jié)果如下：

從上述結(jié)果可以看出，LinkedList的平均執(zhí)行時間比 ArrayList平均執(zhí)行時間快了約 54 倍。

3.尾部添加性能測試

import?org.openjdk.jmh.annotations.*; import?org.openjdk.jmh.infra.Blackhole; import?org.openjdk.jmh.runner.Runner; import?org.openjdk.jmh.runner.RunnerException; import?org.openjdk.jmh.runner.options.Options; import?org.openjdk.jmh.runner.options.OptionsBuilder;import?java.util.ArrayList; import?java.util.LinkedList; import?java.util.concurrent.TimeUnit;@BenchmarkMode(Mode.AverageTime)?//?測試完成時間 @OutputTimeUnit(TimeUnit.NANOSECONDS) @Warmup(iterations?=?2,?time?=?1,?timeUnit?=?TimeUnit.SECONDS)?//?預(yù)熱次數(shù)和時間 @Measurement(iterations?=?5,?time?=?5,?timeUnit?=?TimeUnit.SECONDS)?//?測試次數(shù)和時間 @Fork(1)?//?fork?1?個線程 @State(Scope.Thread) public?class?ArrayOptimizeTest?{private?static?final?int?maxSize?=?1000;?//?測試循環(huán)次數(shù)private?static?final?int?operationSize?=?100;?//?操作次數(shù)private?static?ArrayList<Integer>?arrayList;private?static?LinkedList<Integer>?linkedList;public?static?void?main(String[]?args)?throws?RunnerException?{//?啟動基準(zhǔn)測試Options?opt?=?new?OptionsBuilder().include(ArrayOptimizeTest.class.getSimpleName())?//?要導(dǎo)入的測試類.build();new?Runner(opt).run();?//?執(zhí)行測試}@Setuppublic?void?init()?{//?啟動執(zhí)行事件arrayList?=?new?ArrayList<Integer>();linkedList?=?new?LinkedList<Integer>();for?(int?i?=?0;?i?<?maxSize;?i++)?{arrayList.add(i);linkedList.add(i);}}@Benchmarkpublic?void?addArrayByEnd(Blackhole?blackhole)?{int?startCount?=?maxSize?-?1?-?operationSize;for?(int?i?=?startCount;?i?<?(maxSize?-?1);?i++)?{arrayList.add(i,?i);}//?為了避免?JIT?忽略未被使用的結(jié)果計算blackhole.consume(arrayList);}@Benchmarkpublic?void?addLinkedByEnd(Blackhole?blackhole)?{int?startCount?=?maxSize?-?1?-?operationSize;for?(int?i?=?startCount;?i?<?(maxSize?-?1);?i++)?{linkedList.add(i,?i);}//?為了避免?JIT?忽略未被使用的結(jié)果計算blackhole.consume(linkedList);} }

以上程序的執(zhí)行結(jié)果為：

從上述結(jié)果可以看出，LinkedList 的平均執(zhí)行時間比 ArrayList 平均執(zhí)行時間快了約 32 倍。

4.頭部查詢性能評測

import?org.openjdk.jmh.annotations.*; import?org.openjdk.jmh.runner.Runner; import?org.openjdk.jmh.runner.RunnerException; import?org.openjdk.jmh.runner.options.Options; import?org.openjdk.jmh.runner.options.OptionsBuilder;import?java.util.ArrayList; import?java.util.LinkedList; import?java.util.concurrent.TimeUnit;@BenchmarkMode(Mode.AverageTime)?//?測試完成時間 @OutputTimeUnit(TimeUnit.NANOSECONDS) @Warmup(iterations?=?2,?time?=?1,?timeUnit?=?TimeUnit.SECONDS)?//?預(yù)熱次數(shù)和時間 @Measurement(iterations?=?5,?time?=?5,?timeUnit?=?TimeUnit.SECONDS)?//?測試次數(shù)和時間 @Fork(1)?//?fork?1?個線程 @State(Scope.Thread) public?class?ArrayOptimizeTest?{private?static?final?int?maxSize?=?1000;?//?測試循環(huán)次數(shù)private?static?final?int?operationSize?=?100;?//?操作次數(shù)private?static?ArrayList<Integer>?arrayList;private?static?LinkedList<Integer>?linkedList;public?static?void?main(String[]?args)?throws?RunnerException?{//?啟動基準(zhǔn)測試Options?opt?=?new?OptionsBuilder().include(ArrayOptimizeTest.class.getSimpleName())?//?要導(dǎo)入的測試類.build();new?Runner(opt).run();?//?執(zhí)行測試}@Setuppublic?void?init()?{//?啟動執(zhí)行事件arrayList?=?new?ArrayList<Integer>();linkedList?=?new?LinkedList<Integer>();for?(int?i?=?0;?i?<?maxSize;?i++)?{arrayList.add(i);linkedList.add(i);}}@Benchmarkpublic?void?findArrayByFirst()?{for?(int?i?=?0;?i?<?operationSize;?i++)?{arrayList.get(i);}}@Benchmarkpublic?void?findLinkedyByFirst()?{?for?(int?i?=?0;?i?<?operationSize;?i++)?{linkedList.get(i);}} }

以上程序的執(zhí)行結(jié)果為：

從上述結(jié)果可以看出，從頭部查詢 100 個元素時 ArrayList 的平均執(zhí)行時間比 LinkedList 平均執(zhí)行時間快了約 1990 倍。

5.中間查詢性能評測

import?org.openjdk.jmh.annotations.*; import?org.openjdk.jmh.infra.Blackhole; import?org.openjdk.jmh.runner.Runner; import?org.openjdk.jmh.runner.RunnerException; import?org.openjdk.jmh.runner.options.Options; import?org.openjdk.jmh.runner.options.OptionsBuilder;import?java.util.ArrayList; import?java.util.LinkedList; import?java.util.concurrent.TimeUnit;@BenchmarkMode(Mode.AverageTime)?//?測試完成時間 @OutputTimeUnit(TimeUnit.NANOSECONDS) @Warmup(iterations?=?2,?time?=?1,?timeUnit?=?TimeUnit.SECONDS)?//?預(yù)熱次數(shù)和時間 @Measurement(iterations?=?5,?time?=?5,?timeUnit?=?TimeUnit.SECONDS)?//?測試次數(shù)和時間 @Fork(1)?//?fork?1?個線程 @State(Scope.Thread) public?class?ArrayOptimizeTest?{private?static?final?int?maxSize?=?1000;?//?測試循環(huán)次數(shù)private?static?final?int?operationSize?=?100;?//?操作次數(shù)private?static?ArrayList<Integer>?arrayList;private?static?LinkedList<Integer>?linkedList;public?static?void?main(String[]?args)?throws?RunnerException?{//?啟動基準(zhǔn)測試Options?opt?=?new?OptionsBuilder().include(ArrayOptimizeTest.class.getSimpleName())?//?要導(dǎo)入的測試類.build();new?Runner(opt).run();?//?執(zhí)行測試}@Setuppublic?void?init()?{//?啟動執(zhí)行事件arrayList?=?new?ArrayList<Integer>();linkedList?=?new?LinkedList<Integer>();for?(int?i?=?0;?i?<?maxSize;?i++)?{arrayList.add(i);linkedList.add(i);}}@Benchmarkpublic?void?findArrayByMiddle()?{?int?startCount?=?maxSize?/?2;int?endCount?=?startCount?+?operationSize;for?(int?i?=?startCount;?i?<?endCount;?i++)?{arrayList.get(i);}}@Benchmarkpublic?void?findLinkedyByMiddle()?{?int?startCount?=?maxSize?/?2;int?endCount?=?startCount?+?operationSize;for?(int?i?=?startCount;?i?<?endCount;?i++)?{linkedList.get(i);}} }

以上程序的執(zhí)行結(jié)果為：

從上述結(jié)果可以看出，從中間查詢 100 個元素時 ArrayList 的平均執(zhí)行時間比 LinkedList 平均執(zhí)行時間快了約 28089 倍，真是恐怖。

6.尾部查詢性能評測

import?org.openjdk.jmh.annotations.*; import?org.openjdk.jmh.runner.Runner; import?org.openjdk.jmh.runner.RunnerException; import?org.openjdk.jmh.runner.options.Options; import?org.openjdk.jmh.runner.options.OptionsBuilder;import?java.util.ArrayList; import?java.util.LinkedList; import?java.util.concurrent.TimeUnit;@BenchmarkMode(Mode.AverageTime)?//?測試完成時間 @OutputTimeUnit(TimeUnit.NANOSECONDS) @Warmup(iterations?=?2,?time?=?1,?timeUnit?=?TimeUnit.SECONDS)?//?預(yù)熱次數(shù)和時間 @Measurement(iterations?=?5,?time?=?5,?timeUnit?=?TimeUnit.SECONDS)?//?測試次數(shù)和時間 @Fork(1)?//?fork?1?個線程 @State(Scope.Thread) public?class?ArrayOptimizeTest?{private?static?final?int?maxSize?=?1000;?//?測試循環(huán)次數(shù)private?static?final?int?operationSize?=?100;?//?操作次數(shù)private?static?ArrayList<Integer>?arrayList;private?static?LinkedList<Integer>?linkedList;public?static?void?main(String[]?args)?throws?RunnerException?{//?啟動基準(zhǔn)測試Options?opt?=?new?OptionsBuilder().include(ArrayOptimizeTest.class.getSimpleName())?//?要導(dǎo)入的測試類.build();new?Runner(opt).run();?//?執(zhí)行測試}@Setuppublic?void?init()?{//?啟動執(zhí)行事件arrayList?=?new?ArrayList<Integer>();linkedList?=?new?LinkedList<Integer>();for?(int?i?=?0;?i?<?maxSize;?i++)?{arrayList.add(i);linkedList.add(i);}}@Benchmarkpublic?void?findArrayByEnd()?{for?(int?i?=?(maxSize?-?operationSize);?i?<?maxSize;?i++)?{arrayList.get(i);}}@Benchmarkpublic?void?findLinkedyByEnd()?{?for?(int?i?=?(maxSize?-?operationSize);?i?<?maxSize;?i++)?{linkedList.get(i);}} }

以上程序的執(zhí)行結(jié)果為：

從上述結(jié)果可以看出，從尾部查詢 100 個元素時 ArrayList 的平均執(zhí)行時間比 LinkedList 平均執(zhí)行成時間快了約 1839 倍。

7.擴展添加測試

接下來我們再來測試一下，正常情況下我們從頭開始添加數(shù)組和鏈表的性能對比，測試代碼如下：

import?org.openjdk.jmh.annotations.*; import?org.openjdk.jmh.infra.Blackhole; import?org.openjdk.jmh.runner.Runner; import?org.openjdk.jmh.runner.RunnerException; import?org.openjdk.jmh.runner.options.Options; import?org.openjdk.jmh.runner.options.OptionsBuilder;import?java.util.ArrayList; import?java.util.LinkedList; import?java.util.concurrent.TimeUnit;@BenchmarkMode(Mode.AverageTime)?//?測試完成時間 @OutputTimeUnit(TimeUnit.NANOSECONDS) @Warmup(iterations?=?2,?time?=?1,?timeUnit?=?TimeUnit.SECONDS)?//?預(yù)熱次數(shù)和時間 @Measurement(iterations?=?5,?time?=?5,?timeUnit?=?TimeUnit.SECONDS)?//?測試次數(shù)和時間 @Fork(1)?//?fork?1?個線程 @State(Scope.Thread) public?class?ArrayOptimizeTest?{private?static?final?int?maxSize?=?1000;?//?測試循環(huán)次數(shù)private?static?ArrayList<Integer>?arrayList;private?static?LinkedList<Integer>?linkedList;public?static?void?main(String[]?args)?throws?RunnerException?{//?啟動基準(zhǔn)測試Options?opt?=?new?OptionsBuilder().include(ArrayOptimizeTest.class.getSimpleName())?//?要導(dǎo)入的測試類.build();new?Runner(opt).run();?//?執(zhí)行測試}@Benchmarkpublic?void?addArray(Blackhole?blackhole)?{?//?中間刪數(shù)組表arrayList?=?new?ArrayList<Integer>();for?(int?i?=?0;?i?<?maxSize;?i++)?{arrayList.add(i);}//?為了避免?JIT?忽略未被使用的結(jié)果計算blackhole.consume(arrayList);}@Benchmarkpublic?void?addLinked(Blackhole?blackhole)?{?//?中間刪除鏈表linkedList?=?new?LinkedList<Integer>();for?(int?i?=?0;?i?<?maxSize;?i++)?{linkedList.add(i);}//?為了避免?JIT?忽略未被使用的結(jié)果計算blackhole.consume(linkedList);} }

以上程序的執(zhí)行結(jié)果為：

接下來，我們將添加的次數(shù)調(diào)至 1w，測試結(jié)果如下：

最后，我們再將添加次數(shù)調(diào)至 10w，測試結(jié)果如下：

從以上結(jié)果可以看出在正常情況下，從頭部依次開始添加元素時，他們性能差別不大。

總結(jié)

本文我們介紹了數(shù)組的概念以及它的優(yōu)缺點，同時還介紹了單向鏈表、雙向鏈表及循環(huán)鏈表的概念以及鏈表的優(yōu)缺點。我們在最后的評測中可以看出，當(dāng)我們正常從頭部依次添加元素時，鏈表和數(shù)組的性能差不不大。但當(dāng)數(shù)據(jù)初始化完成之后，我們再進行插入操作時，尤其是從頭部插入時，因為數(shù)組要移動之后的所有元素，因此性能要比鏈表低很多；但在查詢時性能剛好相反，因為鏈表要遍歷查詢，并且 LinkedList?是雙向鏈表，所以在中間查詢時性能要比數(shù)組查詢慢了上萬倍（查詢 100 個元素），而兩頭查詢（首部和尾部）時，鏈表也比數(shù)組慢了將近 1000 多倍（查詢 100 個元素），因此在查詢比較多的場景中，我們要盡量使用數(shù)組，而在添加和刪除操作比較多時，我們應(yīng)該使用鏈表結(jié)構(gòu)。

數(shù)組和鏈表的操作時間復(fù)雜度，如下表所示：

數(shù)組鏈表

查詢	O(1)	O(n)
插入	O(n)	O(1)
刪除	O(n)	O(1)

最后的話原創(chuàng)不易，用心寫好每篇文章，若能看出來，請給我一個「在看」鼓勵吧。往期推薦

輕松學(xué)算法的秘密！可視化算法網(wǎng)站匯總！(附動圖)

50種Java編程技巧，越早知道越好！(建議收藏)

關(guān)注下方二維碼，每一天都有干貨！

點亮“在看”，助我寫出更多好文！

總結(jié)

以上是生活随笔為你收集整理的链表竟然比数组慢了1000多倍？(动图+性能评测)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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