05.6.1.md

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