怎样用Golang的container库实现数据结构 heap/list/ring用法

访客科技 2025-12-17 2.2K

container/list实现双向链表，支持高效插入删除；2. container/heap需自定义类型实现堆接口，适用于优先队列；3. container/ring为循环链表，适合环形数据处理。

怎样用Golang的container库实现数据结构 heap/list/ring用法-第1张图片-佛山资讯网

Golang 的 container 包提供了三个常用的数据结构实现：heap、list 和 ring。它们分别适用于不同场景。下面逐一说明用法和实际示例。

1. container/list：双向链表

list 包实现了双向链表，可以高效地在头部、尾部或中间插入/删除元素。

基本用法：

创建链表：list.New() 或 var l list.List
添加元素：PushFront()、PushBack()
删除元素：Remove(element)
遍历：通过 Front() 获取头节点，用 Next() 向后遍历

示例：

package main

import (
    "container/list"
    "fmt"
)

func main() {
    l := list.New()
    l.PushBack(1)
    l.PushBack(2)
    l.PushFront(0)

    for e := l.Front(); e != nil; e = e.Next() {
        fmt.Print(e.Value, " ") // 输出: 0 1 2
    }
}

2. container/heap：最小堆（需自定义实现）

heap 包提供堆操作接口，但需要你实现 heap.Interface，即满足 sort.Interface 并加上 Push 和 Pop 方法。

实现步骤：

定义一个切片类型（如 []int）并实现 5 个必要方法
使用 heap.Init 初始化
用 heap.Push 和 heap.Pop 操作

示例：最小堆

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 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
}

func main() {
    h := &IntHeap{3, 1, 4}
    heap.Init(h)
    heap.Push(h, 2)

    for h.Len() > 0 {
        fmt.Print(heap.Pop(h), " ") // 输出: 1 2 3 4
    }
}

3. container/ring：循环链表（环形结构）

ring 实现了一个单向循环链表，每个节点指向下一个，最后一个指向第一个。

常用方法：

ring.New(n) 创建长度为 n 的环
r.Value 访问当前节点值
r.Next() 获取下一个节点
r.Link() 连接两个环
r.Unlink() 断开部分节点

示例：遍历环

package main

import (
    "container/ring"
    "fmt"
)

func main() {
    r := ring.New(3)
    for i := 1; i <= 3; i++ {
        r.Value = i
        r = r.Next()
    }

    // 遍历
    r.Do(func(p interface{}) {
        fmt.Print(p, " ") // 输出: 1 2 3
    })
}

也可以用 Link 合并两个环，或用 Unlink 移除连续节点。

基本上就这些。list 适合频繁插入删除，heap 用于优先队列，ring 适合循环调度等场景。不复杂但容易忽略接口定义细节。

本文转载于：互联网如有侵犯，请联系zhengruancom@outlook.com删除。
免责声明：正软商城发布此文仅为传递信息，不代表正软商城认同其观点或证实其描述。

标签：节点链表遍历