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

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

不扯了，言歸正傳。其實我個人覺得大佬說好像是事實，因為在業(yè)務(wù)上好像都用不到 LinkedList ，大多數(shù)場景下都是用 ArrayList 比較合適，我細數(shù)了下自己平日里的使用情況，真的都是 ArrayList 。

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

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

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

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

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

問題就出在鏈表的頻繁增刪這一點。如果單從增加查這三個方法的時間復(fù)雜度來看，確實如此，沒有錯。

但是，在平時的使用上來說，這個說法就完全不成立！你想想，如果你要在鏈表中刪除某個元素，你首先得找到它?。∵@個鏈表的查找可耗時的呀！

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

不信？我們來做個實驗看看咯。


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

????static?List?fillList(List?list)?{
????????for?(int?i?=?0;?i?????????????list.add(i);?//將list填滿，假裝我們在數(shù)據(jù)庫里得到這么多數(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? "隨機位置插入"? ?COUNT? ?"次耗時："? ?(t2-t1));
????}

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

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

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

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

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

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

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

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

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

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

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