【第十四天 - Linked list介绍】

Q1. linked list是什麽

是一种资料结构，透过很多节点(Node)串接成一个 linked list 型态的资料。
以 python 宣告的 ListNode class 为例

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

你可以在 python 中宣告一个名为 linked_data 的 ListNode 结构(没有给参数，则根据 ListNode 预设值创建)，宣告一个名为 data_1 的 ListNode 结构，val 为 1

linked_data = ListNode()
data_1 = ListNode(1)

linked_data.next = data_1

画出来的型态如下图
linked list 的资料结构可以实作新增、删除的功能
- 删除 linked list中的一个，只需要将指向下一个节点 next 修改成要指向的新 node
- 新增的功能，只要将新增的Node指向即将插入的後一个 Node，然後再让前一个 Node 指向新Node
python 中 linked list vs. list vs. array
- linked list 通常是自己宣告节点需要哪些资料，若你希望你的 linked list 可以具备往上一个 Node 跳的功能，那你也可以在 class 新增一个 pre，专门指向前一个 Node，形成 doubly linked link。
```
# 宣告一个结构
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 宣告一个命名为 linked_data 的 ListNode class 结构的资料 
linked_data = ListNode()
```
- list
  - 我们平常使用的 List 结构，就会跟记忆体要一连串的位址，如图 0x310718~0x3106e8 位址，每个位址会储存真正的，指向真正储存的值的位址，假设读取 list 最後一个位址 (0x3106e8)，他会导向真正储存值的地方，找到我们储存的资料
  - 有人就会有疑问了，为什麽不直接把资料储存在跟记忆体要的空间，而是还要储存一个位置，导向真正的资料位置，list 这样设计的好处是，他是储存「真正一笔资料的位址」，所以资料可以不限制类型，可以是字串、数字...，储存的不同类型资料会额外分配空间，而list 只要记录地址就可以，这样我们一开始分配 list 空间的时候，就不会忽大忽小，不过也是因为导向的关系，所以 List 效率会比较低
  - 切记，若我们想将 list 中间把资料砍掉，例如 0x310700 的值不要了，那麽 0x3106b8~0x3106e8 就会向前递补，0x310700~0x3106d0 就会储存新导向的地方
- numpy array (额外使用 numpy library)
  - 跟记忆体要一段空间，空间直接储存资料，array 中，只能储存相同型态的资料