Linked List (鏈結串列)◝(　ﾟ∀ ﾟ )◟

介紹完Array接下來來看Linked List，他們可以算是好兄弟常常會一起被提到呢!
陣列是屬於靜態資料結構，而鏈結串列則是屬於動態資料結構，那鏈結串列會有什麼特點呢?

• 使用不連續記憶空間來儲存
• 資料的插入或刪除都很方便，不需要移動大量資料
• 不需要事先宣告連續的記憶體空間，能夠充分節省記憶體空間
• 要查詢特定節點時，無法像靜態資料一般可隨機讀取資料，必須循序走訪直到找到該資料
• 分為單向鏈結、雙向鏈結、環狀鏈結

單向鏈結(Singly Linked List)

特性:

• 每個節點(Node)身上都有資料還有指標
• 只能透過指標單向尋找要讀取的節點，無法像array透過index找尋
• 第一個節點又被稱作頭節點(head)
• 最後一個節點又被稱作tail，且最後一節點的指標指向Null
• 插入或新增節點很方便，只要改變指標即可
  

生活中實例，就像我們玩搭火車遊戲一樣，每個人的手都是搭在前一個人的肩膀上，大家也都面向同一個地方(づ′▽`)づ

雙向鏈結(Doubly Linked List)

特性:

• 一個Node包含資料與2個指標(LLink、RLink)
• 可以雙向讀取節點
• 可快速修補脫落的節點
• 指標較多較浪費空間
• 新增、刪除節點較複雜

雙向鏈結像原住民某種舞蹈!!一手會牽向左方的人，一手牽向右方的人✧◝(⁰▿⁰)◜✧

插入 t node after x node

1. t➝RLink = x➝RLink
2. t➝LLink = x
3. (x➝RLink)➝LLink = t
4. x➝RLink = t

需要改變4個pointer

刪除x node

1. (x➝LLink)➝RLink = x➝RLink
2. (x➝RLink)➝LLink = x➝LLink

比較Singly Linked List與Doubly Linked List)