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. 资料的数量不会有太大变更时 |