Linked list - 鍊表

1.Why Linked list ?

因為Array在使用上存在兩個問題

1. 在宣告時，就得指定大小，如果分配太多會造成空間的浪費，若分配太少又會出現錯誤，
2. 若要刪除或插入某個元素至陣列中，通常須對其他元素進行平移

而Linked list能透過pointer動態的分配紀憶體空間，補足了Array這兩個缺點。

2. Linked list的核心人物：pointer

• Pointer存放的是記憶體位置

• & ： the address operator （對一個變數取得它的位置）
• *  ： the de-referencing operator （到這個變數的位置去取得它的值）
• e.g. ：int * p = &x;
• int * p  ：宣告一個儲存int位置的pointer
• p = &x ：讓p儲存x的地址
• 而*p形同*&x，對x的位置取值，自然能取得x的值囉

• 誤用Pointer
• Dangling pointer
• pointer記錄到失效的記憶體位置（比如已經被刪除的變數），進而取到錯誤的值
• Memory leakage
• 忘了去deallocate不必要用的空間

3.Linked list

• Singly linked list
• 結構 ：
• 一個pointer的欄位，指向下一個節點(node)
• 一個data的欄位，儲存這個節點的資料
• 通常我們會用一個指標Head來指向第一個節點
• 通常最後一個節點會指向NULL
• 對linked的操作
• 1.定義一個節點的結構(struct)
• 2.當要新增一個節點時
• 先分配記憶體給這個新節點
• 把list中最尾端節點的指標指向新節點
• 3.當要移除一個節點時 -> free