Golang Container

# 基本介绍

Go的container包提供了三种数据结构的实现，包括堆（heap）、双向列表（list）、环形列表（ring）。

# `container/heap`

# 数据结构

完全二叉树：在完全二叉树中，所有的层都被完全填满，除了可能的最后一层。在最后一层，所有的节点都尽可能地向左对齐。
堆是特殊的完全二叉树，特殊点在于父节点与其子节点的大小关系：
- 对于最小堆：父节点的值总是小于或等于其子节点的值。
- 对于最大堆：父节点的值总是大于或等于其子节点的值。

借用一张图说明一下（src）

# 适用场景

数据流的实时处理：比如要持续跟踪最大或最小的N个元素。
任务调度：使用优先级队列管理任务的执行优先级。
带优先级的待处理列表：如操作系统中进程调度，或网络路由中的包调度。
图算法：如 Dijkstra 算法或 Prim 算法中使用堆来优化性能。

# 实现接口

要使用 container/heap 包，必须实现 heap.Interface 这个接口，包含以下方法：

Len() int：返回堆中的元素数量。
Less(i, j int) bool：比较索引为 i 和 j 的元素，若第一个元素应当排在第二个元素之前，则返回 true。
- 如果要实现最小堆，则前一个元素要小于后一个元素；
- 如果要实现最大堆，则前一个元素要大于后一个元素。
Swap(i, j int)：交换索引为 i 和 j 的元素。
Push(x interface{})：将元素 x 添加到堆的末尾。
Pop() interface{}：从堆中移除并返回最后一个元素（即最大/小元素）。

# 可用方法

方法	说明	时间复杂度
`Init(h Interface)`	对提供的堆进行初始化或重新构建。	O(n)
`Push(h Interface, x interface{})`	向堆中插入新元素 x。	O(logn)
`Pop(h Interface) interface{}`	从堆中取出并返回最顶端的元素，在最小堆中是最小元素，在最大堆中是最大元素。	O(logn)
`Remove(h Interface, i int) interface{}`	移除并返回索引 i 处的元素。	O(logn)
`Fix(h Interface, i int)`	在修改了堆中索引 i 处的元素后，调用此方法以修复堆的结构。	O(logn)

# 使用示例

官方示例提供了一个整数最小堆的例子。

 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/heap"
	"fmt"
)

// 实现方法
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x any) { *h = append(*h, x.(int))}
func (h *IntHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

// 使用
func main() {
	h := &IntHeap{2, 1, 5}
	heap.Init(h)
	heap.Push(h, 3)
	fmt.Printf("minimum: %d\n", (*h)[0])
	for h.Len() > 0 {
		fmt.Printf("%d ", heap.Pop(h))
	}
}

# 动手实践

Leetcode
- 简单 703. 数据流中的第 K 大元素
- 中等 347. 前 K 个高频元素
- 困难 23. 合并 K 个升序链表
- 困难 630. 课程表 III

# `container/list`

# 数据结构

双向链表：是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。

源码定义

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


// 双向链表
type List struct {
    root Element    // 根节点
    len  int        // 长度
}

// 链表元素
type Element struct {
    next, prev *Element // 前/后节点的指针
    list *List          // 所在链表的指针
    Value any           // 该节点的值
}

# 适用场景

需要频繁插入和删除元素的场景：如任务调度、事件处理队列等，链表可以在任意位置快速插入或删除节点。
实现其他复杂数据结构：例如堆栈、队列、双端队列等。
需要双向遍历的情况：双向链表可以从头到尾或从尾到头遍历。

# 可用方法

方法	说明	时间复杂度
`New() *List`	创建并返回一个新的空链表。	O(1)
`Len() int`	返回链表长度。	O(1)
`PushFront(v interface{}) *Element`	在链表的前端添加一个新元素，返回新元素的指针。	O(1)
`PushBack(v interface{}) *Element`	在链表的末尾添加一个新元素，返回新元素的指针。	O(1)
`InsertBefore(v any, mark Element) Element`	在指定元素的前面添加一个新元素，返回新元素的指针。	O(1)
`InsertAfter(v any, mark Element) Element`	在指定元素的后面添加一个新元素，返回新元素的指针。	O(1)
`MoveToFront(e *Element)`	把指定元素移动到链表的前端。	O(1)
`MoveToBack(e *Element)`	把指定元素移动到链表的末尾。	O(1)
`MoveBefore(e, mark *Element)`	把一个元素移动到另一个元素之前。	O(1)
`MoveAfter(e, mark *Element)`	把一个元素移动到另一个元素之后。	O(1)
`PushBackList(other *List)`	将另一个链表的内容添加到当前链表的末尾。	O(1)
`PushFrontList(other *List)`	将另一个链表的内容添加到当前链表的前端。	O(1)
`Remove(e *Element) interface{}`	从链表中删除指定元素，返回该元素中存储的数据。	O(1)
`Front() *Element`	获取链表的第一个元素。	O(1)
`Back() *Element`	获取链表的最后一个元素。	O(1)

# 使用示例

官方示例

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


package main

import (
	"container/list"
	"fmt"
)

func main() {
	// Create a new list and put some numbers in it.
	l := list.New()
	e4 := l.PushBack(4)
	e1 := l.PushFront(1)
	l.InsertBefore(3, e4)
	l.InsertAfter(2, e1)

	// Iterate through list and print its contents.
	for e := l.Front(); e != nil; e = e.Next() {
		fmt.Println(e.Value)
	}
}

# 动手实践

Leetcode
- 简单 705. 设计哈希集合
- 简单 706. 设计哈希映射

# 源码学习

除了通过调用l := list.New()方法，也可以直接声明变量var l list.List获得一个List实例，这是因为有lazyInit的存在。

lazyInit的实现如下，主要用于检查根节点的next元素是否为nil

1
2
3
4
5


func (l *List) lazyInit() {
    if l.root.next == nil {
        l.Init()
    }
}

lazyInit使用如下，在所有push方法调用时，先做lazy init

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


func (l *List) PushFront(v any) *Element {
    l.lazyInit()
    ...
}

func (l *List) PushBack(v any) *Element {
    l.lazyInit()
    ...
}

func (l *List) PushBackList(other *List) {
    l.lazyInit()
    ...
}

func (l *List) PushFrontList(other *List) {
    l.lazyInit()
    ...
}

# `container/ring`

# 数据结构

双向链表：是链表的一种，其中的最后一个元素指向第一个元素，形成一个闭环。

源码定义

1
2
3
4


type Ring struct {
    next, prev *Ring    // 前/后节点的指针
    Value      any      // 该节点的值
}

# 适用场景

资源池管理：循环使用一组固定的资源。
轮询调度：在操作系统中，为了实现时间片轮转调度。
游戏编程：管理游戏中的循环事件或状态，如回合制游戏中的玩家顺序。

# 可用方法

方法	说明	时间复杂度
`New(n int) *Ring`	创建并返回一个由 `n` 个元素组成的环形链表。如果 `n` 为0，则返回值为 `nil`。	O(n)
`Next() *Ring`	返回当前环的下一个元素。	O(1)
`Prev() *Ring`	返回当前环的前一个元素。	O(1)
`Move(n int) *Ring`	将当前环节点向前或向后移动 `n` 步。如果 `n` 为正，则向前（顺时针）移动；如果 `n` 为负，则向后（逆时针）移动。	O(n)
`Link(s Ring) Ring`	在当前环节点后插入另一个环 `s`，并返回被插入的环 `s` 的第一个元素。如果 `s` 为空，则不进行操作并返回当前环。	O(1)
`Unlink(n int) *Ring`	从当前环节点开始，删除 `n` 个元素，并返回被删除元素组成的新环。如果 `n` 大于环的长度，则整个环被清空。	O(n)
`Do(f func(interface{}))`	对环中的每个元素执行函数 `f`。函数 `f` 被调用的次数等于环的长度。	O(n)
`Len() int`	返回环中的元素总数。	O(n)

# 使用示例

官方示例

 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


package main

import (
    "container/ring"
    "fmt"
)

func main() {
    // 创建一个新的环形链表，包含3个元素
    r := ring.New(3)

    // 初始化环形链表：填充数字
    for i := 0; i < 3; i++ {
        r.Value = i
        r = r.Next()
    }

    // 打印环形链表元素
    r.Do(func(p interface{}) {
        fmt.Println("value:", p)
    })

    // 移动并打印
    r = r.Move(10)
    fmt.Println("Current value:", r.Value)
}

# 基本介绍

# container/heap

# 数据结构

# 适用场景

# 实现接口

# 可用方法

# 使用示例

# 动手实践

# container/list

# 数据结构

# 适用场景

# 可用方法

# 使用示例

# 动手实践

# 源码学习

# container/ring

# 数据结构

# 适用场景

# 可用方法

# 使用示例

# 动手实践

# 参考

# `container/heap`

# `container/list`

# `container/ring`