數(shù)組和鏈表有何區(qū)別

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

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

?

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

?

一般都會有個容量限制，比如：

int arr[5];

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

?

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

?

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

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

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

?

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

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

?

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

鏈表因為在內(nèi)存中排布不連續(xù)，所以不支持這種隨機訪問。要鎖定某個結(jié)點，必須得借助指針，一步一步向下移動，結(jié)點越多，訪問的效率越低。

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

假設都往第一個位置插入元素。

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

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

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

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

審核編輯：劉清