05.6.1 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() 函数效果很好!