Go标准库容器介绍：list（双向链表）、heap（堆）、ring（圈）
前言
大家在使用Go的时候会不会感觉Go的容器（集合）非常的少，好像只有map和slice两种，其实Go还自带了3个容器类型：list（双向链表）、heap（堆）、ring（圈），虽然还是很少，但是在遇到适合场景的时候直接使用标准库还是比较方便的。
这三个容器位于container包下：
文章使用Go 1.18 Beta 1版本，会涉及到一些泛型的知识，了解泛型可以阅读文章：Go泛型快速入门和Go泛型实战：实现通用slice库
下面将介绍每个容器的使用方式、实现方式和应用。
list-双向链表
双向链表一般用于经常堆头部和尾部进行增删的场景，同时它不需要在一开始初始化它的容量，它的容量随着使用动态变化（扩大or缩小）。
数据结构
Go的双向链表主要包含两个数据结构：
// 链表的一个元素 type Element struct { next, prev *Element // 前后指针 list *List // 所属链表 Value any // 值 } 复制代码// 链表 type List struct { root Element // 哨兵元素 len int // 链表元素个数 } 复制代码哨兵的加入可以让各种操作变得简单一致
初始化
List支持延迟初始化，因此不管你使用list.New()创建一个已经初始化的list，或者直接使用list.List{}创建一个未初始化的list，都可以正常运行。
在调用PushFront()、PushBack()、PushFrontList()、PushBackList()时会调用 lazyInit() 检查是否已经初始化，如果没有初始化则调用 Init() 进行初始化。
package main import ( "container/list" "fmt" ) func main() // 使用list.New()直接初始化 l1 := list.New() l1.PushFront(1) fmt.Println(l1.Front().Value) // 1 // 使用list.List{}延迟初始化 l2 := list.List{} l2.PushFront(2) fmt.Println(l2.Front().Value) // 2 } 复制代码PushFront()、PushBack()、PushFrontList()、PushBackList()
PushFront()、PushBack()分别是在链表头部或尾部添加元素，PushFrontList()、PushBackList()分别是在链表头部或在尾部插入链表
package main import ( "container/list" "fmt" ) func main() { // 新建三个只有一个节点的链表 l1 := list.New() l1.PushFront(1) l2 := list.New() l2.PushBack(2) l3 := list.New() l3.PushBack(3) // 把l1和l3分别链到l2的前面和后面 l2.PushFrontList(l1) l2.PushBackList(l3) // 打印 PrintlnList(l2) //1 //2 //3 } func PrintlnList(l *list.List) { if l.Front() == nil { return } for cur := l.Front(); cur != l.Front().Prev(); cur = cur.Next() { fmt.Println(cur.Value) } } 复制代码Front()、Back()、Len()
分别是获取头元素、获取尾元素、获取长度，都不会对链表修改
package main import ( "container/list" "fmt" ) func main() { // 新建一个有三个节点的链表 l := list.New() l.PushBack(1) l.PushBack(2) l.PushBack(3) fmt.Println(l.Front().Value) // 1 fmt.Println(l.Back().Value) // 3 fmt.Println(l.Len()) // 3 } 复制代码InsertBefore()、InsertAfter()
分别是在某个元素前插入，在某个元素后插入。
package main import ( "container/list" "fmt" ) func main() { // 新建一个有三个节点的链表 l := list.New() l.PushBack(1) e3 := l.PushBack(3) // 这里故意把3这个节点存下来 l.PushBack(5) PrintlnList(l) //1 //3 //5 l.InsertBefore(2, e3) // 在e3前面插入2 l.InsertAfter(4, e3) // 在e3后面插入4 PrintlnList(l) //1 //2 //3 //4 //5 } func PrintlnList(l *list.List) { if l.Front() == nil { return } for cur := l.Front(); cur != l.Front().Prev(); cur = cur.Next() { fmt.Println(cur.Value) } } 复制代码MoveBefore()、MoveAfter()、MoveToFront()、MoveToBack()
分别是移动元素到某个元素前面、移动元素到某个元素后面、移动元素到头部、移动元素到尾部
package main import ( "container/list" "fmt" ) func main() { // 新建一个有三个节点的链表 l := list.New() e5 := l.PushBack(5) e3 := l.PushBack(3) e1 := l.PushBack(1) PrintlnList(l) //5 //3 //1 l.MoveAfter(e5, e3) // 移动e5到e3后面 l.MoveBefore(e1, e3) // 移动e1到e3前面 PrintlnList(l) //1 //3 //5 l.MoveToFront(e5) // 移动e5到头部 l.MoveToBack(e1) // 移动e1到尾部 PrintlnList(l) //5 //3 //1 } func PrintlnList(l *list.List) { if l.Front() == nil { return } for cur := l.Front(); cur != l.Front().Prev(); cur = cur.Next() { fmt.Println(cur.Value) } } 复制代码Remove()
移除元素
package main import ( "container/list" "fmt" ) func main() { // 新建一个有五个节点的链表 l := list.New() l.PushBack(1) l.PushBack(2) e3 := l.PushBack(3) l.PushBack(4) l.PushBack(5) PrintlnList(l) //1 //2 //3 //4 //5 // 移除e3节点 l.Remove(e3) PrintlnList(l) //1 //2 //4 //5 } func PrintlnList(l *list.List) { if l.Front() == nil { return } for cur := l.Front(); cur != l.Front().Prev(); cur = cur.Next() { fmt.Println(cur.Value) } } 复制代码应用
双端队列
package deque import "container/list" type Deque[T any] struct { l *list.List } func New[T any]() *Deque[T] { return &Deque[T]{l: list.New()} } // AddFirst 从队头入队 func (d *Deque[T]) AddFirst(elem T) { d.l.PushFront(elem) } // AddLast 从队尾入队 func (d *Deque[T]) AddLast(elem T) { d.l.PushBack(elem) } // RemoveFirst 从队头出队 func (d *Deque[T]) RemoveFirst() T { return d.l.Remove(d.l.Front()).(T) } // RemoveLast 从队尾出队 func (d *Deque[T]) RemoveLast() T { return d.l.Remove(d.l.Back()).(T) } // Len 队列元素个数 func (d *Deque[T]) Len() int { return d.l.Len() } // Empty 队列是否为空 func (d *Deque[T]) Empty() bool { return d.Len() == 0 } 复制代码栈
package deque import "container/list" type Stack[T any] struct { l *list.List } func New[T any]() *Stack[T] { return &Stack[T]{l: list.New()} } // Push 入栈 func (s *Stack[T]) Push(elem T) { s.l.PushBack(elem) } // Pop 出栈 func (s *Stack[T]) Pop() T { return s.l.Remove(s.l.Back()).(T) } // Peek 栈顶元素 func (s *Stack[T]) Peek() T { return s.l.Back().Value.(T) } // Len 栈元素个数 func (s *Stack[T]) Len() int { return s.l.Len() } // Empty 栈是否为空 func (s *Stack[T]) Empty() bool { return s.Len() == 0 } 复制代码LRU
package lru import "container/list" type kv[K comparable, V any] struct { k K v V } type LRU[K comparable, V any] struct { l *list.List m map[K]*list.Element size int } func New[K comparable, V any](size int) *LRU[K, V] { return &LRU[K, V]{ l: list.New(), m: make(map[K]*list.Element, size), size: size, } } // Put 添加或更新元素 func (l *LRU[K, V]) Put(k K, v V) { // 如果k已经存在，直接把它移到最后面，然后设置新值 if elem, ok := l.m[k]; ok { l.l.MoveToBack(elem) keyValue := elem.Value.(kv[K, V]) keyValue.v = v return } // 如果已经到达最大尺寸，先剔除一个元素 if l.l.Len() == l.size { front := l.l.Front() l.l.Remove(front) delete(l.m, front.Value.(kv[K, V]).k) } // 添加元素 elem := l.l.PushBack(kv[K, V]{ k: k, v: v, }) l.m[k] = elem } // Get 获取元素 func (l *LRU[K, V]) Get(k K) (V, bool) { // 如果存在移动到尾部，然后返回 if elem, ok := l.m[k]; ok { l.l.MoveToBack(elem) return elem.Value.(kv[K, V]).v, true } // 不存在返回空值和false var v V return v, false } 复制代码heap-堆
堆适合于需要数据有序，又需要能够随时添加或移除元素，最好是能够每次取最大或最小元素的场景。
下面是未调整的堆：
调整后的堆：可以看到堆顶是最大的
数据结构
container包下的堆的结构是一个接口，它只定义了5个方法：
heap.Interface接口：
type Interface interface { sort.Interface // sort.Interface接口 Push(x any) // 添加元素x到Len()的位置 Pop() any // 移除并返回Len() - 1位置的元素 } 复制代码sort.Interface接口
type Interface interface { Len() int // 元素个数 Less(i, j int) bool // 比较 Swap(i, j int) // 交换 } 复制代码可以看到，它继承了sort.Interface接口，也就是排序需要的3个操作。
同时它新增了Push()和Pop()两个操作，分别用于把元素添加到列表末尾和从列表末尾删除一个元素。
heap.Interface接口的5个操作的使用下面在heap包提供的函数时进行分析，因为heap包提供的5个函数的第一个参数都需要实现heap.Interface接口。
Init()
初始化堆，这是经典的堆初始化过程，也就三个（或两个）比较，把大的向上移动，从一颗树的中间开始操作（一般底层是一个列表，但是把它想象成树）。
可以看到sort.Interface接口的三个操作都被使用到了。
func Init(h Interface) { n := h.Len() for i := n/2 - 1; i >= 0; i-- { down(h, i, n) } } func down(h Interface, i0, n int) bool { i := i0 for { j1 := 2*i + 1 if j1 >= n || j1 < 0 { // j1 < 0 after int overflow break } j := j1 // left child if j2 := j1 + 1; j2 < n && h.Less(j2, j1) { j = j2 // = 2*i + 2 // right child } if !h.Less(j, i) { break } h.Swap(i, j) i = j } return i > i0 } 复制代码Push()
往堆添加一个元素。可以看到这个操作它先使用heap.Interface接口的Push()方法把元素添加到列表尾部，然后再从最后一个元素向上调整。
func Push(h Interface, x any) { h.Push(x) up(h, h.Len()-1) } 复制代码Pop()
取出堆顶元素，也就是最大或最小的元素。可以看到先把堆顶元素和最后一个元素进行交换，然后从头向下重新调整。最后把列表最后一个元素取出来，也就是通过heap.Interface接口的Pop()方法。
func Pop(h Interface) any { n := h.Len() - 1 h.Swap(0, n) down(h, 0, n) return h.Pop() } 复制代码Remove()
移除某个下标的元素。这个操作其实和Pop类似，只是它移除的数在中间。
func Remove(h Interface, i int) any { n := h.Len() - 1 if n != i { h.Swap(i, n) if !down(h, i, n) { up(h, i) } } return h.Pop() } 复制代码Fix()
从某个下标进行调整。这个操作用于你直接修改列表某个下标的元素的值的时候，可以直接从这个下标进行调整。
func Fix(h Interface, i int) { if !down(h, i, h.Len()) { up(h, i) } } 复制代码直接使用heap包
heap包直接使用很麻烦，因为要为数据实现5个方法：
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 { elem := (*h)[len(*h)-1] *h = (*h)[:len(*h)-1] return elem } func main() { var intHeap IntHeap heap.Init(&intHeap) heap.Push(&intHeap, 5) heap.Push(&intHeap, 3) heap.Push(&intHeap, 4) heap.Push(&intHeap, 2) heap.Push(&intHeap, 1) fmt.Println(heap.Pop(&intHeap)) // 1 fmt.Println(heap.Pop(&intHeap)) // 2 fmt.Println(heap.Pop(&intHeap)) // 3 fmt.Println(heap.Pop(&intHeap)) // 4 fmt.Println(heap.Pop(&intHeap)) // 5 } 复制代码使用泛型包装一下
其实我们只要默认底层数据结构是slice，那么我们完全不需要编写Len()、Swap()、Push()、Pop()这些方法，只需要知道元素如何比较就可以（Less()）。
可以看到我们先实现了一个internalHeap，这个类实现了heap.Interface()接口。而Heap类直接组合了internalHeap，这样只需要暴露出来Push()和Pop()两个堆必须的操作。
package main import ( "container/heap" "fmt" ) type Heap[T any] struct { h *internalHeap[T] } func New[T any](less func(e1 T, e2 T) bool) *Heap[T] { return &Heap[T]{h: newInternalHeap[T](less)} } func (h *Heap[T]) Len() int { return h.h.Len() } func (h *Heap[T]) Push(x T) { heap.Push(h.h, x) } func (h *Heap[T]) Pop() T { return heap.Pop(h.h).(T) } type internalHeap[T any] struct { l []T less func(e1 T, e2 T) bool } func (h *internalHeap[T]) Len() int { return len(h.l) } func (h *internalHeap[T]) Less(i, j int) bool { return h.less(h.l[i], h.l[j]) } func (h *internalHeap[T]) Swap(i, j int) { h.l[i], h.l[j] = h.l[j], h.l[i] } func (h *internalHeap[T]) Push(x any) { h.l = append(h.l, x.(T)) } func (h *internalHeap[T]) Pop() any { elem := h.l[len(h.l)-1] h.l = h.l[:len(h.l)-1] return elem } func newInternalHeap[T any](less func(e1 T, e2 T) bool) *internalHeap[T] { h := &internalHeap[T]{ less: less, } heap.Init(h) return h } func main() { // 创建一个堆 h := New(func(e1 int, e2 int) bool { return e1 > e2 }) // 推入元素 h.Push(5) h.Push(6) h.Push(3) h.Push(7) h.Push(2) h.Push(4) h.Push(8) h.Push(9) h.Push(1) // 取出元素 fmt.Println(h.Pop()) // 9 fmt.Println(h.Pop()) // 8 fmt.Println(h.Pop()) // 7 fmt.Println(h.Pop()) // 6 fmt.Println(h.Pop()) // 5 fmt.Println(h.Pop()) // 4 fmt.Println(h.Pop()) // 3 fmt.Println(h.Pop()) // 2 fmt.Println(h.Pop()) // 1 } 复制代码应用
优先队列
package priority_queue import "github.com/jiaxwu/container/heap" // PriorityQueue 优先队列 type PriorityQueue[T any] struct { h *heap.Heap[T] } func New[T any](less func(e1 T, e2 T) bool) *PriorityQueue[T] { return &PriorityQueue[T]{ h: heap.New(less), } } // Add 入队 func (p *PriorityQueue[T]) Add(elem T) { p.h.Push(elem) } // Remove 出队 func (p *PriorityQueue[T]) Remove() T { return p.h.Pop() } // Len 队列元素个数 func (p *PriorityQueue[T]) Len() int { return p.h.Len() } // Empty 队列是否为空 func (p *PriorityQueue[T]) Empty() bool { return p.Len() == 0 } 复制代码求Top K
大小为K的堆，比如小顶堆，如果遇到比堆顶大的元素，则移除堆顶元素，然后该元素加入堆，这样到最后堆里的元素就是K个最大的。
ring-圈
Ring是一个在循环链表里面的元素，它没有头尾。
空Ring必须是一个nil。
零值Ring是一个元素的Ring。
数据结构
可以看到就是一个经典的双向链表的一个节点的结构
type Ring struct { next, prev *Ring // 前后指针 Value any // 值，使用者自己设置 } 复制代码创建Ring
直接创建
我们可以直接创建圈，只指定我们需要存储的值，不需要管前后指针的初始化，因为Ring的方法都会在执行前检查Ring是否初始化，如果没有初始化则先进行初始化。
package main import ( "container/ring" "fmt" ) func main() { // 创建两个圈 r1 := ring.Ring{Value: 1} r2 := ring.Ring{Value: 2} // 链接两个单圈 r1.Link(&r2) // 遍历整个圈 r1.Do(func(a any) { fmt.Println(a) }) // 1 // 2 } 复制代码使用New()
我们也可以使用New()创建圈，New()的参数是指定要创建圈元素的个数，而且使用New()前后指针是已经初始化好的。
package main import ( "container/ring" "fmt" ) func main() { r1 := ring.New(1) // 创建一个元素的圈 r2 := ring.New(2) // 创建两个元素的圈 r1.Value = 1 r2.Value = 2 // 链接两个单圈 r1.Link(r2) // 遍历整个圈 r1.Do(func(a any) { fmt.Println(a) }) //1 //2 //<nil> } 复制代码New()源码：
func New(n int) *Ring { if n <= 0 { return nil } r := new(Ring) p := r for i := 1; i < n; i++ { p.next = &Ring{prev: p} p = p.next } p.next = r r.prev = p return r } 复制代码Link()、Unlink()
Link()很好理解，就是拼接两个圈；Unlink()就是与当前节点后面的第n + 1个节点进行链接，这样中间的n个节点就被unlink了。
package main import ( "container/ring" "fmt" ) func main() { r1 := ring.New(1) // 创建一个元素的圈 r2 := ring.New(1) // 创建一个元素的圈 r3 := ring.New(1) // 创建一个元素的圈 r1.Value = 1 r2.Value = 2 r3.Value = 3 r1.Link(r2) // 链接两个单圈 r2.Link(r3) // 链接两个单圈 // 遍历整个圈 r1.Do(func(a any) { fmt.Println(a) }) //1 //2 //3 // unlink掉后面1个节点 r1.Unlink(1) // 遍历整个圈 r1.Do(func(a any) { fmt.Println(a) }) //1 //3 } 复制代码Unlink()源码：跟当前节点后面的第n + 1个节点链接。
func (r *Ring) Unlink(n int) *Ring { if n <= 0 { return nil } return r.Link(r.Move(n + 1)) } 复制代码Prev()、Next()、Move()
分别是前一个节点、后一个节点、移动多少个节点（Move(1)==Next()，Move(-1)==Prev())
package main import ( "container/ring" "fmt" ) func main() { r1 := ring.New(1) // 创建一个元素的圈 r2 := ring.New(1) // 创建一个元素的圈 r3 := ring.New(1) // 创建一个元素的圈 r1.Value = 1 r2.Value = 2 r3.Value = 3 r1.Link(r2) // 链接两个单圈 r2.Link(r3) // 链接两个单圈 // 遍历整个圈 r1.Do(func(a any) { fmt.Println(a) }) //1 //2 //3 cur := r1 fmt.Println(cur.Value) // 1 cur = cur.Prev() fmt.Println(cur.Value) // 3 cur = cur.Next() fmt.Println(cur.Value) // 1 cur = cur.Move(3) fmt.Println(cur.Value) // 1 cur = cur.Move(2) fmt.Println(cur.Value) // 3 } 复制代码Len()、Do()
分别是圈元素个数和堆圈中每个元素执行操作。
应用
环形缓冲器（Ring Buffer）
一种生产者消费者模式的结构，而且如果只有一个读线程、一个写线程，二者没有共享的被修改的控制变量，那么可以证明这种情况下不需要并发控制
一致性Hash
一致性哈希算法在1997年由麻省理工学院提出，是一种特殊的哈希算法，目的是解决分布式缓存的问题。在移除或者添加一个服务器时，能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系。一致性哈希解决了简单哈希算法在分布式哈希表( Distributed Hash Table，DHT) 中存在的动态伸缩等问题。（来自百度百科）
总结
Go标准库中的三种数据结构都非常的灵活，当然可能易用性比较一般，但是只要根据自己的场景对它们进行封装，加上泛型的支持，还有平时常用的map和slice，基本上是足够日常开发的。
作者：XHSF
链接：https://juejin.cn/post/7042729165400834056