单链表

链表是一个个数据节点组成的，它是一个递归结构，要么为空，要么它存在一个指向另外一个数据节点的引用。

简单的链表：

package main

import "fmt"

// 单链表
type LinkNode struct {
	Data     int64
	NextNode *LinkNode
}

func main() {
	node := new(LinkNode)

	node.Data = 1

	node1 := new(LinkNode)
	node1.Data = 2
	node.NextNode = node1

	node2 := new(LinkNode)
	node2.Data = 3
	node1.NextNode = node2

	// print list data
	nowNode := node
	for {
		if nowNode != nil {
			fmt.Println(nowNode.Data)

			nowNode = nowNode.NextNode
			continue
		}
		break
	}

}

打印结果为：

1
2
3

除了单链表我们还需要知道哪些链表呢？

1. 双链表。每个节点既可以找到它之前的节点也可以找到它后面的节点，是双向的。=
2. 循环链表。从一个点开始往下寻找数据，转一圈之后仍可以回到它本身那个节点，形成一个回路。
3. 循环单链表和循环双链表的区别就是，一个只能一个方向走，一个可以两个方向走。

接下来，我们来实现一下循环链表。

循环链表

定义结构:

type Ring struct {
	next, prev *Ring
	Value      interface{}
}

循环链表有三个字段，next 表示后驱节点，prev 表示前驱节点， Value 表示值。

初始化循环链表

// 初始化循环链表
func (r *Ring) init() *Ring {
	r.next = r
	r.prev = r
	return r
}

创建指定大小

// New 创建一个链表
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 为负数的时候，表示向前移动，当 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， 连接一个节点，并且返回之前节点 p 的后驱节点
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
}

也就是说，在节点 r 之后插入一个新的节点 s ，而 r 节点之前的后继节点，将会链接到新节点后面，并且返回之前的第一个后驱节点 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 {
		for p := r.Next(); p != r; p = p.next {
			n++
		}
	}
	return n
}