链表是一种很常用到的数据结构，那么这次就环形链表来聊一聊对它的操作。
首先声明环形链表的结构体：结构体内有三个成员变量：分别是两个指向自身类型的前后指针，还有一个value用来存放数据。当然，实际应用中的链表会比这个要复杂，这里只是作为操作演示用～
type Ring struct {
next, pre *Ring
Value interface{}
}
有了结构体以后，我们就可以开始初始化环形链表了。
这里需要注意的是：环形链表第一个节点的前后指针都是指向自己
// InitRing 函数初始化一个环形链表
// 环形链表的首尾指针都是指向自己
func InitRing() (r *Ring) {
r = new(Ring)
r.next, r.pre = r, r
return r
}
//初始化一个环形链表
ring := InitRing() (r *Ring)
在初始化好第一个节点后，就可以拿来使用啦，因为目前ring只有一个节点，我们需要更多的节点来实现对环形链表更多的操作。
所以，我写了一个在ring后添加 N 个节点的函数：NewRing()，代码如下：
// NewRing 创建 N 个节点的环形链表
func (r *Ring) NewRing(n int) error {
if n <= 0 {
return fmt.Errorf("所需添加节点值小于0")
}
p := r
for i := 0; i < n; i++ {
p.next = &Ring{pre: p, Value: i}
p = p.next
}
p.next, r.pre = r, p
return fmt.Errorf("添加%d个节点成功~", n)
}
// 向Ring中新增五个节点
fmt.Println(ring.NewRing(5))
//输出：- 添加5个节点成功~
// 注意⚠️：我这里写的是默认往后添加节点值，
// 因此 只需将新的节点值的pre指针指向r就好了
// p在这里是一个临时的控制变量，在for循环中，每次都将p指向p的下一个节点，也就是新添加的节点！
按照以上的示例来看，我们得到了一个长度为6的环形链表算上init的首个节点！
在每次对节点做完操作后，都需要打印验证一下对环形链表是否操作成功了。
那现在就需要写一个工具来验证一下，这五个值是否添加成功了呢？
一个遍历打印环形链表的函数TravelRing()
// TravelRing 遍历环形链表
func (r *Ring) TravelRing() error {
t := r.next
n := 0
if r == nil {
return NilRing
}
for {
fmt.Printf("\t第%d个值为: %d\n", n, t.Value)
if t.next == r {
return TravelDone
}
n++
t = t.next
}
}
// 打印测试是否添加成功
if err := ring.TravelRing(); err != nil {
fmt.Println(err)
}
//输出
// 第0个值为: 0
// 第1个值为: 1
// 第2个值为: 2
// 第3个值为: 3
// 第4个值为: 4
有了打印环形链表节点值的函数，那也很容易写一个统计环形链表长度的函数CountRing()
// CountRing 获取环形链表的长度
func (r *Ring) CountRing() error {
t := r
count := 0
if r == nil {
return NilRing
}
for {
if t.next != nil {
count++
}
if t.next == r {
fmt.Printf("环形链表长度为: %d\n", count)
return TravelDone
}
t = t.next
}
}
//统计环形链表的长度
ring.CountRing()
//输出：
//环形链表长度为: 6
为了满足对环形链表的基本操作，此外我还写了两个函数，分别是AppendNode()和DeleteNode()
这两个函数是基于某个节点中存储的值来操作的。
AppendNode()函数：首先遍历环形链表中的每一个元素，对比是否有需要插入位置的匹配值。如果有则插入，如果没有则返回。
// AppendNode 在循环链表中某个值位置后插入新数据
func (r *Ring) AppendNode(ins, pos int) error {
t := r
if r == nil {
return NilRing
}
for {
if t.Value == pos {
temp := t.next
t.next = &Ring{
pre: t,
Value: ins,
next: temp,
}
return AppendSuccess
}
if t.next == r {
return AppendFalse
}
t = t.next
}
}
// 尝试在环形链表值 “1” 后加入一个新的节点,值为100
if err := ring.AppendNode(99, 1); err != nil {
fmt.Println(err)
}
// 尝试在环形链表值 “3” 后加入一个新的节点,值为123
if err := ring.AppendNode(123, 3); err != nil {
fmt.Println(err)
}
// 打印测试是否添加成功
if err := ring.TravelRing(); err != nil {
fmt.Println(err)
}
//输出
//插入成功~
//插入成功~
// 第0个值为: 0
// 第1个值为: 1
// 第2个值为: 99
// 第3个值为: 2
// 第4个值为: 3
// 第5个值为: 123
// 第6个值为: 4
//循环完毕~
根据以上输出信息，可以看出，两个节点插入成功了。
DeleteNode() 这个函数就是删除包含某个值的节点
// DeleteNode 删除包含某个值的节点
func (r *Ring) DeleteNode(del int) error {
t := r
if r == nil {
return NilRing
}
for {
if t.Value == del {
t.pre.next = t.next
return DeleteSuccess
}
if t.next == r {
return DeleteFalse
}
t = t.next
}
}
/*=====================测试删除环形链表中某个值=====================*/
if err := ring.DeleteNode(99); err != nil {
fmt.Println(err)
}
if err := ring.DeleteNode(123); err != nil {
fmt.Println(err)
}
if err := ring.TravelRing(); err != nil {
fmt.Println(err)
}
//输出：
//删除节点成功~
//删除节点成功~
// 第0个值为: 0
// 第1个值为: 1
// 第2个值为: 2
// 第3个值为: 3
// 第4个值为: 4
//循环完毕~
由输出可以看出，删除链表中的某个节点的操作也是成功完成了
以上就是我对环形链表的实现以及一些简单的操作，本人才疏学浅，不乏考虑不周的地方，所以贴出来供大家学习交流，如有错误或改进还请批评指正。
代码集合：
package main
import (
"fmt"
)
var (
// TravelDone 遍历链表结束时,返回此提示
TravelDone = fmt.Errorf("循环完毕~")
// NilRing 当环形链表为空时,返回此错误
NilRing = fmt.Errorf("环形链表为空!")
// AppendSuccess 在环形链表某个值后插入成功
AppendSuccess = fmt.Errorf("插入成功~")
// AppendFalse 插入失败,环形链表中查无插入特定位置值
AppendFalse = fmt.Errorf("环形链表中没有该值!")
// DeleteSuccess 在环形链表中删除某值的节点成功
DeleteSuccess = fmt.Errorf("删除节点成功~")
// DeleteFalse 在环形链表中没找到该值
DeleteFalse = fmt.Errorf("环形链表中没有找到该节点,删除失败!")
)
// Ring 环形（循环）链表结构体声明
type Ring struct {
next, pre *Ring
Value interface{}
}
// InitRing 函数初始化一个环形链表
// 环形链表的首尾指针都是指向自己
func InitRing() (r *Ring) {
r = new(Ring)
r.next, r.pre = r, r
return r
}
// NewRing 创建 N 个节点的环形链表
func (r *Ring) NewRing(n int) error {
if n <= 0 {
return fmt.Errorf("所需添加节点值小于0")
}
p := r
for i := 0; i < n; i++ {
p.next = &Ring{pre: p, Value: i}
p = p.next
}
p.next, r.pre = r, p
return fmt.Errorf("添加%d个节点成功~", n)
}
// AppendNode 在循环链表中某个值位置后插入新数据
func (r *Ring) AppendNode(ins, pos int) error {
t := r
if r == nil {
return NilRing
}
for {
if t.Value == pos {
temp := t.next
t.next = &Ring{
pre: t,
Value: ins,
next: temp,
}
return AppendSuccess
}
if t.next == r {
return AppendFalse
}
t = t.next
}
}
// DeleteNode 删除包含某个值的节点
func (r *Ring) DeleteNode(del int) error {
t := r
if r == nil {
return NilRing
}
for {
if t.Value == del {
t.pre.next = t.next
return DeleteSuccess
}
if t.next == r {
return DeleteFalse
}
t = t.next
}
}
// CountRing 获取环形链表的长度
func (r *Ring) CountRing() error {
t := r
count := 0
if r == nil {
return NilRing
}
for {
if t.next != nil {
count++
}
if t.next == r {
fmt.Printf("环形链表长度为: %d\n", count)
return TravelDone
}
t = t.next
}
}
// TravelRing 遍历环形链表
func (r *Ring) TravelRing() error {
t := r.next
n := 0
if r == nil {
return NilRing
}
for {
fmt.Printf("\t第%d个值为: %d\n", n, t.Value)
if t.next == r {
return TravelDone
}
n++
t = t.next
}
}
func main() {
/*======================初始化一个环形链表========================*/
// 初始化一个环形链表Ring实例
ring := InitRing()
// 向Ring中新增五个节点
fmt.Println(ring.NewRing(5))
// 打印测试是否添加成功
if err := ring.TravelRing(); err != nil {
fmt.Println(err)
}
/*===================测试向环形链表中某个位置插入值===================*/
// 尝试在环形链表值 “1” 后加入一个新的节点,值为100
if err := ring.AppendNode(99, 1); err != nil {
fmt.Println(err)
}
// 尝试在环形链表值 “3” 后加入一个新的节点,值为123
if err := ring.AppendNode(123, 3); err != nil {
fmt.Println(err)
}
// 打印测试是否添加成功
if err := ring.TravelRing(); err != nil {
fmt.Println(err)
}
/*=====================测试删除环形链表中某个值=====================*/
if err := ring.DeleteNode(99); err != nil {
fmt.Println(err)
}
if err := ring.DeleteNode(123); err != nil {
fmt.Println(err)
}
if err := ring.TravelRing(); err != nil {
fmt.Println(err)
}
/*========================获取环形链表长度========================*/
ring.CountRing()
}
