鏈結串列(Linked List)
鏈結串列(Linked List)介紹
- 由一組節點(Node)組成的有序串列
- 每個節點由資料欄和一個以上的鏈結欄(Link, Point)組成
- 鏈結欄指向其它Node的位址
- 串列結構宣告
- 特性:
- 各Node不一定佔用連結的記憶體空間
- 各Node的型態不一定相同
- 只支援循序存取(Sequential Access)
- 插入(Insert)/刪除(Delete) Node容易
- 種類:
- 單向鏈結串列(Single Link List)
- 環狀鏈結串列(Circular Link List)
- 雙向鏈結串列(Double Link List)
- 鏈結串列和陣列的比較
項目 鏈結串列 陣列 記憶體需求 不需連續的記憶體空間 需連續的記憶體空間 節點型態 各Node型態不需相同 各Node型態需相同 操作複雜度 插入、刪除都O(1) 插入、刪除都O(n) 空間配置 不需事先預留空間,可任意增刪 須事先宣告連續空間 資料共享 資料共享容易 資料共享不易 資料分割、連結 資料分割、連結容易 資料分割、連結不易 存取方式 只支援循序存取 可支援隨機及循序存取 存取速度 循序存取速度慢 循序存取速度快 可靠性 可靠性差 可靠性佳 額外指標空間 需額外的指標空間 不需額外的指標空間