之前我們大量地使用陣列與字串，而本文我們開始來介紹 Linked List 這個不一樣的資料結構，它的中文叫做鏈結串列，他能夠解決一些陣列的限制，使資料存放更加彈性，怎麼說呢？就讓我們往下看下去。

鏈結串列與一般陣列不同點：

• 無須一開始宣告一個連續區塊的記憶體空間大小
• 每一個鍊結所分配的記憶體位址並不連續
• 方便動態新增以及刪除節點，不用擔心浪費記憶體
• 每一個節點都會存放它下一個節點的位置
• 沒有索引值，所以在查找某一個數值會需要一個一個走訪，不能直接取用

列了這麼多不同點，似乎優點還是大於陣列的資料結構，但是在高階程式語言裡，這個概念還是比較抽象的，而我們可以看圖片來理解這個資料結構。

它分為三種類型 (圖片來自維基百科)：

1. 單向鏈結串列，節點只會關聯下一個節點，最尾端關聯是空的。

2. 雙向鏈結串列，節點會關聯前後節點，最前面的節點關連會是空的，最尾端的節點關連也會是空的。

3. 環狀鏈結串列，因為是環狀所以關連節點不會有空的，會關連回最前面的節點。

這三種在 LeetCode 上分別都有對應的各自題型，但是新手的話建議先了解第一種單向的操作，剛開始學習的時候其實會感受到巨大的差異，在操作上也會感受不順手是非常正常，所以建議逐步學習。

Swift 如何建立 Linked List

基本上我們會建立一個 class，會定義一個泛型的 value ，也就是說它不限定是哪種資料類型，所以會變成資料可以存放的非常多元，然後會放一個 next 去關聯下一個節點，這樣一個一個串起來，就是 Linked List，在生活上其實很像我們在串珠子一樣。

class ListNode<T> {
    var value: T
    var next: ListNode?
    
    init(_ value: T) {
        self.value = value
    }
}

Swift 新增一個全新的節點

我們在加入一個全新的節點，會從尾端加入，此時就要一個一個節點往後走訪，發現走到尾端，也就是 next = nil 之時，就可以安插新的節點上去。

// 加入節點到鏈結串列尾端
func append(_ value: T) {
    let newNode = ListNode(value)
    if head == nil {
       head = newNode
       return
    }
    var current = head
    while current?.next != nil {
        current = current?.next
    }
    current?.next = newNode
}

Swift 刪除一個節點

在刪除節點的時候，會先去問第一個節點是不是符合，如果符合我們會把第一個節點指向它下一個節點，達成刪除作用。

如果不是，則會一個一個走訪去判斷，這邊要注意的是它會用兩個存放暫時節點資料的指針，分別是 current 跟 prev，這個可以複習我們前兩篇在解說的 Two pointers 概念，用兩個指針去紀錄並且操作刪除節點。

// 刪除指定節點
func deleteNode(_ value: T) {
    if head?.value == value {
        head = head?.next
        return
    }
    var current = head
    var prev: ListNode<T>?
    while current != nil && current!.value != value {
        prev = current
        current = current?.next
    }
    prev?.next = current?.next
}

LeetCode 應用題

這邊我們就看一題經典好上手的基礎題來理解 Linked List 概念，選題為 206. Reverse Linked List 這題，題目要我們反轉鏈結串列的資料。

這題就很明顯考驗我們如何要把每一個節點引用的位置翻轉過來，練習這個資料結構的操作。

一樣利用 Two pointers 先設定兩個指針紀錄，分別為 prev 跟 current，為了不影響走訪節點，因為會邊走訪邊改next指向的位置，所以一開始用 next 先放原始的 next，然後讓 current.next 被 prev 覆蓋，最後 prev 的值在更新成 current，就這樣一路走訪結束，最後直接拿 prev 的節點就會是我們要的結果了。

class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        var current = head
        var prev: ListNode<T>? = nil
        while current != nil {
            let next = current?.next
            current?.next = prev
            prev = current
            current = next
        }
        return prev
    }
}

這題的時間複雜度為 O(n)，因為我們一個一個走訪了節點，總共有幾個節點就走訪幾次，所以為N次。

空間複雜度因為沒有新增任何空間，單純只是用指針去指向現有的位置，做位置上的改動，所以為 O(1)。

總結

這一篇文章更讓我重新複習了一次 Linked List 應用，其實會寫程式碼跟會用文章解說還是不一樣的兩件事，透過文章解說，我把一些解釋不清楚的地方看得更明白，面試的很大一部分成分也是在練習如何「解說」自己學習到的程式概念，希望透過這一篇文章讓大家對於這個資料結構有更清晰的理解。