go 语言 container 包内都有什么？用 container 包有什么效果？本文整理了这些内容并做了详细介绍。
List
ListElement源码定义
// Element 表示链表的一个元素
type Element struct {
next, prev *Element // 上一个和下一个元素指针
list *List // 元素所在的链表
Value interface{} // 元素值
}
// List 表示一个双向链表
type List struct {
root Element // 链表的根元素
len int // 链表的长度
}
Demo Code:
package main
import (
"container/list"
"fmt"
)
func main() {
var l = list.New()
e0 := l.PushBack(42)
e1 := l.PushFront(13)
e2 := l.PushBack(7)
l.InsertBefore(3, e0)
l.InsertAfter(196, e1)
l.InsertAfter(1729, e2)
for e := l.Front(); e != nil; e = e.Next() {
fmt.Printf("%#v\n", e.Value.(int))
}
}
方法集
List 对应的方法：
type Element
func (e *Element) Next() *Element // 返回该元素的下一个元素，如果没有下一个元素则返回 nil
func (e *Element) Prev() *Element // 返回该元素的前一个元素，如果没有前一个元素则返回 nil
type List
func New() *List // 返回一个初始化的 list
func (l *List) Back() *Element // 获取 list l 的最后一个元素
func (l *List) Front() *Element // 获取 list l 的最后一个元素
func (l *List) Init() *List // list l 初始化或者清除 list l
func (l *List) InsertAfter(v interface{}, mark *Element) *Element // 在 list l 中元素 mark 之后插入一个值为 v 的元素，并返回该元素，如果 mark 不是 list 中元素，则 list 不改变
func (l *List) InsertBefore(v interface{}, mark *Element) *Element // 在 list l 中元素 mark 之前插入一个值为 v 的元素，并返回该元素，如果 mark 不是 list 中元素，则 list 不改变
func (l *List) Len() int // 获取 list l 的长度
func (l *List) MoveAfter(e, mark *Element) // 将元素 e 移动到元素 mark 之后，如果元素 e 或者 mark 不属于 list l，或者 e==mark，则 list l 不改变
func (l *List) MoveBefore(e, mark *Element) // 将元素 e 移动到元素 mark 之前，如果元素 e 或者 mark 不属于 list l，或者 e==mark，则 list l 不改变
func (l *List) MoveToBack(e *Element) // 将元素 e 移动到 list l 的末尾，如果 e 不属于 list l，则 list 不改变
func (l *List) MoveToFront(e *Element) // 将元素 e 移动到 list l 的首部，如果 e 不属于 list l，则 list 不改变
func (l *List) PushBack(v interface{}) *Element // 在 list l 的末尾插入值为 v 的元素，并返回该元素
func (l *List) PushBackList(other *List) // 在 list l 的尾部插入另外一个 list，其中 l 和 other 可以相等
func (l *List) PushFront(v interface{}) *Element // 在 list l 的首部插入值为 v 的元素，并返回该元素
func (l *List) PushFrontList(other *List) // 在 list l 的首部插入另外一个 list，其中 l 和 other 可以相等
func (l *List) Remove(e *Element) interface{} // 如果元素 e 属于 list l，将其从 list 中删除，并返回元素 e 的值
问题：可以把自己生成的 Element 类型的值传给链表吗？
- 这里给出一个 典型回答：不会接受，这些上述的方法将不会对链表做出任何改动。因为我们自己生成的 Element 值并不在链表中，所以也就谈不上 “在链表中移动元素”。更何况链表不允许我们把自己生成的 Element 值插入其中。
- 问题解析：在 List 包包含的方法中，用于插入新元素的那些方法都只接受 interface{} 类型的值。这些方法在内部会使用 Element 值，包装接收到的新元素。这样做正是为了避免直接说使用我们自己生成的元素，主要原因是避免链表的内部关联，遭到外界的破坏，这对于链表本身以及我们这些使用者来说都是有益的。
扩展阅读：
- 链表（Linked list）：是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针 (Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到 O(1) 的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要 O(n) 的时间，而顺序表相应的时间复杂度分别是 O(logn) 和 O(1)。
- 双向链表：又称为双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
知识扩展
问题 1：为什么链表可以做到开箱即用？
List 和 Element 都是结构体类型。结构体类型有一个特点，那就是它们的零值都会拥有特定结构，但是没有任何定制化内容的值，相当于一个空壳。值中的字段也都会被分别赋予各自类型的零值。
var l list.List开箱即用var l list.List延迟初始化延迟初始化
所谓的 延迟初始化：你可以理解为把初始化操作延后，仅在实际需要的时候才进行。延迟初始化的优点在于 “延后”，它可以分散初始化操作带来的计算量和存储空间消耗。
延迟初始化的缺点恰恰也在于“延后”。你可以想象一下，如果我在调用链表的每个方法的时候，它们都需要先去判断链表是否已经被初始化，那这也会是一个计算量上的浪费。在这些方法被非常频繁地调用的情况下，这种浪费的影响就开始显现了，程序的性能将会降低。
Ring
container/ring 包中的 Ring 类型实现的是一个循环链表，也就是我们俗称的环。其实 List 在内部就是一个循环链表。它的根元素永远不会持有任何实际的元素值，而该元素的存在就是为了连接这个循环链表的首尾两端。
所以，也可以说：List 的零值是一个只包含了根元素，但不包含任何实际元素值的空链表。那么，既然 Ring 和 List 的本质上都是循环链表，它们到底有什么不同呢？
Ring 和 List 的不同有以下几种：
- Ring 类型的数据结构仅由它自身即可代表，而 List 类型则需要由它以及 Element 类型联合表示。这是表示方式上的不同，也是结构复杂度上的不同。
- 一个 Ring 类型的值严格来讲，只代表了其所属的循环链表中的一个元素，而一个 List 类型的值则代表了一个完整的链表。这是表示维度上的不同。
- 在创建并初始化一个 Ring 值得时候，我们可以指定它包含的元素数量，但是对于一个 List 值来说却不能这样做（也没必要这样做）。循环链表一旦被创建，其长度是不可变的。这是两个代码包中 New 函数在功能上的不同，也是两个类型在初始化值方面的第一个不同
- 仅通过 var r ring.Ring 语句声明的 r 将会是一个长度为 1 的循环链表，而 List 类型的零值则是一个长度为 0 的链表。别忘了，List 中的根元素不会持有实际元素的值，因此计算长度时不会包含它。这是两个类型在初始化值方面的第二个不同。
- Ring 值得 Len 方法的算法复杂度是 O(N) 的，而 List 值得 Len 方法的算法复杂度是 O(1) 的。这是两者在性能方面最显而易见的差别。
源码定义
type Ring struct {
next, prev *Ring
Value interface{}
}
我们初始化环的时候，需要定义好环的大小，然后对环的每个元素进行赋值。环还提供了一个 Do 方法，能遍历一边环，对每个元素执行一次 func。一个 Demo 如下：
package main
import (
"container/ring"
"fmt"
)
func main() {
// 创建一个环，包含 3 个元素
r := ring.New(3)
fmt.Printf("ring: %+v\n", *r)
// 初始化
for i := 1; i <= 3; i++ {
r.Value = i
r = r.Next()
}
fmt.Printf("init ring: %+v\n", *r)
// sum
s := 0
r.Do(func(i interface{}) {
fmt.Println(i)
s += i.(int)
})
fmt.Printf("sum ring: %d\n", s)
}
方法集
Ring 包含的方法：
type Ring
func New(n int) *Ring // 用于创建一个新的 Ring, 接收一个整形参数，用于初始化 Ring 的长度
func (r *Ring) Len() int // 环长度
func (r *Ring) Next() *Ring // 返回当前元素的下个元素
func (r *Ring) Prev() *Ring // 返回当前元素的上个元素
func (r *Ring) Move(n int) *Ring // 指针从当前元素开始向后移动或者向前 (n 可以为负数）
// Link & Unlink 组合起来可以对多个链表进行管理
func (r *Ring) Link(s *Ring) *Ring // 将两个 ring 连接到一起 (r 不能为空）
func (r *Ring) Unlink(n int) *Ring // 从当前元素开始，删除 n 个元素
func (r *Ring) Do(f func(interface{})) // Do 会依次将每个节点的 Value 当作参数调用这个函数 f, 实际上这是策略方法的引用，通过传递不同的函数以在同一个 ring 上实现多种不同的操作。
通过 Next & Prev 方法也可以对一个 ring 进行便利，首先保存当前节点，然后依次访问下一个节点，直到回到其实节点，Demo 如下：
p := ring.Next()
// do something with the first element
for p != ring {
// do something with current element
p = p.Next()
}
Heap
container/heap 中堆使用的数据结构是最小二叉树，即根节点比左边子树和右边子树的所有值都要小。Go 的堆包只是实现了一个接口，其定义如下：
type Interface interface {
sort.Interface
Push(x interface{}) // Add x as element Len()
Pop() interfaceP{} // remove and return element Len() -1.
}
可以看出，这个堆结构继承自 sort.Interface，回顾下 sort.Interface, 它需要实现三个方法
Len() intLess(i, j int) boolSwap(i, j int)加上堆接口定义的两个方法
Push(x interface{})Pop() interface{}就是说你定义了一个堆，就要实现 5 个方法，package doc 的 example 例子：
思考题
- container/ring 包中的循环链表的适用场景都有哪些？
- 你使用过 container/heap 包中的堆吗？它的适用场景又有那些呢？