05.5.1.md

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!