使用Golang实现双向环形链表

什么是双向环形链表？

双向环形链表 属于线性表的其中一种结构,也被称为双向循环链表,以下是根据个人的理解使用Golang编写的一个 环形双向链表 ,通过这种数据结构能够能够实现大量数据记录在内存中的CURD而不需要通过数据库。双向环形链表也可以解决约瑟夫问题（但一般选用单向环形链表解决）

实现步骤1：定义双向链表结构体

//双向环形链表数据结构
package pkg
import (
	"fmt"
)
//双向环形链表结构体
type CircleLink struct {
	Id int  //节点索引
	Data interface{} //data域，用于维护数据
	prev *CircleLink //prev域
	next *CircleLink //next域	
}
//初始化头节点元素,头节点的id初始化为1,获取到的结构体实例就作为头节点存在
func InitHeadNode(data interface{}) *CircleLink{
	return &CircleLink{
		Id:1,
		Data:data,
	}
}

实现步骤2:实现链表一些基本的判断和末尾元素获取的相关方法

//重置头元素
func (head *CircleLink) ResetHeadNode(data interface{}){
	if head.Id == 0 {
		head.Id = 1
	}
	head.Data = data
}
//判断当前头部是否为空
func  (head *CircleLink) IsHeadEmpty() bool{
	return head.next == nil && head.prev == nil
}
//判断当前是否为空链表
func (head *CircleLink) IsEmptyLink() bool {
	return head.Data == nil && head.next == nil && head.prev==nil && head.Id == 0
}

//或者末尾元素
func (head *CircleLink) GetLastNode()  *CircleLink{
	//如果只有一个头元素则直接返回
	currentNode := head
	if !head.IsHeadEmpty() {
		//如果不为空，则遍历到最后一个元素
		for{
			if currentNode.next == head { //表示找到了末尾
				break
			}
			currentNode = currentNode.next //让当前节点前进
		}
	}
	return currentNode
}

实现步骤3：实现对链表的添加操作

//从头节点按顺序插入双向链表节点
func (head *CircleLink) AddNode(newNode *CircleLink){
	//如果只有一个元素则初始化next和prev指针形成双向环形链表
	if head.IsHeadEmpty() {
		//头节点则让next指针指向newNode
		head.next = newNode
		//头节点则让prev指向nil
		head.prev = newNode
		//让newNode的prev和next指针都指向head
		newNode.prev = head
		newNode.next = head 
		return;
	}
	//如果环形已经形成则按照顺序添加节点,把当前节点指向头部
	currentNode := head
	//表示是否应该进行中间插入
	flag := false //默认表示添加都最后
	for{
		
		if currentNode == head.prev {
			//已经是最后一个元素则表示添加都末尾
			break
		}else if currentNode.next.Id > newNode.Id {
			//fmt.Println("如果当前节点的next大于newNode.id则找到了添加的位置")
			//如果当前节点的next大于newNode.id则找到了添加的位置
			flag = true
			break
		}else if currentNode.next.Id == newNode.Id {
			fmt.Println("error:id already exists")
			return
		}
		//当前节点继续前进
		currentNode = currentNode.next 
	}
	if flag {
		//如果在中间添加
		newNode.next = currentNode.next 
		newNode.prev = currentNode
		currentNode.next.prev = newNode
		currentNode.next = newNode
	}else{
		//在末尾添加
		newNode.prev = currentNode
		newNode.next = currentNode.next 
		currentNode.next = newNode
		head.prev = newNode
	}
}