ring实现了一个环形链表

go
// Package ring 实现了环形链表的操作。
package ring



// Ring 是环形链表的元素。
// 环形链表没有明确定义的开头或结尾；指向环形链表的任何元素的指针都可视为对整个环形链表的引用。
// 空环形链表表示为 nil Ring 指针。Ring 的零值是一个只包含一个 nil Value 的环。
type Ring struct {
	next, prev *Ring
	Value      any // 由客户端使用；本库不会修改该值
}

// init 方法：初始化环形链表，返回链表的第一个元素。
func (r *Ring) init() *Ring {
	r.next = r
	r.prev = r
	return r
}

// Next 返回下一个环形链表元素。r 不能为空。
func (r *Ring) Next() *Ring {
	if r.next == nil {
		return r.init()
	}
	return r.next
}

// Prev 返回前一个环形链表元素。r 不能为空。
func (r *Ring) Prev() *Ring {
	if r.next == nil {
		return r.init()
	}
	return r.prev
}

// Move 将 n % r.Len() 个元素向前（n < 0）或向后（n >= 0）移动，并返回移动后的环形链表元素。r 不能为空。
func (r *Ring) Move(n int) *Ring {
	if r.next == nil {
		return r.init()
	}
	switch {
	case n < 0:
		for ; n < 0; n++ {
			r = r.prev
		}
	case n > 0:
		for ; n > 0; n-- {
			r = r.next
		}
	}
	return r
}

// New 创建包含 n 个元素的新环形链表。
func New(n int) *Ring {
	if n <= 0 {
		return nil
	}
	r := new(Ring)
	p := r
	for i := 1; i < n; i++ {
		p.next = &Ring{prev: p}
		p = p.next
	}
	p.next = r
	r.prev = p
	return r
}

// Link 连接环形链表 r 和 s，使得 r.Next() 变为 s，并返回 r.Next() 的原始值。
// r 不能为空。
//
// 如果 r 和 s 指向同一个环形链表，则连接它们将从链表中移除 r 和 s 之间的元素。
// 被移除的元素形成一个子环，结果是对该子环的引用（如果没有移除元素，则结果仍为 r.Next() 的原始值，而不是 nil）。
//
// 如果 r 和 s 指向不同的环形链表，则连接它们将创建一个单一的环形链表，其中包含 s 的元素插入到 r 之后。
// 结果指向插入后 s 的最后一个元素的下一个元素。
func (r *Ring) Link(s *Ring) *Ring {
	n := r.Next()
	if s != nil {
		p := s.Prev()
		// 注意：不能使用多重赋值，因为 LHS 的评估顺序未指定。
		r.next = s
		s.prev = r
		n.prev = p
		p.next = n
	}
	return n
}

// Unlink 从环形链表 r 中移除 n % r.Len() 个元素，从 r.Next() 开始。如果 n % r.Len() == 0，则 r 保持不变。
// 返回被移除的子环。r 不能为空。
func (r *Ring) Unlink(n int) *Ring {
	if n <= 0 {
		return nil
	}
	return r.Link(r.Move(n + 1))
}

// Len 计算环形链表 r 中的元素数量。
// 执行时间与元素数量成正比。
func (r *Ring) Len() int {
	n := 0
	if r != nil {
		n = 1
		for p := r.Next(); p != r; p = p.next {
			n++
		}
	}
	return n
}

// Do 对环形链表中的每个元素调用函数 f，按照正向顺序。
// 如果 f 改变 *r，则 Do 的行为未定义。
func (r *Ring) Do(f func(any)) {
	if r != nil {
		f(r.Value)
		for p := r.Next(); p != r; p = p.next {
			f(p.Value)
		}
	}
}

使用示例

go
package main

import (
	"container/ring"
	"fmt"
)

func main() {
	// 创建一个包含 3 个元素的环形链表
	r := ring.New(3)

	// 遍历环形链表并设置元素值
	for i := 1; i <= r.Len(); i++ {
		r.Value = i
		r = r.Next()
	}

	// 遍历环形链表并打印元素值
	r.Do(func(x interface{}) {
		fmt.Print(x, " ")
	})
	fmt.Println()

	// 移动环形链表的元素，使得下一个元素成为新的第一个元素
	r = r.Move(1)

	// Link 连接两个环形链表
	s := ring.New(2)
	s.Value = 4
	r.Link(s)

	// 遍历连接后的环形链表并打印元素值
	r.Do(func(x interface{}) {
		fmt.Print(x, " ")
	})
	fmt.Println()

	// Unlink 移除环形链表中的两个元素
	unlinked := r.Unlink(2)

	// 遍历被移除的子环形链表并打印元素值
	unlinked.Do(func(x interface{}) {
		fmt.Print(x, " ")
	})
	fmt.Println()
}