2.4　順序表與鏈表的比較

以上介紹了線性表的兩種存儲(chǔ)結(jié)構(gòu)：順序表和鏈表。順序表和鏈表各有其優(yōu)缺點(diǎn)，不能籠統(tǒng)地說哪種存儲(chǔ)結(jié)構(gòu)更好，只能根據(jù)實(shí)際問題的具體需要，并對(duì)各方面的優(yōu)缺點(diǎn)加以綜合分析比較，才能選擇出符合應(yīng)用需求的存儲(chǔ)結(jié)構(gòu)。以下從時(shí)間性能和空間性能兩方面對(duì)順序表和鏈表進(jìn)行比較。

1．時(shí)間性能方面

順序表是隨機(jī)存取結(jié)構(gòu)，完成按位置隨機(jī)訪問的運(yùn)算的時(shí)間復(fù)雜度為O(1)；鏈表不具有隨機(jī)訪問的特點(diǎn)，按位置訪問元素時(shí)只能從表頭開始依次遍歷鏈表，直至找到特定的位置，平均時(shí)間復(fù)雜度為O(n)。

對(duì)于鏈表，在確定插入或刪除的位置后，只需修改指針即可完成插入或刪除運(yùn)算，所需的時(shí)間復(fù)雜度為O(1)；順序表進(jìn)行插入或刪除操作時(shí)，需移動(dòng)近乎表長(zhǎng)一半的元素，平均時(shí)間復(fù)雜度為O(n)。尤其是當(dāng)線性表中元素個(gè)數(shù)較多時(shí)，移動(dòng)元素的時(shí)間開銷相當(dāng)可觀。

如上所述，若線性表需頻繁進(jìn)行插入和刪除操作，則宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。若線性表需頻繁查找卻很少進(jìn)行插入和刪除操作或其所做運(yùn)算和“數(shù)據(jù)元素在線性表中的位置”密切相關(guān)，則宜采用順序表作為存儲(chǔ)結(jié)構(gòu)。

2．空間性能方面

順序表需要預(yù)分配一定長(zhǎng)度的存儲(chǔ)空間，若存儲(chǔ)空間預(yù)分配過大，將導(dǎo)致存儲(chǔ)空間浪費(fèi)；若存儲(chǔ)空間預(yù)分配過小，將造成空間溢出問題。鏈表不需要預(yù)分配空間，只要有可用的內(nèi)存空間分配，鏈表中的元素個(gè)數(shù)就沒有限制。

綜上所述，當(dāng)線性表中元素個(gè)數(shù)變化較大或者未知時(shí)，應(yīng)盡量采用鏈表作為存儲(chǔ)結(jié)構(gòu)；當(dāng)線性表中元素個(gè)數(shù)變化不大，可事先確定線性表的大致長(zhǎng)度時(shí)，可采用順序表作為存儲(chǔ)結(jié)構(gòu)。