链表

链表是一种非连续的存储容器，由多个节点组成，节点通过一些变量记录彼此之间的关系，链表有多种实现方法，如单链表、双链表等
在Go语言中，链表使用 container/list 包来实现，内部的实现原理是双链表，链表能够高效地进行任意位置的元素插入和删除操作。

初始化列表

list 的初始化有两种方法：分别是使用 New() 函数和 var 关键字声明，两种方法的初始化效果都是一致的。

  1. 通过 container/list 包的 New() 函数初始化 list
1
变量名 := list.New()
  1. 通过 var 关键字声明初始化 list
1
var 变量名 list.List

链表与切片和 map 不同的是，链表并没有具体元素类型的限制，因此，链表的元素可以是任意类型，这既带来了便利，也引来一些问题，例如给链表中放入了一个 interface{} 类型的值，取出值后，如果要将 interface{} 转换为其他类型将会发生宕机。

在链表中插入元素

双链表支持从队列前方或后方插入元素，分别对应的方法是 PushFront 和 PushBack。

提示
这两个方法都会返回一个 *list.Element 结构，如果在以后的使用中需要删除插入的元素，则只能通过 *list.Element 配合 Remove() 方法进行删除，这种方法可以让删除更加效率化，同时也是双链表特性之一。

下面代码展示如何给 list 添加元素：

1
2
3
l := list.New()
l.PushBack("fist")
l.PushFront(67)

代码说明如下：

  • 第 1 行，创建一个链表实例。
  • 第 3 行，将 fist 字符串插入到列表的尾部，此时列表是空的，插入后只有一个元素。
  • 第 4 行，将数值 67 放入列表，此时，列表中已经存在 fist 元素，67 这个元素将被放在 fist 的前面。

链表插入元素的方法如下表所示。

方法 功能
InsertAfter(v interface {}, mark * Element) * Element 在 mark 点之后插入元素，mark 点由其他插入函数提供
InsertBefore(v interface {}, mark * Element) *Element 在 mark 点之前插入元素，mark 点由其他插入函数提供
PushBackList(other *List) 添加 other 列表元素到尾部
PushFrontList(other *List) 添加 other 列表元素到头部

从链表中删除元素

链表插入函数的返回值会提供一个 *list.Element 结构，这个结构记录着列表元素的值以及与其他节点之间的关系等信息，从链表中删除元素时，需要用到这个结构进行快速删除。

列表操作元素：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
package main

import "container/list"

func main() {
    l := list.New()

    // 尾部添加
    l.PushBack("canon")

    // 头部添加
    l.PushFront(67)

    // 尾部添加后保存元素句柄
    element := l.PushBack("fist")

    // 在fist之后添加high
    l.InsertAfter("high", element)

    // 在fist之前添加noon
    l.InsertBefore("noon", element)

    // 使用
    l.Remove(element)
}

代码说明如下：

  • 第 6 行，创建列表实例。
  • 第 9 行，将字符串 canon 插入到列表的尾部。
  • 第 12 行，将数值 67 添加到列表的头部。
  • 第 15 行，将字符串 fist 插入到列表的尾部，并将这个元素的内部结构保存到 element 变量中。
  • 第 18 行，使用 element 变量，在 element 的位置后面插入 high 字符串。
  • 第 21 行，使用 element 变量，在 element 的位置前面插入 noon 字符串。
  • 第 24 行，移除 element 变量对应的元素。

下表中展示了每次操作后列表的实际元素情况。

列表元素操作的过程

操作内容 列表元素
l.PushBack(“canon”) canon
l.PushFront(67) 67, canon
element := l.PushBack(“fist”) 67, canon, fist
l.InsertAfter(“high”, element) 67, canon, fist, high
l.InsertBefore(“noon”, element) 67, canon, noon, fist, high
l.Remove(element) 67, canon, noon, high

遍历列表

访问列表的每一个元素

遍历双链表需要配合 Front() 函数获取头元素，遍历时只要元素不为空就可以继续进行，每一次遍历都会调用元素的 Next() 函数，代码如下所示

1
2
3
4
5
6
7
8
l := list.New()
// 尾部添加
l.PushBack("canon")
// 头部添加
l.PushFront(67)
for i := l.Front(); i != nil; i = i.Next() {
    fmt.Println(i.Value)
}

代码输出如下：

1
2
67
canon

代码说明如下：

  • 第 1 行，创建一个列表实例。
  • 第 4 行，将 canon 放入列表尾部。
  • 第 7 行，在队列头部放入 67。
  • 第 9 行，使用 for 语句进行遍历，其中 i:=l.Front() 表示初始赋值，只会在一开始执行一次，每次循环会进行一次 i != nil 语句判断，如果返回 false，表示退出循环，反之则会执行 i = i.Next()。
  • 第 10 行，使用遍历返回的 *list.Element 的 Value 成员取得放入列表时的原值。

循环链表

  ring的应用：基于滑动窗口的统计。比如最近100次接口调用的平均耗时、最近10笔订单的平均值、最近30个交易日股票的最高点。ring的容量即为滑动窗口的大小，把待观察变量按时间顺序不停地写入ring即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package main

import (
	"container/ring"
	"fmt"
)

func main() {
	//必须指定长度，各元素被初始化为nil
	ring := ring.New(5)
	// 链表中插入元素
	for i := 0; i < 3; i++ {
		ring.Value = i
		ring = ring.Next()
	}

	//通过Do()来遍历ring，内部实际上调用了Next()而非Prev()
	ring.Do(func(a any) {
		fmt.Printf("a: %v\n", a)
	})
}

应用案例

  LRU(Least Recently Used, 最近最少使用)缓存淘汰的总体思路：缓存的key放到链表中，头部的元素表示最近刚使用。

  • 如果命中缓存，从链表中找到对应的key，移到链表头部。
  • 如果没命中缓存：
    • 如果缓存容量没超，放入缓存，并把key放到链表头部。
    • 如果超出缓存容量，删除链表尾部元素，再把key放到链表头部。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
package main

import (
	"container/list"
	"fmt"
	"strconv"
)

type LRUCache struct {
	cache map[int]string
	lst   list.List
	Cap   int //缓存容量的上限
}

func NewLRUCache(cap int) *LRUCache {
	lru := new(LRUCache)
	lru.Cap = cap
	lru.cache = make(map[int]string, cap)
	lru.lst = list.List{}
	return lru
}

func (lru *LRUCache) Add(key int, value string) {
	if len(lru.cache) < lru.Cap { //还没有到达缓存容量上限
		//直接把key value放到缓存中去
		lru.cache[key] = value
		lru.lst.PushFront(key)
	} else { //刚刚到达缓存容量上限
		//先从缓存中淘汰一个元素
		back := lru.lst.Back()
		delete(lru.cache, back.Value.(int)) //interface {} is nil, not int
		lru.lst.Remove(back)
		//然后再把key value放到缓存中去
		lru.cache[key] = value
		lru.lst.PushFront(key)
	}
}

func (lru *LRUCache) find(key int) *list.Element {
	if lru.lst.Len() == 0 {
		return nil
	}
	head := lru.lst.Front()
	for {
		if head == nil {
			break
		}
		if head.Value.(int) == key {
			return head
		} else {
			head = head.Next()
		}
	}
	return nil
}

func (lru *LRUCache) Get(key int) (string, bool) {
	value, exists := lru.cache[key]
	ele := lru.find(key)
	if ele != nil {
		lru.lst.MoveToFront(ele)
	}
	return value, exists
}

func testLRU() {
	lru := NewLRUCache(10)
	for i := 0; i < 10; i++ {
		lru.Add(i, strconv.Itoa(i)) //9 8 7 6 5 4 3 2 1 0
	}

	for i := 0; i < 10; i += 2 {
		lru.Get(i) //8 6 4 2 0 9 7 5 3 1
	}

	for i := 10; i < 15; i++ {
		lru.Add(i, strconv.Itoa(i)) //14 13 12 11 10 8 6 4 2 0
	}

	for i := 0; i < 10; i++ {
		_, exists := lru.Get(i)
		fmt.Printf("key %d exists %t\n", i, exists) //9 7 5 3 1不存在，8 6 4 2 0存在
	}
}

func main() {
	testLRU()
}

运行结果：

key 0 exists true
key 1 exists false
key 2 exists true
key 3 exists false
key 4 exists true
key 5 exists false
key 6 exists true
key 7 exists false
key 8 exists true
key 9 exists false

栈

  栈是一种先进后出的数据结构，push把元素压入栈底，pop弹出栈顶的元素。编程语言的编译系统也用到了栈的思想。

  go自带的List已经包含了栈的功能，这里实现一个线程安全的栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
type (
	node struct {
		value interface{}
		prev  *node
	}
	MyStack struct {
		top    *node
		length int
		lock   *sync.RWMutex
	}
)

func NewMyStack() *MyStack {
	return &MyStack{nil, 0, &sync.RWMutex{}}
}

func (stack *MyStack) Push(value interface{}) {
	stack.lock.Lock()
	defer stack.lock.Unlock()
	n := &node{value, stack.top}
	stack.top = n
	stack.length++
}

func (stack *MyStack) Pop() interface{} {
	stack.lock.Lock()
	defer stack.lock.Unlock()
	if stack.length == 0 {
		return nil
	}
	n := stack.top
	stack.top = n.prev
	stack.length--
	return n.value
}

func (stack *MyStack) Peak() interface{} {
	stack.lock.RLock()
	defer stack.lock.RUnlock()
	if stack.length == 0 {
		return nil
	}
	return stack.top.value
}

func (stack *MyStack) Len() int {
	return stack.length
}

func (stack *MyStack) Empty() bool {
	return stack.Len() == 0
}

栈应用

利用栈容器实现斐波那契序列计算
11235813…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
package main

import (
	"container/list"
	"fmt"
)

func Fib(n int, stack *list.List) int {
	if n == 1 || n == 2 {
		return 1
	}
	stack.PushBack(1)
	stack.PushBack(1)

	for i := 2; i < n; i++ {
		a := stack.Back()
		stack.Remove(a)
		b := stack.Back()
		stack.Remove(b)
		stack.PushBack(a.Value.(int))
		stack.PushBack(a.Value.(int) + b.Value.(int))
	}
	ret := stack.Back().Value.(int)
	return ret
}

func main() {
	l := list.New()
	i := Fib(5000, l)
	fmt.Printf("i: %v\n", i)
}

堆

  堆是一棵二叉树。大根堆即任意节点的值都大于等于其子节点。反之为小根堆。
  用数组来表示堆，下标为 i 的结点的父结点下标为(i-1)/2，其左右子结点分别为 (2i + 1)、(2i + 2)。

构建堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
package main

import "fmt"

//AdjustTraingle 如果只是修改slice里的元素，不需要传slice的指针；如果要往slice里append或让slice指向新的子切片，则需要传slice指针
func AdjustTraingle(arr []int, parent int) {
	left := 2*parent + 1
	if left >= len(arr) {
		return
	}

	right := 2*parent + 2
	minIndex := parent
	minValue := arr[minIndex]
	if arr[left] < minValue {
		minValue = arr[left]
		minIndex = left
	}
	if right < len(arr) {
		if arr[right] < minValue {
			minValue = arr[right]
			minIndex = right
		}
	}
	if minIndex != parent {
		arr[minIndex], arr[parent] = arr[parent], arr[minIndex]
		AdjustTraingle(arr, minIndex) //递归。每当有元素调整下来时，要对以它为父节点的三角形区域进行调整
	}
}

func ReverseAdjust(arr []int) {
	n := len(arr)
	if n <= 1 {
		return
	}
	lastIndex := n / 2 * 2
	fmt.Println(lastIndex)
	for i := lastIndex; i > 0; i -= 2 { //逆序检查每一个三角形区域
		right := i
		parent := (right - 1) / 2
		fmt.Println(parent)
		AdjustTraingle(arr, parent)
	}
}

func buildHeap() {
	arr := []int{62, 40, 20, 30, 15, 10, 49}
	ReverseAdjust(arr)
	fmt.Println(arr)
}

  每当有元素调整下来时，要对以它为父节点的三角形区域进行调整。

插入元素

删除堆顶

下面讲几个堆的应用。
堆排序

  1. 构建堆O(N)。
  2. 不断地删除堆顶O(NlogN)。

求集合中最大的K个元素

  1. 用集合的前K个元素构建小根堆。
  2. 逐一遍历集合的其他元素，如果比堆顶小直接丢弃；否则替换掉堆顶，然后向下调整堆。

把超时的元素从缓存中删除

  1. 按key的到期时间把key插入小根堆中。
  2. 周期扫描堆顶元素，如果它的到期时间早于当前时刻，则从堆和缓存中删除，然后向下调整堆。
      golang中的container/heap实现了小根堆，但需要自己定义一个类，实现以下接口：
  • Len() int
  • Less(i, j int) bool
  • Swap(i, j int)
  • Push(x interface{})
  • Pop() x interface{}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
type Item struct {
	Value    string
	priority int //优先级，数字越大，优先级越高
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int {
	return len(pq)
}

func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].priority > pq[j].priority //golang默认提供的是小根堆，而优先队列是大根堆，所以这里要反着定义Less
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

//往slice里append,需要传slice指针
func (pq *PriorityQueue) Push(x interface{}) {
	item := x.(*Item)
	*pq = append(*pq, item)
}

//让slice指向新的子切片，需要传slice指针
func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]   //数组最后一个元素
	*pq = old[0 : n-1] //去掉最一个元素
	return item
}

Trie树

  trie树又叫字典权。
  现有term集合：{分散，分散精力，分散投资，分布式，工程，工程师}，把它们放到Trie树里如下图:

  Trie树的根节点是总入口，不存储字符。对于英文，第个节点有26个子节点，子节点可以存到数组里；中文由于汉字很多，用数组存子节点太浪费内存，可以用map存子节点。从根节点到叶节点的完整路径是一个term。从根节点到某个中间节点也可能是一个term，即一个term可能是另一个term的前缀。上图中红圈表示从根节点到本节点是一个完整的term。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
package main

import "fmt"

type TrieNode struct {
	Word     rune               //当前节点存储的字符。byte只能表示英文字符，rune可以表示任意字符
	Children map[rune]*TrieNode //孩子节点，用一个map存储
	Term     string
}

type TrieTree struct {
	root *TrieNode
}

//add 把words[beginIndex:]插入到Trie树中
func (node *TrieNode) add(words []rune, term string, beginIndex int) {
	if beginIndex >= len(words) { //words已经遍历完了
		node.Term = term
		return
	}

	if node.Children == nil {
		node.Children = make(map[rune]*TrieNode)
	}

	word := words[beginIndex] //把这个word放到node的子节点中
	if child, exists := node.Children[word]; !exists {
		newNode := &TrieNode{Word: word}
		node.Children[word] = newNode
		newNode.add(words, term, beginIndex+1) //递归
	} else {
		child.add(words, term, beginIndex+1) //递归
	}
}

//walk words[0]就是当前节点上存储的字符，按照words的指引顺着树往下走，最终返回words最后一个字符对应的节点
func (node *TrieNode) walk(words []rune, beginIndex int) *TrieNode {
	if beginIndex == len(words)-1 {
		return node
	}
	beginIndex += 1
	word := words[beginIndex]
	if child, exists := node.Children[word]; exists {
		return child.walk(words, beginIndex)
	} else {
		return nil
	}
}

//traverseTerms 遍历一个node下面所有的term。注意要传数组的指针，才能真正修改这个数组
func (node *TrieNode) traverseTerms(terms *[]string) {
	if len(node.Term) > 0 {
		*terms = append(*terms, node.Term)
	}
	for _, child := range node.Children {
		child.traverseTerms(terms)
	}
}

func (tree *TrieTree) AddTerm(term string) {
	if len(term) <= 1 {
		return
	}
	words := []rune(term)

	if tree.root == nil {
		tree.root = new(TrieNode)
	}

	tree.root.add(words, term, 0)
}

func (tree *TrieTree) Retrieve(prefix string) []string {
	if tree.root == nil || len(tree.root.Children) == 0 {
		return nil
	}
	words := []rune(prefix)
	firstWord := words[0]
	if child, exists := tree.root.Children[firstWord]; exists {
		end := child.walk(words, 0)
		if end == nil {
			return nil
		} else {
			terms := make([]string, 0, 100)
			end.traverseTerms(&terms)
			return terms
		}
	} else {
		return nil
	}
}

func main() {
	tree := new(TrieTree)
	tree.AddTerm("分散")
	tree.AddTerm("分散精力")
	tree.AddTerm("分散投资")
	tree.AddTerm("分布式")
	tree.AddTerm("工程")
	tree.AddTerm("工程师")

	terms := tree.Retrieve("分散")
	fmt.Println(terms)
	terms = tree.Retrieve("人工")
	fmt.Println(terms)
}