Go 數據結構和算法篇：鏈表

鏈表是一種數據結構，和數組不同，鏈表並不需要一塊連續的內存空間，它通過「指針」將一組零散的內存塊串聯起來使用，如圖所示：

數組和鏈表的內存分佈

一、單鏈表

鏈表有多種類型，最簡單的是單鏈表，單鏈表是最原生的鏈表，其結構如圖所示：

單鏈表中有兩個節點比較特殊，分別是第一個節點和最後一個節點。我們通常把第一個節點叫作頭節點，把最後一個結點叫作尾節點。

其中，頭節點用來記錄鏈表的基地址，有了它，我們就可以遍歷得到整條鏈表。而尾節點特殊的地方是：指針不是指向下一個結點，而是指向一個空地址 NULL，表示這是鏈表上最後一個節點。

對於其他普通節點而言，每個節點至少使用兩個內存空間：一個用於存儲實際數據，另一個用於存儲下一個元素的指針，從而形成出一個節點序列，構建鏈表。

對單鏈表而言，理論上來說，插入和刪除節點的時間複雜度是 O(1)，查詢節點的時間複雜度是 O(n)。

基於 Go 語言實現單鏈表

下面我們基於 Go 語言來實現簡單的單鏈表，並實現添加節點、遍歷鏈表、查找節點和獲取鏈表長度等功能：

package main

import (
    "fmt"
)

// 定義節點
type Node struct {
    Value int
    Next  *Node
}

// 初始化頭節點
var head = new(Node)

// 添加節點
func addNode(t *Node, v int) int {
    if head == nil {
        t = &Node{v, nil}
        head = t
        return 0
    }

    if v == t.Value {
        fmt.Println("節點已存在:", v)
        return -1
    }

   // 如果當前節點下一個節點爲空
    if t.Next == nil {
        t.Next = &Node{v, nil}
        return -2
    }

   // 如果當前節點下一個節點不爲空
    return addNode(t.Next, v)
}

// 遍歷鏈表
func traverse(t *Node) {
    if t == nil {
        fmt.Println("-> 空鏈表!")
        return
    }

    for t != nil {
        fmt.Printf("%d -> ", t.Value)
        t = t.Next
    }

    fmt.Println()
}

// 查找節點
func lookupNode(t *Node, v int) bool {
    if head == nil {
        t = &Node{v, nil}
        head = t
        return false
    }

    if v == t.Value {
        return true
    }

    if t.Next == nil {
        return false
    }

    return lookupNode(t.Next, v)
}

// 獲取鏈表長度
func size(t *Node) int {
    if t == nil {
        fmt.Println("-> 空鏈表!")
        return 0
    }

    i := 0
    for t != nil {
        i++
        t = t.Next
    }

    return i
}

// 入口函數
func main() {
    fmt.Println(head)
    head = nil
    // 遍歷鏈表
    traverse(head) 
    // 添加節點 
    addNode(head, 1)
    addNode(head, -1)
    // 再次遍歷
    traverse(head)
    // 添加更多節點
    addNode(head, 10)
    addNode(head, 5)
    addNode(head, 45)
    // 添加已存在節點
    addNode(head, 5)
    // 再次遍歷
    traverse(head)

   // 查找已存在節點
    if lookupNode(head, 5) {
        fmt.Println("該節點已存在!")
    } else {
        fmt.Println("該節點不存在!")
    }

   // 查找不存在節點 
    if lookupNode(head, -100) {
        fmt.Println("該節點已存在!")
    } else {
        fmt.Println("該節點不存在!")
    }
}

執行上述代碼，打印結果如下：

二、循環鏈表

還可以在單鏈表的基礎上擴展出循環鏈表，循環鏈表和單鏈表的區別是尾節點指向了頭節點，從而首尾相連，有點像貪喫蛇，可用於解決「約瑟夫環」問題，循環鏈表的結構如圖所示：

感興趣的同學可以參考單鏈表自行通過 Go 語言實現循環鏈表，非常簡單，就是將尾節點的後驅節點指針執行頭節點即可。

三、雙向鏈表

比較常見的鏈表結構還有雙向鏈表，顧名思義，與單鏈表的區別是雙向鏈表除了有一個指向下一個節點的指針外，還有一個用於指向上一個節點的指針，從而實現通過 O(1) 複雜度找到上一個節點。正是因爲這個指針，使得雙向鏈表在插入、刪除節點時比單鏈表更高效。

雖然我們前面已經提到單鏈表插入、刪除時間複雜度已經是 O(1) 了，但是這只是針對插入、刪除操作本身而言，以刪除爲例，刪除某個節點後，需要將其前驅節點的指針指向被刪除節點的下一個節點：

這樣，我們還需要獲取其前驅節點，在單鏈表中獲取前驅節點的時間複雜度是 O(n)，所以綜合來看單鏈表的刪除、插入操作時間複雜度也是 O(n)，而雙向鏈表則不然，它有一個指針指向上一個節點，所以其插入和刪除時間複雜度纔是真正的 O(1)：

此外，對於有序鏈表而言，雙向鏈表的查詢效率顯然也要高於單鏈表，不過更優的時間複雜度是靠更差的空間複雜度換取的，雙向鏈表始終需要單鏈表的兩倍空間，不過正如我們之前說的，在 Web 應用中，時間效率優先級更高，所以我們通常都是空間換時間來提高性能，Java 的 LinkedHashMap 底層就用到了雙向鏈表，此外在日常應用中，音樂軟件的播放列表也是一個典型的雙向鏈表（支持在上一首和下一首之間進行切換）。

雙向鏈表的結構如圖所示：

基於 Go 語言實現雙向鏈表

下面我們來看看如何基於 Go 語言實現雙向鏈表，和單鏈表相比，雙向鏈表需要多維護一個前驅節點指針，以及支持反向遍歷：

package main

import (
    "fmt"
)

// 定義節點
type Node struct {
    Value    int
    Previous *Node
    Next     *Node
}

// 添加節點
func addNode(t *Node, v int) int {
    if head == nil {
        t = &Node{v, nil, nil}
        head = t
        return 0
    }

    if v == t.Value {
        fmt.Println("節點已存在:", v)
        return -1
    }

    // 如果當前節點下一個節點爲空
    if t.Next == nil {
        // 與單鏈表不同的是每個節點還要維護前驅節點指針
        temp := t
        t.Next = &Node{v, temp, nil}
        return -2
    }

    // 如果當前節點下一個節點不爲空
    return addNode(t.Next, v)
}

// 遍歷鏈表
func traverse(t *Node) {
    if t == nil {
        fmt.Println("-> 空鏈表!")
        return
    }

    for t != nil {
        fmt.Printf("%d -> ", t.Value)
        t = t.Next
    }

    fmt.Println()
}

// 反向遍歷鏈表
func reverse(t *Node) {
    if t == nil {
        fmt.Println("-> 空鏈表!")
        return
    }

    temp := t
    for t != nil {
        temp = t
        t = t.Next
    }

    for temp.Previous != nil {
        fmt.Printf("%d -> ", temp.Value)
        temp = temp.Previous
    }

    fmt.Printf("%d -> ", temp.Value)
    fmt.Println()
}

// 獲取鏈表長度
func size(t *Node) int {
    if t == nil {
        fmt.Println("-> 空鏈表!")
        return 0
    }

    n := 0
    for t != nil {
        n++
        t = t.Next
    }

    return n
}

// 查找節點
func lookupNode(t *Node, v int) bool {
    if head == nil {
        return false
    }

    if v == t.Value {
        return true
    }

    if t.Next == nil {
        return false
    }

    return lookupNode(t.Next, v)
}

// 初始化頭節點
var head = new(Node)

func main() {
    fmt.Println(head)
    head = nil
    // 遍歷鏈表
    traverse(head)
    // 新增節點
    addNode(head, 1)
    // 再次遍歷
    traverse(head)
    // 繼續添加節點
    addNode(head, 10)
    addNode(head, 5)
    addNode(head, 100)
    // 再次遍歷
    traverse(head)
    // 添加已存在節點
    addNode(head, 100)
    fmt.Println("鏈表長度:", size(head))
    // 再次遍歷
    traverse(head)
    // 反向遍歷
    reverse(head)

    // 查找已存在節點
    if lookupNode(head, 5) {
        fmt.Println("該節點已存在!")
    } else {
        fmt.Println("該節點不存在!")
    }
}

運行上述代碼，打印結果如下：

四、雙向循環鏈表

最後，我們要介紹的是結合循環鏈表和雙向鏈表爲一體的雙向循環鏈表：

感興趣的同學可以參考雙向鏈表自行基於 Go 語言實現雙向循環鏈表，其實就是將雙向鏈表的首尾通過指針連接起來，對於支持循環播放的音樂列表其實就是個雙向循環鏈表結構。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/Cn39YN8R6jOJZS-istaTKA