順序表和鏈表的比較

順序表和鏈表的比較

    順序表和鏈表各有短長在實際應用中究竟選用哪一種存儲結構呢？這要根據具體問題的要求和性質來決定通常有以下幾方面的考慮
┌───┬───────────────┬───────────────┐
│      │       　　順序表　　　       │　　       鏈表　　　         │
├─┬─┼───────────────┼───────────────┤
│基│分│靜態分配程序執行之前必須明確│動態分配只要內存空間尚有空閒│
│於│配│規定存儲規模若線性表長度n變 │就不會產生溢出因此當線性表│
│空│方│化較大則存儲規模難於預先確定│的長度變化較大難以估計其存儲│
│間│式│估計過大將造成空間浪費估計太│規模時以采用動態鏈表作為存儲│
│考│  │小又將使空間溢出機會增多    │結構為好                    │
│慮├─┼───────────────┼───────────────┤
│  │存│為當線性表的長度變化不大 │<                            │
│  │儲│易於事先確定其大小時為了節約│                              │
│  │密│存儲空間宜采用順序表作為存儲│                              │
│  │度│結構                        │                              │
├─┼─┼───────────────┼───────────────┤
│基│存│隨機存取結構對表中任一結點都│順序存取結構鏈表中的結點需│
│於│取│可在O（）時間內直接取得      │從頭指針起順著鏈掃描才能取得│
│時│方│線性表的操作主要是進行查找很│                              │
│間│法│少做插入和刪除操作時采用順序│                              │
│考│  │表做存儲結構為宜            │                              │
│慮├─┼───────────────┼───────────────┤
│  │插│在順序表中進行插入和刪除平均│在鏈表中的任何位置上進行插入和│
│  │入│要移動表中近一半的結點尤其是│刪除都只需要修改指針對於頻│
│  │刪│當每個結點的信息量較大時移動│繁進行插入和刪除的線性表宜采│
│  │除│結點的時間開銷就相當可觀    │用鏈表做存儲結構若表的插入和│
│  │操│                              │刪除主要發生在表的首尾兩端則│
│  │作│                              │采用尾指針表示的單循環鏈表為宜│
└─┴─┴───────────────┴───────────────┘

    存儲密度（Storage Density）是指結點數據本身所占的存儲量和整個結點結構所占的存儲量之比即

    存儲密度=（結點數據本身所占的存儲量）/（結點結構所占的存儲總量）

 

From:http://tw.wingwit.com/Article/program/sjjg/201311/22873.html