順序表詳細內容：
【數據結構】線性表 順序表（動態、靜態分配，插入刪除查找基本操作）解析+完整代碼
單鏈表詳細內容：
【數據結構】單鏈表解析+完整代碼（插入、刪除、尾插法、頭插法、按值和按位查找、前插和后插）帶頭結點和不帶兩種實現

3.5 順序表和鏈表的對比

• 邏輯結構上

  • 相同：都屬于線性表，都是線性結構。

• 存儲結構上

  • 不同點：

    	順序表	鏈表
    優點	支持隨機存取、存儲密度高	離散空間分配方便，改變容量容易
    缺點	大量連續內存不方便，改變容量麻煩	不可隨機存取，存儲密度低

• 基本操作

  • 1.創建

    順序表：容易浪費內存。

    鏈表：方便拓展。

  • 2.銷毀操作

    順序表：修改Length=0，靜態分配系統自動回收空間，動態分配需要手動free。

    鏈表：依次free結點。

  • 3.增、刪

    順序表：需要將元素前移/后移，時間復雜度$O(n)$，開銷來自移動元素。

    鏈表：只$O(n)$，開銷主要來自查找目標元素。 代價更低。

  • 4.查找操作

    順序表：按位查找$O(1)$，按值查找$O(n)$。效率更高。

    鏈表：兩種查找都是$O(n)$。

• 如何選擇用鏈表or順序表？

  • 表長難估計，經常增、刪元素 ——鏈表。

  • 表長可估計，查詢操作多 ——順序表。