Go容器：双向链表和小根堆的源码解读
·
List
container/list
go实现的list就像是一个可以双端操作的双向链表，队头可进可出、队尾可进可出
通过阅读代码，本质上是对insert和remove操作的封装
List结构
- 首先看一下链表中存储的元素结构
// Element是链表中的元素
type Element struct {
// 双向链表中元素的后向（Next）和前向（Previous）指针。
// 为简化实现，链表 l 在内部通过环形结构实现：
// 即 &l.root 既是链表最后一个元素（l.Back ()）的后向元素，
// 同时也是链表第一个元素（l.Front ()）的前向元素。
next, prev *Element
// Element属于的链表
list *List
// 存储的元素的值
Value any
}
通过注释发现，list是一个循环链表
理论上，双向链表有一个头节点，一个尾节点，可能是为了节省空间降低GC，省去了一个节点，只用一个节点既充当尾节点又充当头节点
type List struct {
// List 表示一个双向链表。
// List 的零值（默认初始化值）即为一个可直接使用的空链表。
// 哨兵链表节点，仅使用 &root、root.prev 和 root.next 这三个字段
root Element
// 链表的长度，不包括哨兵节点，既元素的个数
len int
}
// 初始化或者清除链表
func (l *List) Init() *List {
l.root.next = &l.root
l.root.prev = &l.root
l.len = 0
return l
}
// 返回一个新的初始化链表
func New() *List { return new(List).Init() }
// lazyInit lazily initializes a zero List value.
// lazyInit 用于延迟初始化 List 类型的零值（实例）。
func (l *List) lazyInit() {
if l.root.next == nil {
l.Init()
}
}
可以发现，List可以延迟初始化，也就是不用提前New一个链表，也可以直接用，但是只能使用Push系列的方法，在以下代码中也有所体现
写入接口
Insert系列
| 接口 | 含义 | 函数原型 |
|---|---|---|
| InsertAfter | 在mark之后插入新元素，并返回新元素 | func (l *List) InsertAfter(v any, mark *Element) *Element |
| InsertBefore | 在mark之前插入新元素，并返回新元素 | func (l *List) InsertBefore(v any, mark *Element) *Element |
insert辅助函数 |
// insertValue 是 insert (&Element {Value: v}, at) 的便捷包装函数。
func (l *List) insertValue(v any, at *Element) *Element {
return l.insert(&Element{Value: v}, at)
}
// insert 会将元素 e 插入到 at 之后，增加 l 的长度，并返回 e。
func (l *List) insert(e, at *Element) *Element {
// 前四个步骤就是双向链表的插入操作
e.prev = at
e.next = at.next
e.prev.next = e
e.next.prev = e
// e归属的list就是l
e.list = l
// 元素个数递增
l.len++
return e
}
// InsertBefore 会创建一个值为 v 的新元素 e，并将其直接插入到 mark 之前，然后返回 e。
// 若 mark 不是链表 l 中的元素，则链表不会被修改。
// mark 不能为 nil（空值）。
func (l *List) InsertBefore(v any, mark *Element) *Element {
// 判断mark是否属于链表l
// 确保元素插入到当前链表中
if mark.list != l {
return nil
}
// 参见 List.Remove 方法中关于 l（链表）初始化的注释。
// insert的本质是插入到节点的后面，这里是在mark节点前插入，所以要插入mark前一个节点的后面
return l.insertValue(v, mark.prev)
}
// InsertAfter 会创建一个值为 v 的新元素 e，并将其直接插入到 mark 之后，然后返回 e。
// 若 mark 不是链表 l 中的元素，则链表 l 不会被修改。
//mark 不能为 nil（空值）。
func (l *List) InsertAfter(v any, mark *Element) *Element {
if mark.list != l {
return nil
}
// 参见 List.Remove 方法中关于 l（链表）初始化的注释。
return l.insertValue(v, mark)
}
Push系列
| 接口 | 含义 | 函数原型 |
|---|---|---|
| PushFront | 从链表头部插入一个元素，其实是在root之后插入一个元素 | func (l *List) PushFront(v any) *Element |
| PushBack | 从链表尾部插入一个元素，其实就是在root.prev之后插入一个元素 | func (l *List) PushBack(v any) *Element |
| PushFrontList | 将传入的参数链表插入当前链表头部，从最后一个节点开始头插 | func (l *List) PushFrontList(other *List) |
| PushBackList | 将传入的参数链表插入当前链表尾部，从第一个节点开始尾插 | func (l *List) PushBackList(other *List) |
// PushFront 会在链表 l 的头部插入一个值为 v 的新元素 e，并返回该元素 e。
func (l *List) PushFront(v any) *Element {
l.lazyInit()
// 在root之后插入新的节点
return l.insertValue(v, &l.root)
}
// PushBack 会在链表 l 的尾部插入一个值为 v 的新元素 e，并返回该元素 e。
func (l *List) PushBack(v any) *Element {
l.lazyInit()
// root的之后插入，是头插
// root前一个节点的之后，是尾插
return l.insertValue(v, l.root.prev)
}
// PushFrontList 会将另一个链表（other）的副本插入到链表 l 的头部。
// 链表 l 和 other 可以是同一个链表，但两者都不能为 nil（空值）。
func (l *List) PushFrontList(other *List) {
l.lazyInit()
// 从尾节点开始采用头插法
for i, e := other.Len(), other.Back(); i > 0; i, e = i-1, e.Prev() {
// 每次插入都要构造新的节点所以是副本
l.insertValue(e.Value, &l.root)
}
}
// PushBackList 会将另一个链表（other）的副本插入到链表 l 的尾部。
// 链表 l 和 other 可以是同一个链表，但两者都不能为 nil（空值）。
func (l *List) PushBackList(other *List) {
l.lazyInit()
// 从头节点开始尾插
for i, e := other.Len(), other.Front(); i > 0; i, e = i-1, e.Next() {
l.insertValue(e.Value, l.root.prev)
}
}
发现一个遍历链表的好方式
// 本质上就是链表的遍历方式，只不过list包装成了接口
// 正向遍历
for e:=list.Front();e!=nil;e=e.Next(){
fmt.Println(e)
}
// 反向遍历
for e:=list.Back();e!=nil;e=e.Prev(){
fmt.Println(e)
}
移除接口
| 接口 | 含义 | 函数原型 |
|---|---|---|
| Remove | 将元素从链表中移除，并返回移除元素 | func (l *List) Remove(e *Element) any |
remove辅助函数
// 从list中移除元素，并减少元素个数
// 核心就是链表移除元素的操作
func (l *List) remove(e *Element) {
// 链表的删除元素操作
e.prev.next = e.next
e.next.prev = e.prev
// 对象失去引用关系变为不可达对象就会被回收
e.next = nil // avoid memory leaks
e.prev = nil // avoid memory leaks
e.list = nil
l.len--
}
// Remove 方法会将元素 e 从链表 l 中移除（前提是 e 是链表 l 的元素）。
// 该方法返回元素 e 所存储的值 e.Value。
// 待移除的元素 e 不能为 nil（空值）。
func (l *List) Remove(e *Element) any {
if e.list == l {
// if e.list == l, l must have been initialized when e was inserted
// in l or l == nil (e is a zero Element) and l.remove will crash
l.remove(e)
}
return e.Value
}
list.remove中有个e.next=nil,e.prev=nil,e.list=nil指针置空的操作，这样做可以让不再使用的指针对象失去引用关系，从而变为不可达对象，GC时被回收，从而避免内存泄露
从链表中删除元素的前提：
- 若 e.list == l，则有两种情况：要么 e 插入 l 时 l 已完成初始化，
- 要么 l == nil（即 e 是零值 Element）—— 而后者会导致 l.remove 触发崩溃。
Move接口
remove+push
| 接口 | 含义 | 函数原型 |
|---|---|---|
| MoveToFront | 将元素移动到链表的头部，既root的后面 | func (l *List) MoveToFront(e *Element) |
| MoveToBack | 将元素移动到链表的尾部，即root.prev的后面 | func (l *List) MoveToBack(e *Element) |
| MoveBefore | 将元素移动到mark.prev的后面 | func (l *List) MoveBefore(e, mark *Element) |
| MoveAfter | 将元素移动到mark的后面 | func (l *List) MoveAfter(e, mark *Element) |
move辅助函数
// 将元素e移动到元素st之后
func (l *List) move(e, at *Element) {
if e == at {
return
}
// 从原有位置移除
e.prev.next = e.next
e.next.prev = e.prev
// 插入at之后
e.prev = at
e.next = at.next
e.prev.next = e
e.next.prev = e
}
// MoveToFront 会将元素 e 移动到链表 l 的头部。
// 若 e 不是链表 l 中的元素，则链表不会被修改。
// 该元素 e 不能为 nil（空值）。
func (l *List) MoveToFront(e *Element) {
// e不属于链表l，或者，root的下一个节点就是e，直接返回
if e.list != l || l.root.next == e {
return
}
// see comment in List.Remove about initialization of l
// 插入到root的后面
l.move(e, &l.root)
}
// MoveToBack 会将元素 e 移动到链表 l 的尾部。
// 若 e 不是链表 l 中的元素，则链表不会被修改。
// 该元素 e 不能为 nil（空值）。
func (l *List) MoveToBack(e *Element) {
// e不属于链表，或者，root的前一个节点就是e
if e.list != l || l.root.prev == e {
return
}
// see comment in List.Remove about initialization of l
// 插入到root.prev的后面
l.move(e, l.root.prev)
}
// MoveBefore 会将元素 e 移动到 mark 之前的新位置。
// 若 e 或 mark 不是链表 l 中的元素，或者 e == mark，则链表不会被修改。
// 元素 e 和 mark 都不能为 nil（空值）。
func (l *List) MoveBefore(e, mark *Element) {
if e.list != l || e == mark || mark.list != l {
return
}
l.move(e, mark.prev)
}
// MoveAfter 会将元素 e 移动到 mark 之后的新位置。
// 若 e 或 mark 不是链表 l 中的元素，或者 e 与 mark 为同一个元素（e == mark），则链表不会被修改。
// 元素 e 和 mark 都不能为 nil（空值）。
func (l *List) MoveAfter(e, mark *Element) {
if e.list != l || e == mark || mark.list != l {
return
}
l.move(e, mark)
}
读取接口
| 接口 | 含义 | 函数原型 |
|---|---|---|
| Front | 获取链表首部元素 | func (l *List) Front() *Element |
| Back | 获取链表尾部元素 | func (l *List) Back() *Element |
| Element.Next | 获取e的下一个元素，既e.next | func (e *Element) Next() *Element |
| Element.Prev | 获取e的前一个元素，既e.prev | func (e *Element) Prev() *Element |
// Next returns the next list element or nil.
func (e *Element) Next() *Element {
// 因为list是一个循环链表，所以要多一层判断
// p!=e.list.root
if p := e.next; e.list != nil && p != &e.list.root {
return p
}
return nil
}
// Prev returns the previous list element or nil.
func (e *Element) Prev() *Element {
if p := e.prev; e.list != nil && p != &e.list.root {
return p
}
return nil
}
// Front returns the first element of list l or nil if the list is empty.
func (l *List) Front() *Element {
if l.len == 0 {
return nil
}
return l.root.next
}
// Back returns the last element of list l or nil if the list is empty.
func (l *List) Back() *Element {
if l.len == 0 {
return nil
}
return l.root.prev
}
用List实现LRU
type entry struct{
key,val int
}
type LRUCache struct {
cap , len int
list *list.List
ma map[int]*list.Element
}
func Constructor(capacity int) LRUCache {
return LRUCache{
cap:capacity,
list:list.New(),
ma:make(map[int]*list.Element,capacity),
}
}
func (this *LRUCache) Get(key int) int {
node,ok:=this.ma[key]
if ok{
this.list.MoveToFront(node)
return node.Value.(entry).val
}
return -1
}
func (this *LRUCache) Put(key int, value int) {
node,ok:=this.ma[key]
if ok{
node.Value = entry{key,value}
this.list.MoveToFront(node)
}else{
data:=entry{key,value}
for this.len >= this.cap{
ele:=this.list.Remove(this.list.Back())
// 一定要记得从哈希表中删除
delete(this.ma,ele.(entry).key)
this.len--
}
ele:=this.list.PushFront(data)
this.ma[key]=ele
this.len++
}
}
Heap
container/heap
基本用法
// 包 heap 为所有实现了 heap.Interface 接口的类型提供堆操作。堆是一种树形数据结构，其特性为：树中的每个节点都是其所在子树中的最小值节点。
// 树中的最小元素是根节点，位于索引 0 处。
// 堆是实现优先级队列的常用方式。若要构建优先级队列，需实现 Heap 接口，其中 Less 方法需以（负的）优先级作为排序依据
// 这样一来，Push 方法会向队列中添加元素，而 Pop 方法会从队列中移除优先级最高的元素。
// 示例代码中包含了此类实现；完整源代码可参见文件 example_pq_test.go。
// Interface 类型定义了使用本包中函数所需满足的类型要求。
// 任何实现了该接口的类型，都可作为最小堆使用，且需满足以下不变式（在调用 [Init] 之后、或数据为空、或数据已排序的情况下成立）：
// 对于 0 <= i < h.Len ()、2_i+1 <= j <= 2_i+2 且 j <h.Len () 的情况，需满足！h.Less (j, i)
// 注意：此接口中的 [Push] 和 [Pop] 方法是供 heap 包内部实现调用的。若要向堆中添加元素或从堆中移除元素，
// 需使用 [heap.Push] 和 [heap.Pop] 函数。
- 从源代码的注释中可以得出，使用
heap之前，需要先实现heap.Interface接口； - “树中的最小元素是根节点”，所以默认实现的是小根堆，若要实现大根堆可以调整
Less函数的具体实现
heap.Interface具体细节如下，sort.Interface在src/sort/sort.go
type Interface interface {
sort.Interface // 嵌入式继承
Push(x any) // add x as element Len()
Pop() any // remove and return element Len() - 1.
}
// 实现了 Interface 接口的类型，可以通过本包中的函数进行排序。
// 接口中的方法通过整数索引来引用底层集合中的元素。
type Interface interface {
// 集合中的元素个数
Len() int
// Less 方法用于判断索引 i 对应的元素是否必须排在索引 j 对应的元素之前。
// 若 Less (i, j) 和 Less (j, i) 均为 false，则认为索引 i 和 j 对应的元素相等。Sort 函数在最终结果中可能会以任意顺序排列相等的元素，
// 而 Stable 函数会保留相等元素在原始输入中的顺序。
// Less 方法必须定义一个可传递的排序规则：
// - 若 Less (i, j) 和 Less (j, k) 均为 true，则 Less (i, k) 也必须为 true。
// - 若 Less (i, j) 和 Less (j, k) 均为 false，则 Less (i, k) 也必须为 false。
// 注意：当涉及非数字（NaN）值时，浮点型比较（对 float32 或 float64 类型使用 < 运算符）不满足可传递的排序规则。
// 关于浮点型值的正确比较实现，可参考Float64Slice.Less 方法。
Less(i, j int) bool
// 交换索引为i,j位置的元素
Swap(i, j int)
}
源码中还特意提醒：对于浮点数的比较可以参考Float64Slice.Less方法
使用heap之前必须要实现的接口如下
| 实现的方法 | 含义 | 函数原型 |
|---|---|---|
| Less | 属于sort包 | Less(i, j int) bool |
| Swap | 属于sort包 | Swap(i, j int) |
| Len | 属于sort包 | Len() int |
| Push | 属于heap包 | Push(x any) |
| Pop | 属于heap包 | Pop() any |
- 一个小小的实现案例
这里有一个小小的技巧，对于Less、Swap、Len方法的实现采用的是值接收器，原因如下 - 对于值接收器，go会默认实现对应的指针接收器，所以实际上指针接收器实现了
heap.Interface - 这样写的好处是写起来简单，如果使用指针接收器，需要这样写：
(*h)[i]<(*h)[j]
type myheap []int
// 值接收器会实现对应的指针接收器
func (h myheap) Less(i, j int) bool {
return h[i] > h[j]
}
func (h myheap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h myheap) Len() int {
return len(h)
}
func (h *myheap) Push(v any) {
*h = append(*h, v.(int))
}
func (h *myheap) Pop() any {
x := (*h)[len(*h)-1]
*h = (*h)[:len(*h)-1]
return x
}
func main() {
var h myheap
rand.Seed(time.Now().UnixNano())
for i := 0; i < 10; i++ {
x := rand.Intn(100)
heap.Push(&h, x)
}
heap.Init(&h)
for len(h) != 0 {
x := heap.Pop(&h)
fmt.Println(x.(int))
}
}
初始化堆 && 调整堆
| 方法 | 含义 | 函数原型 |
|---|---|---|
| Init | 从最后一个非叶子节点开始执行down操作初始化堆 | func Init(h Interface) |
// Init 方法会建立本包中其他函数所需的堆不变式（即堆的结构约束）。
// 对于堆不变式而言，Init 方法具有幂等性 —— 无论调用多少次，只要堆不变式的状态一致，结果都相同；
// 当堆不变式可能已被破坏时，均可调用该方法重新恢复。
// 该方法的时间复杂度为 O (n)，其中 n 等于堆的长度 h.Len ()。
func Init(h Interface) {
// heapify
n := h.Len()
for i := n/2 - 1; i >= 0; i-- {
down(h, i, n)
}
}
堆操作的核心就是down和up操作
// 未导出的辅助函数
func up(h Interface, j int) {
for {
i := (j - 1) / 2 // parent
if i == j || !h.Less(j, i) {
break
}
h.Swap(i, j)
j = i
}
}
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 | 向堆中添加一个元素，添加到len的位置，并向上调整 | func Push(h Interface, x any) |
| Pop | 将堆顶元素既0号元素和len-1号元素交换，然后向下调整0号元素 | func Pop(h Interface) any |
| Remove | 将索引i位置的元素和索引len-1位置的元素交换，然后down或者up索引i处的元素 | func Remove(h Interface, i int) any |
| Fix | 对索引i位置的元素执行down操作或者up操作 | func Fix(h Interface, i int) |
如果想要使用Remove\Fix方法需要在自定义结构中增加一个index字段，指明元素在堆中的索引位置
// Push 会将元素 x 压入堆中。
// 该操作的时间复杂度为 O (log n)，其中 n 等于堆的长度 h.Len ()。
func Push(h Interface, x any) {
// h.Push是在自己实现的push方法
h.Push(x)
up(h, h.Len()-1)
}
// Pop 会从堆中移除并返回最小元素（依据 Less 方法的定义）。
// 该操作的时间复杂度为 O (log n)，其中 n 等于堆的长度 h.Len ()。
// Pop 操作等价于调用 [Remove](h, 0)（即从堆中移除索引 0 处的元素）。
func Pop(h Interface) any {
n := h.Len() - 1
h.Swap(0, n)
down(h, 0, n)
return h.Pop()
}
// Remove 会从堆中移除索引 i 处的元素，并返回该元素。
// 该操作的时间复杂度为 O (log n)，其中 n 等于堆的长度 h.Len ()。
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 会在索引 i 处元素的值发生改变后，重新建立堆的排序顺序（即恢复堆不变式）。
// 修改索引 i 处元素的值后调用 Fix，与先调用 [Remove](h, i)（移除该元素）再 Push 新值的效果相同，但前者的开销更低。
// 该操作的时间复杂度为 O (log n)，其中 n 等于堆的长度 h.Len ()。
func Fix(h Interface, i int) {
if !down(h, i, h.Len()) {
up(h, i)
}
}
用Heap实现LFU
460. LFU 缓存 - 力扣（LeetCode）
哈希表+小根堆
type entry struct{
key,val int
freq int
index int
}
type mh []*entry
func(h mh)Len()int{return len(h)}
func(h mh)Less(i,j int)bool{return h[i].freq<h[j].freq}
func(h mh)Swap(i,j int){h[i],h[j]=h[j],h[i];h[i].index=i;h[j].index=j}
func(h *mh)Push(v any){*h=append(*h,v.(*entry))}
func(h *mh)Pop()any{x:=(*h)[len(*h)-1];*h=(*h)[:len(*h)-1];return x}
type LFUCache struct {
cap,cou int
freqtree mh
ma map[int]*entry
}
func Constructor(capacity int) LFUCache {
lfu:=LFUCache{
cap:capacity,
freqtree:make([]*entry,0,capacity),
ma:make(map[int]*entry,capacity),
}
// heap.Init(&lfu.freqtree)
return lfu
}
func (this *LFUCache) Get(key int) int {
node,ok:=this.ma[key]
if ok{
node.freq+=1
heap.Fix(&this.freqtree,node.index)
return node.val
}
return -1
}
func (this *LFUCache) Put(key int, value int) {
node,ok:=this.ma[key]
if ok{
node.freq+=1
node.val=value
heap.Fix(&this.freqtree,node.index)
}else{
data:=&entry{key:key,val:value}
for this.cou >= this.cap{
v:=heap.Pop(&this.freqtree)
delete(this.ma,v.(*entry).key)
this.cou--
}
heap.Push(&this.freqtree,data)
this.ma[key]=data
this.cou++
}
}
参考资料
码道开发者社区，聚焦华为云码道 CodeArts 代码智能体，沉淀 Agent、Skill、鸿蒙开发实战内容，供开发者查阅资料、交流技术、分享工程实践
更多推荐
21
0- 0
已为社区贡献2条内容
所有评论(0)