Image by macrovector on Freepik
Singly Linked List 定義
- 每個 Node 會包含 value 和 next 的資訊
- Linked List 會包含 head, tail 的資訊
- Linked List 包含 append, prepend, insert, remove, printList 的方法
Doubly Linked List 定義
- 每個節點(Node)包含了 next, prev 和 value
- Linked List 會紀錄 head, tail 的資訊
- Linked List 實作了 append, prepend, insert, remove printList 的方法
Linked List 優點
使用 Linked List 的資料結構可以更有效率的使用記憶體,因為每一個元素都是獨立,彼此之間是透過 next 和 prev 來關聯在一起
Array 和 Linked List 的差異
|
Linked List |
Array |
說明 |
類似把很多個物件關聯起來,並有順序性 |
同一記憶體空間的一個區間 |
記憶體 |
不需要連續的記憶體空間,因此不需要預留空間 |
需要連續的記憶體空間,宣告時就需要決定空間大小 |
資料插入/刪除 |
相對快,插入和刪除本身是 O(1),但有時需要先搭配搜尋 O(n) 來找到節點位置 |
相對慢,插入與刪除均為 O(n) |
資料取出 |
相對慢,要從頭開始找 O(n) 到後取出 |
相對快,可以直接使用索引(index)取出 |
適用時機 |
1. 無法預期資料數量時 2. 需要頻繁增刪資料時 3. 不需要頻繁查詢並取出資料時 |
1. 需要快速取出資料時 2. 不需要頻繁增刪資料時 3. 資料的數量不會有太大變更時 |
參考資料
Donate KJ 贊助作者喝咖啡
如果這篇文章對你有幫助的話,可以透過下面支付方式贊助作者喝咖啡,如果有什麼建議或想說的話可以贊助並留言給我
If this article has been helpful to you, you can support the author by treating them to a coffee through the payment options below. If you have any suggestions or comments, feel free to sponsor and leave a message for me!