遍歷鏈表與數(shù)組，哪個(gè)效率高？因?yàn)镺（n）的內(nèi)涵不同，他們是寫(xiě)O（n）和讀O（n）。數(shù)組善于讀取，鏈表善于寫(xiě)入。寫(xiě)入前讀取位置。讀取場(chǎng)景：任意順序讀取，復(fù)雜度：數(shù)組o（1），鏈表o（n）。寫(xiě)入場(chǎng)景：按任

遍歷鏈表與數(shù)組，哪個(gè)效率高？

因?yàn)镺（n）的內(nèi)涵不同，他們是寫(xiě)O（n）和讀O（n）。

數(shù)組善于讀取，鏈表善于寫(xiě)入。

寫(xiě)入前讀取位置。

讀取場(chǎng)景：任意順序讀取，復(fù)雜度：數(shù)組o（1），鏈表o（n）。

寫(xiě)入場(chǎng)景：按任意順序?qū)懭耄恢脧?fù)雜度：數(shù)組o（1），鏈表o（n）；寫(xiě)入復(fù)雜度：數(shù)組o（n），鏈表o（1）。

在寫(xiě)入場(chǎng)景中，數(shù)組鏈表的復(fù)雜度是位置寫(xiě)入復(fù)雜度的總和，即O（n），但是寫(xiě)入速度比位置O（n）慢得多，并且具有相同表面的兩個(gè)O（n）的實(shí)際時(shí)間仍然少得多。因此，鏈表和數(shù)組的插入和刪除時(shí)間復(fù)雜度為O（n），鏈表寫(xiě)入效率高。

鏈表和數(shù)組的區(qū)別在哪里？

1. 數(shù)組中的數(shù)據(jù)按順序存儲(chǔ)在內(nèi)存中，鏈表則隨機(jī)存儲(chǔ)。要訪(fǎng)問(wèn)數(shù)組中的元素，可以通過(guò)下標(biāo)索引來(lái)訪(fǎng)問(wèn)它們，這相對(duì)比較快。如果插入鏈表，需要移動(dòng)很多元素，因此插入數(shù)組的效率很低，因?yàn)殒湵硎请S機(jī)存儲(chǔ)的，鏈表的插入和刪除效率很高（相對(duì)數(shù)組）。如果要訪(fǎng)問(wèn)鏈表中的某個(gè)元素，必須從鏈表的開(kāi)頭逐個(gè)遍歷，直到找到所需的元素。因此，鏈表的隨機(jī)存取效率低于數(shù)組。2遞歸算法：在函數(shù)或子進(jìn)程中直接或間接調(diào)用自己的算法。由于鏈表使用下一個(gè)指針來(lái)維護(hù)鏈表的結(jié)構(gòu)，因此其插入和刪除效率相對(duì)較高。再次插入和刪除時(shí)，不需要移動(dòng)以下數(shù)據(jù)。。但每次搜索都要從頂部節(jié)點(diǎn)遍歷，效率不高。數(shù)組使用下標(biāo)來(lái)維護(hù)數(shù)據(jù)，因此效率非常高。插入和刪除，需要將數(shù)據(jù)移到后面，效率不高。