version: 1.10

package ring

import "container/ring"

概述

ring 包实现了循环链表的操作。

索引

例子

文件

ring.go

type Ring 

  1. type Ring struct {
  2.     Value interface{} // 被用户使用，本库不会接触
  3.     // 包含被过滤的或未导出的字段
  4. }

Ring 是一个循环链表。循环链表没有开始和结束，通过循环链表中的任意一个元素的指针都能引用整个链表。使用值为 nil 的 Ring 指针来表示空循环链表。零值循环链表是指链表只有一个值为 nil 的元素。

func New 

  1. func New(n int) *Ring

New 函数创建一个元素个数为 n 的循环链表。

func (*Ring) Do 

  1. func (r *Ring) Do(f func(interface{}))

Do 方法对循环链表的每个元素都调用函数 f 。如果函数 f 改变了循环链表，Do 方法的结果将无法预测。

例子:

  1. // 创建一个大小为5的循环链表
  2. r := ring.New(5)
  4. // Get the length of the ring
  5. // 获得循环链表的长度
  7. // 用若干整数来初始化循环链表
  8. for i := 0; i < n; i++ {
  9.     r.Value = i
  10.     r = r.Next()
  11. }
  13. // 迭代循环链表并打印内容
  14. r.Do(func(p interface{}) {
  15.     fmt.Println(p.(int))
  16. })
  18. // Output:
  19. // 0
  20. // 1
  21. // 2
  22. // 3
  23. // 4

func (*Ring) Len 

  1. func (r *Ring) Len() int

Len 方法计算循环链表 r 的元素个数。函数的执行时间与元素个数成正比。

Example:

  1. // 创建一个大小为4的循环链表
  2. r := ring.New(4)
  4. // 打印循环链表的长度
  5. fmt.Println(r.Len())
  7. // Output:
  8. // 4

  1. func (r *Ring) Link(s *Ring) *Ring

Link 方法连接循环链表 r 和 s ，所以 r.Next() 会将变成 s ，并且函数返回 r.Next() 的原来的值。参数 r 一定不能是空。

如果 r 和 s 指向同一个循环链表，连接它们会移除循环链表里 r 和 s 之间的元素。被移除的元素形成了一个子循环链表，函数返回的是对这个子循环链表的引用（如果没有元素被移除，返回结果是原来的 r.Next() 的值，而不是 nil）。

如果 r 和 s 指向不同的循环链表，连接它们将把 s 中的元素插入到 r 中，合成一个循环链表。函数返回的结果指向插入后的 s 的最后一个元素的下一个元素。

例子:

  1. // 创建两个循环链表， r 和 s，长度都是2
  2. r := ring.New(2)
  3. s := ring.New(2)
  5. // 获得循环链表的长度
  6. lr := r.Len()
  7. ls := s.Len()
  9. // 初始化 r 中元素的值为0
  10. for i := 0; i < lr; i++ {
  11.     r.Value = 0
  12.     r = r.Next()
  13. }
  15. // 初始化 s 中元素的值为1
  16. for j := 0; j < ls; j++ {
  17.     s.Value = 1
  18.     s = s.Next()
  19. }
  21. // 连接 r 和 s
  22. rs := r.Link(s)
  24. // 迭代组合后的循环链表并打印内容
  25. rs.Do(func(p interface{}) {
  26.     fmt.Println(p.(int))
  27. })
  29. // Output:
  30. // 0
  31. // 0
  32. // 1
  33. // 1

func (*Ring) Move 

  1. func (r *Ring) Move(n int) *Ring

Move 方法把循环链表中的 n % r.Len() 个元素向后（n < 0）或向前（n >= 0）移动，函数返回这个循环链表。r 一定不能是空。

例子:

  1. // 创建一个大小为5的循环链表
  2. r := ring.New(5)
  4. // 获得循环链表的长度
  5. n := r.Len()
  7. // 用若干整数初始化循环链表
  8. for i := 0; i < n; i++ {
  9.     r.Value = i
  10.     r = r.Next()
  11. }
  13. // 把循环链表向前移动3步
  14. r = r.Move(3)
  16. // 迭代循环链表并打印内容
  17. r.Do(func(p interface{}) {
  18.     fmt.Println(p.(int))
  19. })
  21. // Output:
  22. // 3
  23. // 4
  24. // 0
  25. // 1
  26. // 2

func (*Ring) Next 

  1. func (r *Ring) Next() *Ring

Next 方法返回循环链表中的下一个元素。r 一定不能是空。

例子:

  1. // 创建一个大小为5的循环链表
  2. r := ring.New(5)
  4. // 获得循环链表的长度
  5. n := r.Len()
  7. // 用若干整数初始化循环链表
  8. for i := 0; i < n; i++ {
  9.     r.Value = i
  10.     r = r.Next()
  11. }
  13. // 迭代循环链表并打印内容
  14. for j := 0; j < n; j++ {
  15.     fmt.Println(r.Value)
  16.     r = r.Next()
  17. }
  19. // Output:
  20. // 0
  21. // 1
  22. // 2
  23. // 3
  24. // 4

func (*Ring) Prev 

  1. func (r *Ring) Prev() *Ring

Prev 方法返回循环链表中的前一个元素。r 一定不能是空。

Example:

  1. // 创建一个大小为5的循环链表
  2. r := ring.New(5)
  4. // 获得循环链表的长度
  5. n := r.Len()
  7. // 用若干整数初始化循环链表
  8. for i := 0; i < n; i++ {
  9.     r.Value = i
  10.     r = r.Next()
  11. }
  13. // 迭代循环链表并打印内容
  14. for j := 0; j < n; j++ {
  15.     r = r.Prev()
  16.     fmt.Println(r.Value)
  17. }
  19. // Output:
  20. // 4
  21. // 3
  22. // 2
  23. // 1
  24. // 0

  1. func (r *Ring) Unlink(n int) *Ring

Unlink 方法以 r.Next() 为起点，从循环链表 r 中移除 n % r.Len() 个元素。如果 n % r.Len() 等于0， r 保持不变。函数返回被移除的子循环链表。r 一定不是是空。

Example:

  1. // 创建一个大小为6的循环链表
  2. r := ring.New(6)
  4. // 获得循环链表的长度
  5. n := r.Len()
  7. // 用若干整数初始化循环链表
  8. for i := 0; i < n; i++ {
  9.     r.Value = i
  10.     r = r.Next()
  11. }
  13. // 从 r.Next() 开始，Unlink 3个元素
  14. r.Unlink(3)
  16. // 迭代循环链表的剩余部分并打印内容
  17. r.Do(func(p interface{}) {
  18.     fmt.Println(p.(int))
  19. })
  21. // Output:
  22. // 0
  23. // 4
  24. // 5