順序表與連結清單的差別

• 1.順序表存儲（典型的數組)
• 2.連結清單存儲
• 3.使用場景：

1.順序表存儲（典型的數組)

原理：順序表存儲是将資料元素放到一塊

連續的記憶體存儲空間

，相鄰資料元素的

存放位址也相鄰

（邏輯與實體統一）。

優點：

（1）空間使用率高。（局部性原理，連續存放，命中率高）

（2）存取速度高效，通過下标來直接存儲。

缺點：

（1）插入和删除比較慢，比如：插入或者删除一個元素時，整個表需要周遊移動元素來重新排一次順序。

（2）不可以增長長度，有空間限制,當需要存取的元素個數可能多于順序表的元素個數時,會出現”溢出”問題.當元素個數遠少于預先配置設定的空間時,空間浪費巨大。

時間性能 :查找 O(1) ,插入和删除O（n）。

2.連結清單存儲

原理：連結清單存儲是在程式運作過程中

動态的配置設定

空間，隻要存儲器還有空間，就不會發生存儲溢出問題，相鄰資料元素可随意存放，但所占存儲空間分兩部分，一部分存放結點值，另一部分存放表示結點關系間的指針。

優點：

（1）存取某個元素速度慢。

（2）插入和删除速度快，保留原有的實體順序，比如：插入或者删除一個元素時，隻需要改變指針指向即可。

（3）沒有空間限制,存儲元素的個數無上限,基本隻與記憶體空間大小有關.

缺點：

（1）占用額外的空間以存儲指針(浪費空間，不連續存放，malloc開辟，空間碎片多)

（2）查找速度慢，因為查找時，需要循環連結清單通路，需要從開始節點一個一個節點去查找元素通路。

時間性能 :查找 O(n) ,插入和删除O（1）。

3.使用場景：

*頻繁的查找卻很少的插入和删除操作可以用順序表存儲，堆排序,二分查找适宜用順序表.

*如果頻繁的插入和删除操作很少的查詢就可以使用連結清單存儲

*順序表适宜于做查找這樣的靜态操作；連結清單适宜于做插入、删除這樣的動态操作。

*若線性表長度變化不大，如果事先知道線性表的大緻長度，比如一年12月，一周就是星期一至星期日共七天，且其主要操作是查找，則采用順序表；若線性表長度變化較大或根本不知道多大時，且其主要操作是插入、删除，則采用連結清單，這樣可以不需要考慮存儲空間的大小問題