go语言的循环双链表Ring

go作为类C语言，自己的库里面包括了循环双链表的实现

/*
 * 1. go语言的循环双向链表；
 * 2. 就是每个元素存在两个指针，指向前驱和后继，外加一个链表节点的值Value
 * 3. 这个值采用的是interface{}， 就是类似于C语言中的指针，随便什么类型都行
 * 4. 链表是没有头、也没有尾部的，随便从某个节点都可以遍历
 */
package ring

// A Ring is an element of a circular list, or ring.
// Rings do not have a beginning or end; a pointer to any ring element
// serves as reference to the entire ring. Empty rings are represented
// as nil Ring pointers. The zero value for a Ring is a one-element
// ring with a nil Value.
//
type Ring struct {
	next *Ring		// 后继
	prev *Ring		// 前驱
	Value      interface{} // for use by client; untouched by this library
						   // 链表挂着的节点值，interface{}即任何类型都可以
}

// 初始化，next和prev为本身
func (r *Ring) init() *Ring {
	r.next = r
	r.prev = r
	return r
}

// Next returns the next ring element. r must not be empty.
// 返回下一个元素，如果发现下一个元素指针为空，则返回本身
func (r *Ring) Next() *Ring {
	if r.next == nil {
		return r.init()
	}
	return r.next
}

// Prev returns the previous ring element. r must not be empty.
// 返回上一个元素，如果发现上一个元素指针为空，则返回本身
func (r *Ring) Prev() *Ring {
	if r.next == nil {
		return r.init()
	}
	return r.prev
}

// Move moves n % r.Len() elements backward (n < 0) or forward (n >= 0)
// in the ring and returns that ring element. r must not be empty.
// 当前指针移动n个元素，返回移动后的结果
// 如果这个n的绝对值过大，则实际移动到 n % r.len()元素，但是依然会遍历n次，因为r.len()只能通过遍历知道
func (r *Ring) Move(n int) *Ring {
	// 如果Ring的下一个为nil，则返回本身
	if r.next == nil {
		return r.init()
	}
	switch {
	case n < 0:
		// 如果n为负数，则往prev方向移动，并返回移动的结果
		for ; n < 0; n++ {
			r = r.prev
		}
	case n > 0:
		// 如果n为正数，则往next方向移动
		for ; n > 0; n-- {
			r = r.next
		}
	}
	return r
}

// New creates a ring of n elements.
// 产生n个元素的Ring对象
// n <=0, 则返回nil
func New(n int) *Ring {
	if n <= 0 {
		return nil
	}
	// 产生第一个Ring对象
	r := new(Ring)
	p := r
	// 产生n-1个对象，并赋予值
	for i := 1; i < n; i++ {
		p.next = &Ring{prev: p} // 当前的next指向新的Ring，新Ring的prev为当前的地址
		p = p.next
	}
	
	// 最后一个Ring对象的next指向第一个
	// 第一个的prev指向最后一个
	p.next = r
	r.prev = p
	return r
}

// Link connects ring r with ring s such that r.Next()
// becomes s and returns the original value for r.Next().
// r must not be empty.
//
// If r and s point to the same ring, linking
// them removes the elements between r and s from the ring.
// The removed elements form a subring and the result is a
// reference to that subring (if no elements were removed,
// the result is still the original value for r.Next(),
// and not nil).
//
// If r and s point to different rings, linking
// them creates a single ring with the elements of s inserted
// after r. The result points to the element following the
// last element of s after insertion.
//

/**
 * 连接两个循环链表：
 * r: A0 A1 A2
 * s: B0 B1 B2 B3
 * rs = r.Link(s): A1 A2 A0 [B0 B1 B2 B3]
 *  连接实际上是将s的元素放入r的第一个元素(A0)和第二个元素A1之间，再返回第二个元素A1(rs)为头进行遍历
 * 1）A0 [B0 B1 B2 B3] A1 A2
 * 2) 以A1为头，进行遍历，A1 A2 A0 [B0 B1 B2 B3]
 * 假设s只有一个元素，即[B0]，那么r.Link(s): A1 A2 A0 [B0],在以r为头进行遍历，得出A0 B0 A1 A2,
 */
func (r *Ring) Link(s *Ring) *Ring {
	n := r.Next()
	if s != nil {
		p := s.Prev()
		// Note: Cannot use multiple assignment because
		// evaluation order of LHS is not specified.
		r.next = s
		s.prev = r
		n.prev = p
		p.next = n
	}
	return n
}

// Unlink removes n % r.Len() elements from the ring r, starting
// at r.Next(). If n % r.Len() == 0, r remains unchanged.
// The result is the removed subring. r must not be empty.
//

// 假设r: A0 A1 A2 A3 A4 A5,  n = 3
// r.Move(n+1) 为A4的位置
// 将A0与A4连接，即A0 [A1 A2 A3] A4 A5，[]内的元素被删除掉，即A0 A4 A5
func (r *Ring) Unlink(n int) *Ring {
	if n <= 0 {
		return nil
	}
	return r.Link(r.Move(n + 1))
}

// 获取Ring的长度，其实也就是遍历
func (r *Ring) Len() int {
	n := 0
	if r != nil {
		n = 1
		for p := r.Next(); p != r; p = p.next {
			n++
		}
	}
	return n
}

// 处理循环链表的每个元素，实际上就是一种遍历
// 传入一个Callback即可
// 注意，这里只能做类似读操作，不能进行修改删除节点操作
func (r *Ring) Do(f func(interface{})) {
	if r != nil {
		f(r.Value)
		for p := r.Next(); p != r; p = p.next {
			f(p.Value)
		}
	}
}

简单的测试代码，用来测Link接口

package main
import (
    "fmt"
    "container/ring"
)

func main() {
   
    r := ring.New(3)
    
    var p *ring.Ring
    p = r
    for i := 0; i < r.Len(); i++ {
       p.Value = fmt.Sprintf("%s_%d", "A", i)
       p = p.Next()
    }
    
    s := ring.New(4)
    p = s
    for j := 0; j < s.Len(); j++ {
        p.Value = fmt.Sprintf("%s_%d", "B", j)
        p = p.Next()
    }
    rs :=  r.Link(s)
    p = rs
    for i := 0; i < rs.Len(); i++ {
        fmt.Println(p.Value)
        p = p.Next()
    }

}

当然，也可以参考go语言自己的源码src/container/ring/ring_test.go等文件。