Linked List 鏈結串列
Linked List 鏈結串列
Categories:
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. 資料的數量不會有太大變更時 |