鍊錶和陣列的差別有哪些

    陣列是線性結構，可直接索引，也就是要去第i個元素，a[i]即可。鍊錶也是線性結構，要取第i個元素，只要用指針往後遍歷i次就可。貌似鍊錶比數組還要麻煩些，而且效率低些。

    想到這些相同處中的一些細微的不同處，於是他們的真正不同處漸漸顯現了：鍊錶的效率為何比數組低些？先從兩者的初始化開始。陣列無需初始化，因為陣列的元素在記憶體的堆疊區，系統自動申請空間。而鍊錶的結點元素在記憶體的堆區，每個元素須手動申請空間，如malloc。也就是說數組是靜態分配內存，而鍊錶是動態分配內存。鍊錶如此麻煩為何還要用鍊錶呢？數組不能完全取代鍊錶嗎？回到這個問題只要想想我們當初是怎麼完成學生資訊管理系統的。為何那時候要用鍊錶？因為學生管理系統中的插入，刪除等操作都很靈活，而陣列則大小固定，也無法靈活高效的插入，刪除。因為堆操作靈活性更強。陣列每次插入一個元素就需要移動已有元素，而鍊錶元素在堆上，無需這麼麻煩。

    說了這麼多，數組和鍊錶的差異整理如下：

•     數組靜態分配內存，鍊錶動態分配內存；

##    數組在記憶體中連續，鍊錶不連續；
    數組元素在棧區，鍊錶元素在堆區；
    數組利用下標定位，時間複雜度為O(1)，鍊錶定位元素時間複雜度O(n)；
    數組插入或刪除元素的時間複雜度O(n) ，鍊錶的時間複雜度O(1)。

#######

以上是鍊錶和陣列的差別有哪些的詳細內容。更多資訊請關注PHP中文網其他相關文章！