Go 數(shù)據(jù)結(jié)構(gòu)和算法篇（一）：鏈表

鏈表是一種數(shù)據(jù)結(jié)構(gòu)，和數(shù)組不同，鏈表并不需要一塊連續(xù)的內(nèi)存空間，它通過「指針」將一組零散的內(nèi)存塊串聯(lián)起來使用，如圖所示：

一、單鏈表

鏈表有多種類型，最簡單的是單鏈表，單鏈表是最原生的鏈表，其結(jié)構(gòu)如圖所示：

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

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

對于其他普通節(jié)點而言，每個節(jié)點至少使用兩個內(nèi)存空間：一個用于存儲實際數(shù)據(jù)，另一個用于存儲下一個元素的指針，從而形成出一個節(jié)點序列，構(gòu)建鏈表。

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

基于 Go 語言實現(xiàn)單鏈表

下面我們基于 Go 語言來實現(xiàn)簡單的單鏈表，并實現(xiàn)添加節(jié)點、遍歷鏈表、查找節(jié)點和獲取鏈表長度等功能：

package main

import (
    "fmt"
)

// 定義節(jié)點
type Node struct {
    Value int
    Next  *Node
}

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

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

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

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

   // 如果當前節(jié)點下一個節(jié)點不為空
    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()
}

// 查找節(jié)點
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
}

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

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

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

執(zhí)行上述代碼，打印結(jié)果如下：

二、循環(huán)鏈表

還可以在單鏈表的基礎上擴展出循環(huán)鏈表，循環(huán)鏈表和單鏈表的區(qū)別是尾節(jié)點指向了頭節(jié)點，從而首尾相連，有點像貪吃蛇，可用于解決「約瑟夫環(huán)」問題，循環(huán)鏈表的結(jié)構(gòu)如圖所示：

感興趣的同學可以參考單鏈表自行通過 Go 語言實現(xiàn)循環(huán)鏈表，非常簡單，就是將尾節(jié)點的后驅(qū)節(jié)點指針執(zhí)行頭節(jié)點即可。

三、雙向鏈表

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

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

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

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

雙向鏈表的結(jié)構(gòu)如圖所示：

基于 Go 語言實現(xiàn)雙向鏈表

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

package main

import (
    "fmt"
)

// 定義節(jié)點
type Node struct {
    Value    int
    Previous *Node
    Next     *Node
}

// 添加節(jié)點
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("節(jié)點已存在:", v)
        return -1
    }

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

    // 如果當前節(jié)點下一個節(jié)點不為空
    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
}

// 查找節(jié)點
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)
}

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

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

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

運行上述代碼，打印結(jié)果如下：

四、雙向循環(huán)鏈表

最后，我們要介紹的是結(jié)合循環(huán)鏈表和雙向鏈表為一體的雙向循環(huán)鏈表：

感興趣的同學可以參考雙向鏈表自行基于 Go 語言實現(xiàn)雙向循環(huán)鏈表，其實就是將雙向鏈表的首尾通過指針連接起來，對于支持循環(huán)播放的音樂列表其實就是個雙向循環(huán)鏈表結(jié)構(gòu)。