數(shù)組的訪問效率為什么高于鏈表？

目前刷題到Day60后，過去10天集中強(qiáng)化復(fù)習(xí)這60天所學(xué)。反復(fù)揣摩舊知識(shí)，并從中理解出新的東西，也是很必要的，也是一種能力。

就拿我們最熟悉的數(shù)組來說吧，你想過為什么它的訪問效率高于鏈表等數(shù)據(jù)結(jié)構(gòu)嗎？書本上只告訴我們結(jié)論：數(shù)組的訪問效率更好，鮮有告訴我們?yōu)槭裁矗鼊e想獲得書作者本人對其的理解了。

答案倒還是其次。不知道大家在學(xué)習(xí)的時(shí)候提出過這個(gè)問題嗎？能提出這個(gè)問題說明你也蠻優(yōu)秀。實(shí)話說，這個(gè)問題在面試中也會(huì)常被問到，肯定有答不上來的候選者。

談?wù)勎业臏\見。

數(shù)組在內(nèi)存中是按照順序存儲(chǔ)的，每個(gè)元素出現(xiàn)順序與我們可見的index，也就是索引一一對應(yīng)。這就意味著，只要知道其中一個(gè)元素地址，便能在O(1)時(shí)間內(nèi)隨機(jī)訪問任意一個(gè)元素。

而這種能力以鏈表為代表的非順序存儲(chǔ)模型是無法具備的。我們都知道鏈表某個(gè)節(jié)點(diǎn)引用了前驅(qū)或后繼節(jié)點(diǎn)，因此它只能一次移動(dòng)一步，像蝸牛似的爬到想要訪問的節(jié)點(diǎn)。如果已知節(jié)點(diǎn)和待查找的節(jié)點(diǎn)中間間隔N個(gè)元素，它就得移動(dòng)N步。

綜上，數(shù)組能一步到位，鏈表N步到位，結(jié)論：數(shù)組隨機(jī)訪問能力強(qiáng)于鏈表。若有用，歡迎點(diǎn)贊或轉(zhuǎn)發(fā)支持。