Go 语言实现双向链表

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

doublyLList.go 的第一部分如下：

  1. package main
  3. import (
  4.     "fmt"
  5. )
  7. type Node struct {
  8.     Value    int
  9.     Previous *Node
  10.     Next     *Node
  11. }

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

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

  1. func addNode(t *Node, v int) int {
  2.     if root == nil {
  3.         t = &Node{v, nil, nil}
  4.         root = t
  5.         return 0
  6.     }
  8.     if v == t.Value {
  9.         fmt.Println("Node already exists:", v)
  10.         return -1
  11.     }
  13.     if t.Next == nil {
  14.         temp := t
  15.         t.Next = &Node{v, temp, nil}
  16.         return -2
  17.     }
  19.     return addNode(t.Next, v)
  20. }

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

doublyLList.go 的第三部分如下：

  1. func traverse(t *Node) {
  2.     if t == nil {
  3.         fmt.Println("-> Empty list!")
  4.         return
  5.     }
  7.     for t != nil {
  8.         fmt.Printf("%d -> ", t.Value)
  9.         t = t.Next
  10.     }
  11.     fmt.Println()
  12. }
  14. func reverse(t *Node) {
  15.     if t == nil {
  16.         fmt.Println("-> Empty list!")
  17.         return
  18.     }
  20.     temp := t
  21.     for t != nil {
  22.         temp = t
  23.         t = t.Next
  24.     }
  26.     for temp.Previous != nil {
  27.         fmt.Printf("%d -> ", temp.Value)
  28.         temp = temp.Previous
  29.     }
  30.     fmt.Printf("%d -> ", temp.Value)
  31.     fmt.Println()
  32. }

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

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

  1. func size(t *Node) int {
  2.     if t == nil {
  3.         fmt.Println("-> Empty list!")
  4.         return 0
  5.     }
  7.     n := 0
  8.     for t != nil {
  9.         n++
  10.         t = t.Next
  11.     }
  12.     return n
  13. }
  15. func lookupNode(t *Node, v int) bool {
  16.     if root == nil {
  17.         return false
  18.     }
  20.     if v == t.Value {
  21.         return true
  22.     }
  24.     if t.Next == nil {
  25.         return false
  26.     }
  28.     return lookupNode(t.Next, v)
  29. }

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

  1. var root = new(Node)
  3. func main() {
  4.     fmt.Println(root)
  5.     root = nil
  6.     traverse(root)
  7.     addNode(root, 1)
  8.     addNode(root, 1)
  9.     traverse(root)
  10.     addNode(root, 10)
  11.     addNode(root, 5)
  12.     addNode(root, 0)
  13.     addNode(root, 0)
  14.     traverse(root)
  15.     addNode(root, 100)
  16.     fmt.Println("Size:", size(root))
  17.     traverse(root)
  18.     reverse(root)
  19. }

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

  1. $ go run doublyLList.go
  2. &{0 <nil> <nil>}
  3. -> Empty list!
  4. Node already exists: 1
  5. 1 -> 
  6. Node already exists: 0
  7. 1 -> 10 -> 5 -> 0 -> 
  8. Size: 5
  9. 1 -> 10 -> 5 -> 0 -> 100 -> 
  10. 100 -> 0 -> 5 -> 10 -> 1 ->

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