2.4 順序表與鏈表的比較

本章前面部分介紹了線性表的兩種存儲結構：順序表和鏈表。順序存儲有如下優點。

（1）方法簡單，高級語言都提供有數組，實現容易。

（2）無須為表示線性表中元素的邏輯關系而額外增加存儲開銷。

（3）具有按元素序號隨機訪問的特點。

順序存儲的缺點如下。

（1）在順序表中進行插入、刪除操作時，需要順序移動元素（平均移動次數是線性表長度的一半），因此對長度較長的線性表操作效率較低。

（2）要預先分配足夠大的存儲空間，空間分配過大會造成浪費，過小又有可能導致一些操作（如插入）失敗。

順序表的優點就是鏈表的缺點，而其缺點則是鏈表的優點。在實際使用中究竟采用什么存儲結構呢？通常有如下3點考慮。

1.基于空間的考慮

順序表的存儲空間是靜態分配的，在程序執行之前必須明確規定它的存儲規模，也就是說對MaxSize要有合適的設定。因此，當線性表的長度變化較大，難以估計其存儲規模時，不宜采用順序表。鏈表無須事先估計存儲規模，但鏈表的存儲密度較低，存儲密度是指結點數據本身所占的存儲單元數和整個結點所占的存儲單元數的比。顯然，存儲密度越大，存儲空間的利用率就越高。順序表的存儲密度為1，而鏈表的存儲密度小于1。在鏈式存儲中，雙向鏈表的存儲密度又低于單鏈表的存儲密度。

因此，當線性表的長度變化不大，易于事先確定其大小時，為了節約存儲空間，宜采用順序表作為存儲結構。當線性表的長度變化較大，事先難以確定其大小時，應采用鏈式存儲結構。

2.基于時間的考慮

順序表可實現元素的隨機存取，對表中任意結點都可以在O(1)時間內直接存取，而鏈表中的結點，需從頭指針起順著鏈逐個結點移動才能存取。因此，若線性表的操作主要是進行查找，很少進行插入和刪除，則采用順序表為存儲結構較好。

在順序表中進行插入和刪除，元素的平均移動次數是線性表長度的一半，當每個結點的信息量較大時，移動結點的時間開銷就相當可觀。而在鏈表中進行插入和刪除，雖然也要查找插入位置，但所做的是比較操作，插入過程只需要修改指針。因此，對于頻繁進行插入和刪除的線性表，宜采用鏈表為存儲結構。

3.基于語言的考慮

各種高級語言都提供有數組，但不一定提供有指針，鏈表是基于指針的，所以鏈表的使用有時會受到高級語言的限制。

總之，兩種存儲結構各有利弊，究竟選擇哪種結構要根據實際問題的主要因素來考慮。