數(shù)組和鏈表的區(qū)別，這個(gè)問題，不僅面試中經(jīng)常遇到，考研的同學(xué)也得掌握才行。

這兩個(gè)的區(qū)別，還得從他們?cè)趦?nèi)存里面的布局講起。

?

數(shù)組是一塊連續(xù)的內(nèi)存，這塊內(nèi)存可以在棧空間也可以在堆空間：

?

一般都會(huì)有個(gè)容量限制，比如：

int arr[5];

就表示數(shù)組有 5 個(gè)元素，在內(nèi)存中占 20 個(gè)字節(jié)。

?

而且為了方便使用，數(shù)組在存儲(chǔ)數(shù)據(jù)的時(shí)候盡量保持連續(xù)。

?

鏈表在內(nèi)存中不用連續(xù)，位置由系統(tǒng)隨機(jī)分配，所以這就需要某種機(jī)制能把各個(gè)數(shù)據(jù)串聯(lián)起來。

鏈表由一個(gè)一個(gè)結(jié)點(diǎn)組成，每個(gè)結(jié)點(diǎn)都分成數(shù)據(jù)域和指針域，指針域指向下一個(gè)結(jié)點(diǎn)。

這種結(jié)構(gòu)也決定了鏈表沒有容量限制，只要內(nèi)存夠用，就能保存更多的數(shù)據(jù)。

?

數(shù)組和鏈表的訪問方式也不一樣。

數(shù)組因其在內(nèi)存中連續(xù)排布，訪問的時(shí)候只要數(shù)組名加上數(shù)組下標(biāo)就能精確定位到指定的元素。

?

數(shù)組名本身表示數(shù)組首元素的地址，加上下標(biāo)，其實(shí)就是個(gè)偏移量，所以就訪問速度而言，數(shù)組的效率確實(shí)要高。

鏈表因?yàn)樵趦?nèi)存中排布不連續(xù)，所以不支持這種隨機(jī)訪問。要鎖定某個(gè)結(jié)點(diǎn)，必須得借助指針，一步一步向下移動(dòng)，結(jié)點(diǎn)越多，訪問的效率越低。

他倆的最大區(qū)別，還得是插入和刪除，尤其是針對(duì)開頭的插入和刪除操作。

假設(shè)都往第一個(gè)位置插入元素。

如果是數(shù)組，在空間還沒有滿的情況下，先要把后面的元素逐個(gè)向后移動(dòng)，然后把第一個(gè)位置騰出來，再把新元素放進(jìn)去。 所以數(shù)組里面的元素越多，插入的效率也就越低。

鏈表的插入方法完全不一樣，先來一個(gè)新結(jié)點(diǎn)，填上數(shù)據(jù)域和指針域，然后修改頭節(jié)點(diǎn)的指向關(guān)系，不管鏈表中有多少個(gè)結(jié)點(diǎn)，插入的步驟都是這么多。

所以在插入和刪除操作上，大部分情況下鏈表的效率要高于數(shù)組。

數(shù)組和鏈表在軟件開發(fā)中出現(xiàn)的場(chǎng)景很高，數(shù)組簡(jiǎn)單，鏈表更實(shí)用。

審核編輯：劉清