今天在網(wǎng)上沖浪，看到有文章說(shuō) LinkedList 的作者說(shuō)他自己都不用 LinkedList，我就特意去翻了翻他的推特，發(fā)現(xiàn)他確實(shí)說(shuō)過(guò)這話！

可能這就是大佬吧，我造輪子，但是我不用！或者這就是傳說(shuō)中的廚子不吃自己做的菜？

不扯了，言歸正傳。其實(shí)我個(gè)人覺(jué)得大佬說(shuō)好像是事實(shí)，因?yàn)樵跇I(yè)務(wù)上好像都用不到 LinkedList ，大多數(shù)場(chǎng)景下都是用 ArrayList 比較合適，我細(xì)數(shù)了下自己平日里的使用情況，真的都是 ArrayList 。

說(shuō)到這，可能有人不同意了，說(shuō)我可是看過(guò)面試題的，LinkedList 可是有它的優(yōu)勢(shì)的！

這題我也看過(guò)，沒(méi)記錯(cuò)的話應(yīng)該是：說(shuō)說(shuō) ArrayList 和 LinkedList 的之間區(qū)別？

我覺(jué)得這題可謂之為“八股文前三甲”，其實(shí)這題映射過(guò)來(lái)也就是關(guān)于數(shù)組與鏈表的比較。

只要你在網(wǎng)上看過(guò)這道面試題，你看到的答案必然是：

• 數(shù)組的隨機(jī)訪問(wèn)快，插入和刪除慢
• 鏈表的插入刪除快，隨機(jī)訪問(wèn)慢
• 頻繁增刪的情況下，用鏈表比較合適
• 在隨機(jī)查找多的情況下，用數(shù)組比較合適

問(wèn)題就出在鏈表的頻繁增刪這一點(diǎn)。如果單從增加查這三個(gè)方法的時(shí)間復(fù)雜度來(lái)看，確實(shí)如此，沒(méi)有錯(cuò)。

但是，在平時(shí)的使用上來(lái)說(shuō)，這個(gè)說(shuō)法就完全不成立！你想想，如果你要在鏈表中刪除某個(gè)元素，你首先得找到它啊！這個(gè)鏈表的查找可耗時(shí)的呀！

所以在實(shí)際使用的時(shí)候，如果你有頻繁的增刪，也不應(yīng)該用鏈表。

不信？我們來(lái)做個(gè)實(shí)驗(yàn)看看咯。


public?class?YesArrayLinkedBattle?{
????private?static?final?int?COUNT?=?100000;

????static?List?fillList(List?list)?{
????????for?(int?i?=?0;?i?????????????list.add(i);?//將list填滿，假裝我們?cè)跀?shù)據(jù)庫(kù)里得到這么多數(shù)據(jù)
????????}
????????return?list;
????}
????static?void?randomAdd(List?list,?String?listType)?{
????????long?t1?=?System.currentTimeMillis();
????????for?(int?i?=?0;?i?????????????list.add(ThreadLocalRandom.current().nextInt(0,COUNT),?i);
????????}
????????long?t2?=?System.currentTimeMillis();
????????System.out.println(listType? "隨機(jī)位置插入"? ?COUNT? ?"次耗時(shí)："? ?(t2-t1));
????}

????public?static?void?main(String[]?args)?{

????????randomAdd(fillList(new?ArrayList<>(COUNT)),?"數(shù)組");

????????randomAdd(fillList(new?LinkedList<>()),?"鏈表");

????}
}
這個(gè)實(shí)驗(yàn)很粗暴簡(jiǎn)單，但也很直觀，分別對(duì)被填滿數(shù)據(jù)的 ArrayList 和 LinkedList 執(zhí)行 10 萬(wàn)次隨機(jī)的插入操作，然后分別統(tǒng)計(jì)耗時(shí)。

執(zhí)行結(jié)果如下：

是吧，在隨機(jī)插入的情況下，鏈表不占優(yōu)勢(shì)反而大弱于數(shù)組！

所以說(shuō)對(duì)于鏈表的插入操作，不能只關(guān)注其插入的時(shí)間復(fù)雜度，也要算上查找到前節(jié)點(diǎn)的開(kāi)銷(xiāo)，因此不能武斷地說(shuō)：頻繁增刪的情況下，用鏈表比較合適

當(dāng)然，如果數(shù)據(jù)量很小的話，其實(shí)兩者都是差不多的，比如長(zhǎng)度都為 100 ，執(zhí)行 100 次，則耗時(shí)如下：

長(zhǎng)度都為 1000 ，執(zhí)行 1000 次，則耗時(shí)如下：

所以，在數(shù)據(jù)量不大且操作次數(shù)不多的情況其實(shí)不必過(guò)于糾結(jié)到底用哪個(gè)。但在數(shù)據(jù)量較大且對(duì)時(shí)延敏感的情況下，建議還是做好測(cè)試，不能平白的根據(jù)一些“網(wǎng)上結(jié)論”而下定論。

好了，暫時(shí)扯到這。記住下次去面試別直接八股文硬上，咱們要多點(diǎn)質(zhì)疑，加點(diǎn)個(gè)人思考，這樣會(huì)讓人覺(jué)得你更有東西。