線性表順序存儲與鏈式存儲實現線性表的比較

時間上的比較

線性表的基本操作: 查詢, 插入, 刪除。

查詢:

數組順序存儲,直接通過索引值訪問每個元素, 實現了數組元素的隨機訪問。

鏈式存儲, 每次從頭結點或者尾結點開始依次查找。

如果線性表主要是查詢操作, 優先選擇順序存儲的線性表。

插入與刪除

數組順序實現的線性表, 在插入/刪除時,需要移動大量的元素。

鏈式存儲,只需要修改結點的前驅后續指針即可,不需要移動元素。

如果線性表經常用于插入/刪除操作, 優先選擇鏈式存儲實現的線性表。

空間比較

順序存儲, 預先分配一塊連續的存儲空間, 在使用過程中會出現閑置的空間。

鏈式存儲的空間是動態分配的, 不會浪費空間。

如果線性表的長度經常變化, 優先選擇鏈式存儲。

如果線性表的長度變化不大時, 優先選擇順序存儲, 因為鏈式存儲需要額外的空間存儲它前驅和后繼。