# 74 Data Structure — Linked List
這陣子開發遇到了一顆隕石，一開始要求要3秒一次的 Carousel。
手起刀落的花了 3H 處理完這功能，剛 Commint 完準備 Push 而已，又落下下一顆隕石說：每筆資料都只有3秒不太好，要求秒數從 API 拿到的 Data 撈出每筆的時間來做 Carousel。
挑燈夜戰之後，終於用 Recursion 克服 Timer 沒辦法刷新時間的問題，結果…這其實是流星雨，需求變成：每播完一次，要讓第二筆資料變成第一筆，以此類推…然後，第二輪開始，把沒有 State 的資料，依照權重將資料安插到 Carousel 裡面。
我無助的看著前輩
「刷過 Leet code 沒有？」
「看你表情就知道沒有，看來你現在有機會了」
「去看一下 Linked List 怎寫吧」
「就是應付這種流星雨用的 Array，不難拉～」
前輩霸氣的說
ＯＫ，以上做夢夢到的瞎掰故事說完了，我們來看一下 Linked List 是什麼？
維基百科：
Linked List 是資料結構裡面的一種鏈式儲存結構,可以在降低空間複雜度的情況下達到和雙向鏈結串列一樣的目的，使得在任何一個節點都能方便地存取它的前驅節點和後繼節點。
What? Again…
白話文解釋：
每筆資料就是一個 Node，每個 Node 內會存放下一筆資料的位置(Next)，將這些 Node 串起來，藉此達到一個資料鏈的概念。
Node 的結構會長成這樣 (還有別種寫法，可以自行發揮)
- Node
— Data(要存的資料)
— Next(下一筆資料位置)
— Previous(最後一筆資料位置)
串起來就會如上圖這樣。
這時候會有一個疑問，要怎定義下一筆資料的位置？
日常最常被使用到儲存連續資料的型別是 Array，Array 有個神奇的功能是 Swift 提供的叫做 Index，它直接讓指標指向了這塊記憶體位置，讓我們取得資料
var names: [String] = ["哈利波特","妙麗","榮恩"]
guard !names.isEmpty else { return }
var currnetName = names[1]
print("最美麗的明星：\(currnetName)")
// 最美麗的明星：妙麗OK，既然 Swift 就提供這樣棒的 Array 型別讓我們使用，幹嘛不用呢？
原因就在於，創建 Array 時，是跟記憶體直接拿取一塊連續的位置，可以把它想像成，買了一塊10平方公尺的地，這塊地劃分成10等分，每一等分都要放一個哈利波特內的人物蠟像，但我還不知道這蠟像會放幾個，有可能沒放滿，也可能放超過，反正我就先拿了一塊10平方公尺的地。
這時候問題就來了。
如果我順序要改呢？
如果第二個我要移除呢？
如果要加入一個鄧不利多在第一個位置呢？
這時候會發現使用 Array 的不方便性就出現了。
Array 是個很方便可以對個別位置的資料做處理的方式，我可以單獨拿出指定位置的資料做處理、使用或是展示，但如果要將鄧不利多加入到第一個位置，就必須大費周章的將其他人的位置 +1
原本位置：
0 = 哈利波特
1 = 妙麗
2 = 榮恩
加入鄧不利多之後變成
0 = 鄧不利多
1 = 哈利波特
2 = 妙麗
3 = 榮恩
實在麻煩啊～
這時候 Linked List Data Structure(鏈式資料結構)就派上用場了。
我每次都是拿一個單獨的記憶體位置，裡面就只放一個蠟像，然後告訴他下一個蠟像的位置在哪，最後一個蠟像跟他說你是最後一個，有人要找你的下一個就去找第一個，沒人找下一個就跟他說你是最後一個了～
這時候如果有三個蠟像，就單獨拿三塊的記憶體位置就好，當有第四個蠟像，再拿第四塊就好，既省記憶體又方便要調整位置。
但 Linked List 最大的不方便就是沒辦法直接到我要的位置去，一定要遍歷之後才可以。
如果以上還是無法理解，可以搭配下面表格幫助理解。
下面上 Code 演示
class LinkedList<T> {
class Node {
var value: T
var next: Node?
weak var previous: Node?
init(value: T) {
self.value = value
}
}
}解釋：
首先我們需要一個裝資料的 Node，將要裝進 Node 的資料給 Value，但因為要裝什麼是要用的地方決定的，所以這邊用 T (Generic)型別給他，Next 指向 Node，這裡就是將下一筆資料位置給他的關鍵。
Class 是 Reference Type，所以 Next 是直接參考 Node 這個記憶體位置的資料，這樣下一筆資料的關鍵位置就有了。
Linkedlist 是使用 Node 這個 Data Structure 的人，所以將 Node 放這裏面，再來我們需要讓 Linkedlist 有可以使用 Node 的能力。
private var headNode: Node?
private var tailNode: Node?
private var currentNode: Node?
var first: T? {
return headNode?.value
}
var last: T? {
return tailNode?.value
}
var current: T? {
return currentNode?.value
}解釋：
我們需要
1. 第一個位置
2. 最後一個位置
3. 目前位置
所以將參數開出來，但為了避免外部改到參數，所以用 private 保護起來，return 要用的參數給外部使用就好～
有了參數，再來我們要處理加入 Node 的部分
func append(value: T) {
let newNode = Node(value: value)
if let tailNode = tailNode {
tailNode.next = newNode
newNode.previous = tailNode
} else {
headNode = newNode
currentNode = newNode
}
tailNode = newNode
tailNode?.next = headNode
}解釋：
根據上面提到的概念，我們需要產生一個 Node 物件，塞入需要存放的資料
當 tailNode 不是 nil 的時候，代表有上一筆資料，這時候告訴上一筆資料，你的下一個是新加入的 Node，將 tailNode 交棒給新加入的資料，告訴他你是最後一個，如果沒有上一筆資料，代表新加入的 Node 是第一筆，也是目前位置。
上面判斷式是在
1. 告知上一筆 Node，你下一筆 Node 在哪
2. 告知新 Node 是最後一筆 Node
3. 告知誰是第一筆 Node
4. 告知誰是目前的 Node
最後判斷式外是將 tailNode 裝進新的 Node
告訴裝著新 Node 的 tailNode，你下一筆 Node 是第一筆唷～
搞定加入之後，我們來看一下該怎前往下一筆 Node
func nextItem() -> T? {
currentNode = currentNode?.next
return currentNode?.value
}解釋：
這個就很單純了，將目前 Nodel 裝進下一筆 Node 回傳就好~
接下來處理刪除指定 Node
func remove(node: Node) -> T {
let prev = node.previous
let next = node.next
if let prev = prev {
prev.next = next
} else {
headNode = next
}
next?.previous = prev
if next == nil {
tailNode = prev
}
node.previous = nil
node.next = nil
return node.value
}解釋：
刪除，也是很單純做交接的動作，將要刪除的 Node 位置資訊交給他前後的 Node
首先判斷即將刪除的 Node 是否是最後一筆資料，如果是，將是最後一筆資料的身份交給自己的下一筆 Node，如果不是，把第一個 Node 的身份交給要被刪除 Node 的下一個 Node
頭暈了嗎？
這邊給個當時自己輔助理解畫的圖，給大家參考一下
Linked List 的整體設計重點在於，告訴 Node
我是誰？
我在哪？
下一個去哪裡？
然後將裝載以上資訊的 Node 裝進指定的變數位置裡，最後就會變成
- Node01
— 我是第一筆資料
— 我有一筆資料
— 我下一筆是 Node02
- Node02
— 我有一筆資料
— 我下一筆是 Node03
- Node03
— 我有一筆資料
— 我是最後一筆資料
— 我下一筆要去 Node01
希望以上廢話很多的說明，可以幫助大家理解 Linked List 的使用方式，拿出紙筆畫一次可以大幅度幫助理解的程度，避免自己迷路～