先看網(wǎng)上結(jié)論：
1.ArrayList的底層是數(shù)組，根據(jù)下標(biāo)可以直接定位到元素的位置，這樣查找的時(shí)間復(fù)雜度就是O(1)，插入由于要移動(dòng)其他元素的下標(biāo)，所以增加刪除的復(fù)雜度是O（n）。
2.LinkList的底層是鏈表，查詢時(shí)需要從第一個(gè)元素一個(gè)一個(gè)的查到目標(biāo)索引，所以時(shí)間復(fù)雜度是O（n），而插入時(shí)只需要改變上一個(gè)元素的指向位置，所以時(shí)間復(fù)雜度是O（1）。
我們來驗(yàn)證下，這個(gè)結(jié)論是否屬實(shí)呢。
第一：我們先來測(cè)試一千萬條數(shù)據(jù)的順序插入
這個(gè)結(jié)論有點(diǎn)意外?。篈rrayList的性能比linkList差了四倍。這里的慢速是因?yàn)橐苿?dòng)其他元素的下表導(dǎo)致的嗎？其實(shí)不是，例子中的插入，是尾部插入，并不是隨機(jī)插入，也就是說先前的元素下表并不需要移動(dòng)，這里插入的耗時(shí)就是O（1）。
真是原因?qū)е马樞虿迦氡容^慢的原因是：ArrayList的擴(kuò)容機(jī)制，ArrayList的底層是數(shù)組，是數(shù)組就有大小，初始大小是10，負(fù)載因子是0.75，也就是一旦ArrayList的元素個(gè)數(shù)到達(dá)數(shù)據(jù)長(zhǎng)度就需要擴(kuò)容。擴(kuò)容的過程是，新建一個(gè)1.5倍的新空數(shù)組，然后將舊數(shù)組復(fù)制過去，期間，原始的hash值不重新計(jì)算，舊數(shù)組刪除。
結(jié)論：順序插入多條數(shù)據(jù)時(shí)，ArrayList的效率比LinkList慢很多，原因是ArrayList有擴(kuò)容機(jī)制，LinkList無擴(kuò)容
第二：我們測(cè)試隨機(jī)訪問
結(jié)果爆炸，LinkList的查詢效率遠(yuǎn)遠(yuǎn)低于ArrayList，簡(jiǎn)直天差地別啊，隨機(jī)訪問測(cè)試，ArrayList完勝，應(yīng)了網(wǎng)上的結(jié)論，而且不是差一點(diǎn)，而是差N倍
第三：我們測(cè)試隨機(jī)插入
哎哎哎，這不科學(xué)啊，為啥LinkList的耗時(shí)比ArrayList還高五倍呢？不是說好的LinkList的隨機(jī)插入與刪除效率要好于ArrayList嗎？
其實(shí)，LinkList的插入刪除效率O（1）的前提是，知道上一個(gè)元素節(jié)點(diǎn)的指針，關(guān)鍵是怎么知道上一個(gè)元素節(jié)點(diǎn)的指針呢？還是要從頭循環(huán)知道找到上一個(gè)節(jié)點(diǎn)，才能得知指針，這個(gè)尋找過程還是O（n）.這樣大家的時(shí)間復(fù)雜度都是O（n），為什么LinkList還是要慢呢？這里我認(rèn)識(shí)，是ArrList的下表移動(dòng)效率要高于指針的移動(dòng)效率，而且LinkList采取的指針移動(dòng)方式必然導(dǎo)致內(nèi)存碎片化，從而加劇內(nèi)存移動(dòng)的耗時(shí)。
