Go标准库容器介绍：list（双向链表）、heap（堆）、ring（圈） |
您所在的位置：网站首页 › 钢圈结构标准数据 › Go标准库容器介绍：list（双向链表）、heap（堆）、ring（圈） |
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 // }New()源码： func New(n int) *Ring { if n |
【本文地址】
今日新闻 |
推荐新闻 |