05.5.1 Go 语言实现链表

链表相关实现的 Go 源文件是 linkedList.go，我们将分为五个部分来介绍。

linkedList.go 中的第一个代码段如下：

package main

import (
    "fmt"
)

type Node struct {
    Value int
    Next  *Node
}

var root = new(Node)

在这部分代码中，我们定义了用作链表节点的 Node 结构类型和保存链表第一个元素的全局变量 root，在代码的其他任何地方我们都能访问这个变量。

linkedList.go 的第二部分是如下的 Go 代码：

func addNode(t *Node, v int) int {
    if root == nil {
        t = &Node{v, nil}
        root = t
        return 0
    }

    if v == t.Value {
        fmt.Println("Node already exists:", v)
        return -1
    }

    if t.Next == nil {
        t.Next = &Node{v, nil}
        return -2
    }

    return addNode(t.Next, v)
}

依据工作原理，链表通常不含重复的项。此外，如果不是有序链表，新的节点通常会被添加在链表的尾部。

因此，addNode() 函数的功能就是向链表中添加新的节点。这个实现中使用 if 语句检查了三种不同的情况。第一种情况，检查要处理的链表是否为空。第二种情况，检查将要插入的值是否已经存在。第三种情况，检查是否已经到达了链表的末端，这时，使用 t.Next = &Node{v, nil} 将含有给定值的新节点加入链表的末端。如果所有的情况都不满足，则使用 return addNode(t.Next, v) 对链表中下一个节点调用 addNode()，重复上面的过程。

linkedList.go 程序的第三个代码片段包含了 traverse() 函数的实现：

func traverse(t *Node) {
    if t == nil {
        fmt.Println("-> Empty list!")
        return
    }

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

linkedList.go 的第四部分如下：

func lookupNode(t *Node, v int) bool {
    if root == nil {
        t = &Node{v, nil}
        root = 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("-> Empty list!")
        return 0
    }

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

这一部分包含了两个非常方便的函数——lookupNode() 和 size() 的实现。前一个函数检查链表中是否存在给定的元素，后一个函数返回链表的大小，也就是链表中节点的数量。

lookupNode() 函数实现背后的逻辑很容易理解：依次访问单向链表中所有的元素来查找你想要的值。如果你从头到尾都没找到想要的值，那就说明链表中没有这个值。

linkedList.go 的最后一部分包含 main() 函数的实现：

func main() {
    fmt.Println(root)
    root = nil
    traverse(root)
    addNode(root, 1)
    addNode(root, -1)
    traverse(root)
    addNode(root, 10)
    addNode(root, 5)
    addNode(root, 45)
    addNode(root, 5)
    addNode(root, 5)
    traverse(root)
    addNode(root, 100)
    traverse(root)

    if lookupNode(root, 100) {
        fmt.Println("Node exists!")
    } else {
        fmt.Println("Node does not exist!")
    }

    if lookupNode(root, -100) {
        fmt.Println("Node exists!")
    } else {
        fmt.Println("Node does not exist!")
    }
}

执行 linkedList.go 将生成如下的输出：

$ go run linkedList.go
&{0 <nil>}
-> Empty list!
1 -> -1 -> 
Node already exists: 5
Node already exists: 5
1 -> -1 -> 10 -> 5 -> 45 -> 
1 -> -1 -> 10 -> 5 -> 45 -> 100 -> 
Node exists!
Node does not exist!