數組和鏈表有何區別

數組和鏈表的區別，這個問題，不僅面試中經常遇到，考研的同學也得掌握才行。

這兩個的區別，還得從他們在內存里面的布局講起。

?

數組是一塊連續的內存，這塊內存可以在?？臻g也可以在堆空間：

?

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

int arr[5];

就表示數組有 5 個元素，在內存中占 20 個字節。

?

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

?

鏈表在內存中不用連續，位置由系統隨機分配，所以這就需要某種機制能把各個數據串聯起來。

鏈表由一個一個結點組成，每個結點都分成數據域和指針域，指針域指向下一個結點。

這種結構也決定了鏈表沒有容量限制，只要內存夠用，就能保存更多的數據。

?

數組和鏈表的訪問方式也不一樣。

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

?

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

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

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

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

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

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

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

數組和鏈表在軟件開發中出現的場景很高，數組簡單，鏈表更實用。

審核編輯：劉清