12.md

Linked List

• 為一線性資料集合，但資料的順序並非實體記憶體擺放之位置，而是由 pointer 指向下一個元素
• Linked List 由許多節點 (node) 所構成，每個 node 裡面包涵 value 與 pointer，指向下一個 node 或空 (null)
• 資料結構只有兩個屬性 (property) - Head, Length

Advantages

• Node 可以被無限的加入 (Array 是一開始就宣告長度了)
• 插入 (insertion)、刪除 (deletion) 非常快速

Disadvantages

• 相較於 array，linked list 需要用到更多記憶體空間，因為需要存下一個 node 的位置
• 若需要找到某個位置，則一定要從頭開始巡訪
• 因為 node 為不連續儲存，所以尋訪至某個 node 的速度較慢
• 若要反向巡訪 (reverse traverse) 是很不容易的事情

Difference between Array and Linked List

Linked List

• 沒有 index 概念
• Node 之間的連結都是用 next property
• 隨機存取的方式是不被允許的（一定要從頭存取）

Array

• 有 index 概念
• 插入與刪除某個 index 是非常貴的（因為要重新計算 array 長度）
• 可以快速的被存取

Performance

Accessing Element

• Array: O(1)
• Linked List: O(n)

Insert or Remove from the beginning

• Array: O(n)
• Linked List: O(1)

Insert or Remove from the end

• Array: O(1)
• Linked List: O(n)

Insert or Remove from the middle

• Array: O(n)
• Linked List: O(n)