由於是個人的學習筆記，因此有可能存在錯誤，若有發現錯誤之處煩請糾正或者一起討論！
連結串列(Linked list)
分為單向與雙向連結串列。
單向連結串列
概念圖如下圖所示
- 由一組節點(Node)組成的有序串列。
- 每個節點有
資料欄(Data)與一個連結欄(Pointer)組成。 連結欄(Pointer)指向其它節點(Node)的位置。- 以Null來代表Linked list的終點。
- 各節點之間並不一定占用連續的Memory空間
- 各節點的型態不一定相同
- 插入節點、刪除節點方便(因為只改變指標)
- 僅支援循序存取(Sequential Access)，不支援隨機存取(Random Access)
- 可任意(動態)增加、刪除空間
陣列(Array)與連結串列(Linked list)比較
| 陣列(Array) | 連結串列(Linked list) |
|---|---|
| 占用連續的記憶體空間 | 可以非連續 |
| 各元素型態皆相同 | 各節點型態不必一定相同 |
| 新增/刪除資料很麻煩，費 O(n) (須挪移元素) | 新增/刪除資料較簡單，花費 O(1)(只更改指標) |
| 串列分裂、合併較難 | 串列分裂、合併容易 |
| 須事先宣告連續空間 | 不需預留空間 |
| 可支援隨機與循序存取 | 只能循序存取(因為必須先讀取指標) |
| 可靠性佳 | 可靠性差(因為指標斷裂，資料就遺失) |
| 沒有額外的Link空間需求 | 需要額外的Link空間需求 |
陣列(Array)優點
- random access：只要利用index即可在O(1)時間對Array的資料做存取。
- 較Linked list為節省記憶體空間：因為Linked list需要多一個pointer來記錄下一個node的記憶體位置。
連結串列(Linked list)優點
- 新增/刪除資料較Array簡單，只要對O(1)個node(所有與欲新增/刪除的node有pointer相連的node)調整pointer即可，不需要如同Array般搬動其餘元素。
- 若是在Linked list的「開頭」新增node，只要O(1)。
- 若要刪除特定node，或者在特定位置新增node，有可能需要先執行O(N)的「搜尋」。
動態記憶體配置
動態記憶體配置(Dynamical Memory Allocation)主要是利用連結串列的方法來解決一些無法事先預測處理資料多寡的問題。
【定義】
動態記憶體配置是在等到執行階段，才向作業系統要求配置所需的記憶體空間。而靜態記憶體配置則是編譯階段時就配置記憶體空間。
靜態與動態資料結構
在靜態資料結構中，由於資料所佔用的空間大小及資料數目要事先宣告，因此，在執行時，空間的大小及資料數目是不會改變的(因為利用陣列結構)。
而在動態資料結構中，資料所佔用之空間大小及資料數目不必事先宣告，在執行時視實際需要而動態的增加或減少(因為利用串列結構)。
Linked list 時間複雜度
