線性表順序存儲與鏈?zhǔn)酱鎯?shí)現(xiàn)線性表的比較

時間上的比較

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

查詢:

數(shù)組順序存儲,直接通過索引值訪問每個元素, 實(shí)現(xiàn)了數(shù)組元素的隨機(jī)訪問。

鏈?zhǔn)酱鎯? 每次從頭結(jié)點(diǎn)或者尾結(jié)點(diǎn)開始依次查找。

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

插入與刪除

數(shù)組順序?qū)崿F(xiàn)的線性表, 在插入/刪除時,需要移動大量的元素。

鏈?zhǔn)酱鎯?只需要修改結(jié)點(diǎn)的前驅(qū)后續(xù)指針即可,不需要移動元素。

如果線性表經(jīng)常用于插入/刪除操作, 優(yōu)先選擇鏈?zhǔn)酱鎯?shí)現(xiàn)的線性表。

空間比較

順序存儲, 預(yù)先分配一塊連續(xù)的存儲空間, 在使用過程中會出現(xiàn)閑置的空間。

鏈?zhǔn)酱鎯Φ目臻g是動態(tài)分配的, 不會浪費(fèi)空間。

如果線性表的長度經(jīng)常變化, 優(yōu)先選擇鏈?zhǔn)酱鎯Α?/p>

如果線性表的長度變化不大時, 優(yōu)先選擇順序存儲, 因?yàn)殒準(zhǔn)酱鎯π枰~外的空間存儲它前驅(qū)和后繼。