Golang的container数据结构 heap/list应用-Golang-PHP中文网

Golang的container数据结构 heap/list应用

P粉602998670

发布： 2025-08-23 10:14:02

原创

563人浏览过

Go的container/list实现双向链表，支持高效插入删除，适用于LRU缓存等场景；2. container/heap需自定义类型实现接口，通过Len、Less、Swap、Push、Pop方法构建堆，常用于优先队列。

golang的container数据结构 heap/list应用

Go语言标准库中的 container 包提供了几种常用的数据结构，其中 heap 和 list 是两个非常实用的实现。虽然Go没有内置泛型（在Go 1.18之前），但通过接口和自定义类型，我们可以灵活使用这些结构。下面分别介绍 list 和 heap 的基本用法及典型应用场景。

container/list：双向链表的使用

container/list 实现了一个通用的双向链表，每个节点包含前驱和后继指针，适合频繁插入和删除的场景。

list 的元素类型是 interface{}，因此可以存储任意类型的数据。

常见操作示例：

创建链表：
```
l := list.New()
```
登录后复制
尾部插入：
```
l.PushBack("hello")
```
登录后复制
头部插入：
```
l.PushFront(42)
```
登录后复制
删除元素：
```
l.Remove(element)
```
登录后复制
遍历链表：通过
```
l.Front()
```
登录后复制
获取头节点，然后用
```
element.Next()
```
登录后复制
逐个访问

应用场景举例：实现LRU缓存时，可以用 list 记录访问顺序，配合 map 快速查找，实现 O(1) 的插入、删除和更新。

立即学习“go语言免费学习笔记（深入）”；

container/heap：堆的构建与操作

container/heap 并不提供现成的堆类型，而是要求你实现一个满足 heap.Interface 的类型，然后通过 heap 包的方法来操作它。

即构数智人

即构数智人是由即构科技推出的AI虚拟数字人视频创作平台，支持数字人形象定制、短视频创作、数字人直播等。

查看详情

你需要实现五个方法：Len, Less, Swap, Push, Pop。其中 Push 和 Pop 是用于堆操作的，不是 slice 的普通操作。

构建最小堆示例：

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 interface{}) {
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

登录后复制

使用堆：