Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Go 语言标准库 —— container/ring 包（环形链表）

🔹 概述

container/ring 包实现了环形链表（循环链表）的数据结构。

主要功能：

  • 环形链表操作
  • O(1) 时间复杂度的遍历
  • 支持在任意位置插入/删除元素
  • 可以存储任意类型的元素

重要说明：

  • ring 是一个通用的环形链表实现
  • 不是并发安全的
  • 元素类型为 interface{}（可以存储任意类型）
  • 环形结构（尾节点指向头节点）
  • 可以从任意节点开始遍历整个环

环形链表的特性：

  • 循环结构（没有真正的头尾）
  • 可以从任意节点访问所有节点
  • 支持 O(1) 时间复杂度的遍历
  • 适合固定大小的缓冲区
  • 适合轮转调度场景

应用场景：

  • 循环缓冲区
  • 轮转调度（Round Robin）
  • 时间片轮转
  • 固定大小的缓存
  • 音频/视频缓冲

🔹 核心类型

Ring 环形链表类型

ring.Ring struct

  • 说明：

    • 环形链表结构
    • 每个节点都指向下一个节点
    • 最后一个节点指向第一个节点形成环
    • 零值表示长度为 0 的环

  • 字段：

    type Ring struct {
    Value interface{} // 当前节点的值
    next  *Ring       // 下一个节点（内部字段）
    prev  *Ring       // 上一个节点（内部字段）
}

  • 注意：

    • Value 是公开字段，可以直接访问和修改
    • next 和 prev 是内部字段，不应直接访问
    • 零值 ring 可以直接使用，表示空环

🔹 核心函数

创建新环

ring.New(n int) *Ring

  • 说明：

    • 创建包含 n 个节点的环
    • 每个节点的 Value 初始化为 nil
    • 如果 n <= 0，返回 nil

  • 参数：

    • n int - 节点数量

  • 返回值：

    • *Ring - 新创建的环

  • 时间复杂度：O(n)

  • 示例：

    // 创建包含 5 个节点的环
r := ring.New(5)

// 设置每个节点的值
for i := 0; i < 5; i++ {
    r.Value = i
    r = r.Next()
}

🔹 核心方法

获取下一个节点

r.Next() *Ring

  • 说明：

    • 返回当前节点的下一个节点
    • 如果环只有一个节点，返回自身

  • 返回值：

    • *Ring - 下一个节点

  • 时间复杂度：O(1)

  • 示例：

    r := ring.New(3)

// 遍历环
start := r
for i := 0; i < 3; i++ {
    fmt.Println(r.Value)
    r = r.Next()
}

获取上一个节点

r.Prev() *Ring

  • 说明：

    • 返回当前节点的前一个节点
    • 如果环只有一个节点，返回自身

  • 返回值：

    • *Ring - 前一个节点

  • 时间复杂度：O(1)

  • 示例：

    r := ring.New(3)

// 反向遍历
start := r
for i := 0; i < 3; i++ {
    r = r.Prev()
    fmt.Println(r.Value)
}

移动节点

r.Move(n int) *Ring

  • 说明：

    • 从当前节点移动 n 个位置
    • n > 0 向前移动（Next 方向）
    • n < 0 向后移动（Prev 方向）
    • n = 0 返回当前节点

  • 参数：

    • n int - 移动的步数

  • 返回值：

    • *Ring - 移动后的节点

  • 时间复杂度：O(|n|)

  • 示例：

    r := ring.New(10)

// 向前移动 3 步
r = r.Move(3)

// 向后移动 2 步
r = r.Move(-2)

// 回到起点
r = r.Move(0)

删除节点

r.Unlink(n int) *Ring

  • 说明：

    • 从当前节点之后删除 n 个节点
    • 返回被删除的节点组成的新环
    • 原环会缩短

  • 参数：

    • n int - 要删除的节点数量

  • 返回值：

    • *Ring - 被删除的节点组成的环

  • 时间复杂度：O(n)

  • 示例：

    r := ring.New(5)

// 删除 2 个节点
removed := r.Unlink(2)

fmt.Println("原环大小:", r.Len())      // 3
fmt.Println("删除的环大小:", removed.Len()) // 2

连接两个环

r.Link(s *Ring) *Ring

  • 说明：

    • 将环 s 连接到当前节点之后
    • s 的第一个节点成为 r 的下一个节点
    • 返回 s 的最后一个节点
    • 两个环合并为一个环

  • 参数：

    • s *Ring - 要连接的环

  • 返回值：

    • *Ring - s 的最后一个节点

  • 时间复杂度：O(1)

  • 示例：

    r1 := ring.New(3)
r2 := ring.New(2)

// 连接两个环
r1.Link(r2)

fmt.Println("合并后大小:", r1.Len()) // 5

获取环的长度

r.Len() int

  • 说明：

    • 计算环中节点的数量
    • 需要遍历整个环

  • 返回值：

    • int - 节点数量

  • 时间复杂度：O(n)

  • 示例：

    r := ring.New(5)
fmt.Println("环的大小:", r.Len()) // 5

执行函数

r.Do(f func(interface{}))

  • 说明：

    • 对环中每个节点执行函数 f
    • 从当前节点开始遍历

  • 参数：

    • f func(interface{}) - 要执行的函数

  • 时间复杂度：O(n)

  • 示例：

    r := ring.New(3)
r.Value = 1
r.Next().Value = 2
r.Next().Next().Value = 3

// 对每个节点执行函数
r.Do(func(v interface{}) {
    fmt.Println(v)
})
// 输出：1 2 3

🔹 使用场景

1. 循环缓冲区

package main

import (
	"container/ring"
	"fmt"
)

// CircularBuffer 实现循环缓冲区
type CircularBuffer struct {
	buffer *ring.Ring
	size   int
}

func NewCircularBuffer(size int) *CircularBuffer {
	return &CircularBuffer{
		buffer: ring.New(size),
		size:   size,
	}
}

func (cb *CircularBuffer) Write(value interface{}) {
	cb.buffer.Value = value
	cb.buffer = cb.buffer.Next()
}

func (cb *CircularBuffer) Read() interface{} {
	value := cb.buffer.Value
	cb.buffer.Value = nil
	cb.buffer = cb.buffer.Next()
	return value
}

func (cb *CircularBuffer) GetAll() []interface{} {
	values := make([]interface{}, 0, cb.size)
	cb.buffer.Do(func(v interface{}) {
		if v != nil {
			values = append(values, v)
		}
	})
	return values
}

func main() {
	// 创建大小为 5 的循环缓冲区
	buf := NewCircularBuffer(5)

	// 写入数据
	for i := 1; i <= 7; i++ {
		buf.Write(i)
		fmt.Printf("写入：%d\n", i)
	}

	// 读取所有数据
	fmt.Println("缓冲区内容:", buf.GetAll())
	// 输出：[3 4 5 6 7]（最早的 2 个数据被覆盖）
}

2. 轮转调度（Round Robin）

package main

import (
	"container/ring"
	"fmt"
)

// Task 任务
type Task struct {
	ID   int
	Name string
}

// RoundRobin 实现轮转调度
type RoundRobin struct {
	tasks *ring.Ring
}

func NewRoundRobin(numSlots int) *RoundRobin {
	return &RoundRobin{
		tasks: ring.New(numSlots),
	}
}

func (rr *RoundRobin) AddTask(task Task) {
	rr.tasks.Value = task
	rr.tasks = rr.tasks.Next()
}

func (rr *RoundRobin) GetNextTask() *Task {
	task := rr.tasks.Value
	if task == nil {
		return nil
	}
	t := task.(Task)
	rr.tasks.Value = nil // 清除
	rr.tasks = rr.tasks.Next()
	return &t
}

func (rr *RoundRobin) HasTasks() bool {
	has := false
	rr.tasks.Do(func(v interface{}) {
		if v != nil {
			has = true
		}
	})
	return has
}

func main() {
	// 创建轮转调度器（5 个槽位）
	rr := NewRoundRobin(5)

	// 添加任务
	rr.AddTask(Task{ID: 1, Name: "任务 1"})
	rr.AddTask(Task{ID: 2, Name: "任务 2"})
	rr.AddTask(Task{ID: 3, Name: "任务 3"})

	// 轮转执行任务
	for rr.HasTasks() {
		task := rr.GetNextTask()
		if task != nil {
			fmt.Printf("执行：%s\n", task.Name)
		}
	}
}

3. 时间片轮转

package main

import (
	"container/ring"
	"fmt"
	"time"
)

// Process 进程
type Process struct {
	ID        int
	Name      string
	Remaining int // 剩余时间片
}

// TimeSliceScheduler 时间片轮转调度器
type TimeSliceScheduler struct {
	processes *ring.Ring
	quantum   int // 时间片大小
}

func NewScheduler(numSlots, quantum int) *TimeSliceScheduler {
	return &TimeSliceScheduler{
		processes: ring.New(numSlots),
		quantum:   quantum,
	}
}

func (s *TimeSliceScheduler) AddProcess(p Process) {
	s.processes.Value = p
	s.processes = s.processes.Next()
}

func (s *TimeSliceScheduler) Run() {
	start := s.processes

	for {
		// 检查是否还有进程需要执行
		done := true
		s.processes.Do(func(v interface{}) {
			if v != nil && v.(Process).Remaining > 0 {
				done = false
			}
		})
		if done {
			break
		}

		// 执行当前进程
		if p, ok := s.processes.Value.(Process); ok && p.Remaining > 0 {
			execTime := min(s.quantum, p.Remaining)
			p.Remaining -= execTime
			s.processes.Value = p

			fmt.Printf("进程 %s 执行 %d 时间片，剩余 %d\n",
				p.Name, execTime, p.Remaining)

			time.Sleep(100 * time.Millisecond) // 模拟执行
		}

		s.processes = s.processes.Next()

		// 防止死循环
		if s.processes == start {
			start = s.processes
		}
	}
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	// 创建调度器（5 个槽位，时间片 2）
	scheduler := NewScheduler(5, 2)

	// 添加进程
	scheduler.AddProcess(Process{ID: 1, Name: "P1", Remaining: 5})
	scheduler.AddProcess(Process{ID: 2, Name: "P2", Remaining: 3})
	scheduler.AddProcess(Process{ID: 3, Name: "P3", Remaining: 4})

	// 运行调度
	scheduler.Run()
}

4. 固定大小缓存

package main

import (
	"container/ring"
	"fmt"
)

// Cache 实现固定大小的缓存
type Cache struct {
	cache  *ring.Ring
	lookup map[interface{}]*ring.Ring
}

type CacheEntry struct {
	Key   interface{}
	Value interface{}
}

func NewCache(size int) *Cache {
	return &Cache{
		cache:  ring.New(size),
		lookup: make(map[interface{}]*ring.Ring),
	}
}

func (c *Cache) Put(key, value interface{}) {
	// 如果键已存在，更新值
	if r, ok := c.lookup[key]; ok {
		r.Value = CacheEntry{Key: key, Value: value}
		return
	}

	// 否则，覆盖最旧的条目
	entry := CacheEntry{Key: key, Value: value}
	
	// 删除旧的查找记录
	oldEntry := c.cache.Value.(CacheEntry)
	if oldEntry.Key != nil {
		delete(c.lookup, oldEntry.Key)
	}

	// 写入新条目
	c.cache.Value = entry
	c.lookup[key] = c.cache
	c.cache = c.cache.Next()
}

func (c *Cache) Get(key interface{}) (interface{}, bool) {
	if r, ok := c.lookup[key]; ok {
		return r.Value.(CacheEntry).Value, true
	}
	return nil, false
}

func (c *Cache) GetAll() []CacheEntry {
	entries := make([]CacheEntry, 0, c.cache.Len())
	c.cache.Do(func(v interface{}) {
		if entry, ok := v.(CacheEntry); ok && entry.Key != nil {
			entries = append(entries, entry)
		}
	})
	return entries
}

func main() {
	// 创建大小为 3 的缓存
	cache := NewCache(3)

	// 添加数据
	cache.Put("key1", "value1")
	cache.Put("key2", "value2")
	cache.Put("key3", "value3")

	fmt.Println("缓存内容:", cache.GetAll())

	// 添加新数据（淘汰最旧的）
	cache.Put("key4", "value4")

	fmt.Println("淘汰后:", cache.GetAll())

	// 查询
	if val, ok := cache.Get("key2"); ok {
		fmt.Println("key2 =", val)
	}
}

5. 音频/视频缓冲

package main

import (
	"container/ring"
	"fmt"
)

// AudioBuffer 实现音频缓冲区
type AudioBuffer struct {
	buffer *ring.Ring
	sampleRate int
}

type AudioSample struct {
	Left  float32 // 左声道
	Right float32 // 右声道
}

func NewAudioBuffer(size, sampleRate int) *AudioBuffer {
	return &AudioBuffer{
		buffer:     ring.New(size),
		sampleRate: sampleRate,
	}
}

func (ab *AudioBuffer) Write(sample AudioSample) {
	ab.buffer.Value = sample
	ab.buffer = ab.buffer.Next()
}

func (ab *AudioBuffer) Read() AudioSample {
	sample := ab.buffer.Value.(AudioSample)
	ab.buffer.Value = AudioSample{} // 清零
	ab.buffer = ab.buffer.Next()
	return sample
}

func (ab *AudioBuffer) GetLatency() float64 {
	// 延迟 = 缓冲区大小 / 采样率
	return float64(ab.buffer.Len()) / float64(ab.sampleRate) * 1000 // 毫秒
}

func main() {
	// 创建音频缓冲区（1024 个采样，44.1kHz）
	buf := NewAudioBuffer(1024, 44100)

	fmt.Printf("缓冲区延迟：%.2f ms\n", buf.GetLatency())

	// 写入音频数据
	for i := 0; i < 1024; i++ {
		buf.Write(AudioSample{
			Left:  float32(i) / 1024.0,
			Right: float32(1024-i) / 1024.0,
		})
	}

	// 读取音频数据
	sample := buf.Read()
	fmt.Printf("读取采样：L=%.3f, R=%.3f\n", sample.Left, sample.Right)
}

🔹 注意事项和最佳实践

1. 零值 Ring

  • ✅ 零值 ring 可以直接使用
  • ⚠️ 零值 ring 表示空环（长度为 0）
var r ring.Ring
fmt.Println(r.Len()) // 0

2. 类型断言

  • ⚠️ ring 存储的是 interface{} 类型
  • ✅ 取出元素时必须进行类型断言
  • ⚠️ 类型断言可能 panic，建议使用 comma-ok 形式
// 不安全
value := r.Value.(int)

// 安全
if value, ok := r.Value.(int); ok {
	fmt.Println(value)
}

3. 并发安全

  • ⚠️ ring 不是并发安全的
  • ✅ 多线程环境需要加锁
type SafeRing struct {
	mu   sync.RWMutex
	ring *ring.Ring
}

func (sr *SafeRing) Write(v interface{}) {
	sr.mu.Lock()
	defer sr.mu.Unlock()
	sr.ring.Value = v
	sr.ring = sr.ring.Next()
}

4. 内存管理

  • ✅ 及时清理不需要的数据
  • ✅ 读取后可以清零
value := r.Value
r.Value = nil // 清零
r = r.Next()

5. 性能考虑

  • ✅ 遍历：O(n)
  • ✅ 移动：O(|n|)
  • ✅ 连接：O(1)
  • ⚠️ 长度计算：O(n)

🔹 Ring vs List 对比

数据结构对比

特性RingList
结构环形双向链表
头尾无（循环）有（Front/Back）
遍历循环遍历单向/双向遍历
长度计算O(n)O(1)
固定大小✅ 适合❌ 不适合
轮转调度✅ 适合❌ 不适合

选择指南

使用 Ring：

  • ✅ 需要循环遍历
  • ✅ 固定大小的缓冲区
  • ✅ 轮转调度场景
  • ✅ 时间片轮转

使用 List：

  • ✅ 需要头尾操作
  • ✅ 需要频繁插入删除
  • ✅ 实现 LRU 缓存
  • ✅ 动态大小的队列

🔥 总结

核心类型

类型说明
Ring环形链表节点

核心函数

函数说明时间复杂度
ring.New(n)创建 n 个节点的环O(n)

核心方法

方法说明时间复杂度
Next()返回下一个节点O(1)
Prev()返回上一个节点O(1)
Move(n)移动 n 个位置O(|n|)
Unlink(n)删除 n 个节点O(n)
Link(s)连接环 sO(1)
Len()计算长度O(n)
Do(f)执行函数 fO(n)

主要特点

  • 环形结构 👉 没有真正的头尾
  • 循环遍历 👉 可以从任意节点开始
  • 固定大小 👉 适合缓冲区
  • 任意类型 👉 存储 interface{}

使用场景

  • 循环缓冲区 👉 固定大小缓冲
  • 轮转调度 👉 Round Robin 调度
  • 时间片轮转 👉 进程调度
  • 固定缓存 👉 淘汰最旧数据
  • 音频/视频 👉 流媒体缓冲

最佳实践

  • ✅ 使用类型断言时检查类型
  • ✅ 并发环境加锁保护
  • ✅ 及时清理不需要的数据
  • ✅ 根据场景选择合适的数据结构
  • ⚠️ 注意：长度计算需要 O(n)

性能提示

  • 遍历 👉 O(n)
  • 移动 👉 O(|n|)
  • 连接 👉 O(1)
  • 长度计算 👉 O(n)
  • 访问当前节点 👉 O(1)

container/ring 包提供了高效的环形链表实现，适合循环缓冲区、轮转调度等场景！