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

時(shí)間上的比較

線性表的基本操作: 查詢(xún), 插入, 刪除。

查詢(xún):

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

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

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

插入與刪除

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

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

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

空間比較

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

鏈?zhǔn)酱鎯?chǔ)的空間是動(dòng)態(tài)分配的, 不會(huì)浪費(fèi)空間。

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

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