# [資演] 4-Linked List (I): Singly linked list
###### tags: `資演`
**Linked list (鏈結串列)** 是一種序列式的資料結構，一個 linked list 由一連串的**節點 (node)** 組成，其中第一個節點稱為 head (頭)，最後一個節點稱為 tail (尾)。每個節點都使用一個**指標 (pointer)** 來連結到下一個節點，故稱為 linked list。

## Linked list 是什麼？

我們可以把一個 linked list 看作是一列火車，其中
* 每個節點對應到一節車廂
* 每個節點儲存的資料對應到車上的乘客
* 每節車廂都以某種方式連結到下一節車廂
* head 對應到火車頭
* tail 對應到最後一節車廂，它的下一節車廂不存在
* 每節車廂都是獨立的個體，可以分開來看


那麼，節點又是如何連結到下一個節點的呢？事實上，每一個節點都有它儲存的**記憶體位置**，也就是它的**位址 (address)**。所以，我們可以在一個節點寫上它下一個節點的位址，這麼一來，就可以從這個節點找到它的下一個節點。

所以，一個儲存在某個位址上的節點會帶有兩種資料，或稱為兩個**欄位 (field)**：
1. 節點本身帶有的資料 `data`
2. 下一個節點的位址 `next`

其中，tail 的下一個節點不存在，所以它的`next`必須是`null` (在Python是`None`)。

## Linked list 和 array 的比較
事實上，我們可以對linked list進行的操作，也都可以在array上實作。那麼為什麼我們還需要 linked list 呢？

以下是linked list和array的主要差異。

* 存取
對於 array，你可以直接用 index 去存取第 i 個元素，稱為 **random access** (**隨機存取**，或稱**直接存取**)。但在 linked list 的場合，你必須從 head 節點一個一個巡訪下去，直到你數到第 i 個節點為止，稱為 **sequential access** (**循序存取**)。因此對於存取某個元素來說，array是比linked list來得有效率。
* 記憶體配置
我們知道 array 所占有的是一整塊連續且固定大小的記憶體，並且相鄰的元素在記憶體中也是相鄰的。但 linked list 並不是這樣。linked list 中的每一個節點都是一個獨立的**物件 (object)**，在記憶體中是分開儲存的。每個節點透過指標來連結到下一個節點。所以要新增或刪除元素，對於linked list來說不像array一樣需要搬動大量的元素，只需要修改前一個節點的next指向的位址即可，自然比較有效率。

這些差異，使得我們可以在不同場合選擇使用array或linked list以達到更好的效率。

* 什麼時候該使用 array？
* 已經知道元素的個數，並且不太會再去增減它
* 你希望能夠快速取得第 i 個元素，不想花太多時間
* 當記憶體空間是你主要考量之一的時候
* 什麼時候該使用 linked list？
* 元素數量不固定，需要常常增減
* 你不在乎存取速度
* 記憶體空間充足的時候

簡單的說，linked list 提供了一種**以空間換取增減元素的效率**的方案。更深入的討論可以看看[這篇文章](https://medium.com/@yyisyou/%E8%AB%87linkedlist%E8%88%87array%E7%9A%84%E7%89%B9%E6%80%A7-c10f73505b88)。
## Linked list 的種類
* Singly linked list (單向鏈結串列)
前面的討論都是以最簡單的 linked list 為主，也就是 singly linked list。對於 singly linked list，我們可以從每一個節點參考到它的下一個節點，但是沒辦法反過來從這個節點參考到上一個節點。
* Doubly linked list (雙向鏈結串列)
為了解決 singly linked list 只能單向巡訪造成的麻煩，doubly lniked list 在每一個節點上面多增加了一個欄位 `prev`，用來存放前一個節點的位址。如此一來，便可以用反方向來巡訪整個linked list了。這也是一個使用額外的**儲存空間**來換取**方便性**的例子。
* Circular (singly) linked list (循環單向鏈結串列)
Circular linked list 和一般的 singly linked list 唯一的差別就在於 tail 的 next 是指到 head 的。也就是說，事實上對於一個circular linked list來說並沒有head和tail的概念。和一般的 singly linked list 一樣，巡訪時只能沿著單一方向。

* Circular doubly linked list (循環雙向鏈結串列)
把 circular linked list 上的每一個節點都加上一個指向前一個節點的指標，就成為了 circular doubly linked list，因此巡訪時可以沿著任意的方向。

我們一般講的 linked list，都是以 singly linked list 為主，其他種類的 linked list 才會特別說是哪種 linked list。本篇提到的 linked list ，若無特別說明，都是 singly linked list。

## 在 Python 創建一個 linked list
創建一個linked list的步驟如下：
1. 分別建立並初始化 head 和 tail 節點
2. 依序建立並初始化中間的一般節點
3. 把這些節點連接起來

但是我們要怎麼實作出節點這種物件 (object)，並把它們連接成一個新的物件，也就是 linked list 呢？這邊我們先創建一個**類別(class)** `Node`，我們可以把這個類別當成是創建所有節點的模板：

class Node:
    def __init__(self, data = None):
        self.data = data
        self.next = None

其中，`__init__` 方法就是我們創建一個物件時所執行的方法。在這邊我們分別將 `data` 這個屬性 (attribute) 初始化為傳入方法的引數，並把 `next` 初始化為`None`。

接著，我們再建立一個用來創建linked list的類別：

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

如此一來，我們便可以藉由這些類別來創建出節點，並把它們串成一個linked list：

node1 = Node(5)
node2 = Node(3)

my_list = LinkedList()

node1.next = node2

my_list.head = node1
my_list.tail = node2

現在我們建立了一個只有兩個節點的linked list。