Question

Go 语言实现双向链表

实现了双向链表的 Go 程序是 doublyLList.go，我们将分为五个部分来介绍。双向链表背后的基本思想和单向链表相同。不过由于双向链表中每个节点都有两个指针，所以操作更冗杂。

doublyLList.go 的第一部分如下：

package main

import (
    "fmt"
)

type Node struct {
    Value    int
    Previous *Node
    Next     *Node
}

这部分中使用 Go 的结构体定义了双向链表的节点。不过这次的 struct 中有两个指针字段，原因就不必多说了。

doublyLList.go 的第二部分包含如下的 Go 代码：

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

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

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

    return addNode(t.Next, v)
}

就像单向链表中一样，新的节点都被添加在当前双向链表的末端。这并不是强制性的，你也可以选择对这个双向链表进行排序。

doublyLList.go 的第三部分如下：

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()
}

func reverse(t *Node) {
    if t == nil {
        fmt.Println("-> Empty list!")
        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()
}

这是 traverse() 和 reverse() 函数的 Go 代码。traverse() 的实现和 linkedList.go 中的一样。但是 reverse() 背后的逻辑很有趣。因为没有指向双向链表尾节点的指针，所以我们必须先从头向后访问，直到找到尾节点，之后才能反向遍历所有的节点。

doublyLList.go 的第四部分包含如下的 Go 代码：

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

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

func lookupNode(t *Node, v int) bool {
    if root == nil {
        return false
    }

    if v == t.Value {
        return true
    }

    if t.Next == nil {
        return false
    }

    return lookupNode(t.Next, v)
}

doublyLList.go 的最后一个代码段包含如下的 Go 代码：

var root = new(Node)

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, 0)
    addNode(root, 0)
    traverse(root)
    addNode(root, 100)
    fmt.Println("Size:", size(root))
    traverse(root)
    reverse(root)
}

执行 doublyLList.go，你将得到如下输出：

$ go run doublyLList.go
&{0 <nil> <nil>}
-> Empty list!
Node already exists: 1
1 -> 
Node already exists: 0
1 -> 10 -> 5 -> 0 -> 
Size: 5
1 -> 10 -> 5 -> 0 -> 100 -> 
100 -> 0 -> 5 -> 10 -> 1 ->

如你所见，reverse() 函数效果很好！