Golang循环链表

// 循环链表
type Ring struct {
	prev  *Ring       // 前驱节点
	next  *Ring       // 后驱节点
	Value interface{} // 数据
}

// 初始化空的循环链表，前驱和后驱都指向自己，因为是循环的
func (r *Ring) Init() *Ring {
	r.next = r
	r.prev = r
	return r
}

// 创建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
}

// 获取下一个节点
func (r *Ring) Next() *Ring {
	if r.next == nil {
		return r.Init()
	}
	return r.next
}

// 获取上一个节点
func (r *Ring) Prev() *Ring {
	if r.prev == nil {
		return r.Init()
	}
	return r.prev
}

// 获取第N个节点
// 因为链表是循环的，当 n 为负数，表示从前面往前遍历，否则往后面遍历：
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
}

// 往节点A，链接一个节点，并且返回之前节点A的后驱节点
// 每次链接的是一个新节点，那么链会越来越长，仍然是一个环。
// 因为只是更改链接位置，时间复杂度为：O(1)。
func (r *Ring) Link(s *Ring) *Ring {
	n := r.Next()
	if s != nil {
		p := s.Prev()
		r.next = s
		s.prev = r
		n.prev = p
		p.next = n
	}
	return n
}

// 删除节点后面的 n 个节点
func (r *Ring) Unlink(n int) *Ring {
	if n < 0 {
		return nil
	}
	return r.Link(r.Move(n + 1))
}

// 查看循环链表长度
func (r *Ring) Len() int {
	n := 0
	if r != nil {
		n = 1
		for p := r.Next(); p != r; p = p.next {
			n++
		}
	}
	return n
}