**什么是双向环形链表？**
`双向环形链表`属于线性表的其中一种结构,也被称为双向循环链表,以下是根据个人的理解使用Golang编写的一个`环形双向链表`,通过这种数据结构能够能够实现大量数据记录在内存中的CURD而不需要通过数据库。双向环形链表也可以解决约瑟夫问题（但一般选用单向环形链表解决）
**实现步骤1：定义双向链表结构体**
```go
//双向环形链表数据结构
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:实现链表一些基本的判断和末尾元素获取的相关方法**
```go
//重置头元素
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：实现对链表的添加操作**
```go
//从头节点按顺序插入双向链表节点
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
}
}
```
**实现步骤4：实现对链表的按照id找到节点**
```go
//按照id找到节点
func (head *CircleLink) FindNodeById( id int ) (*CircleLink,bool){
if head.IsHeadEmpty() && head.Id == id {
return head,true
}else if head.IsHeadEmpty() && head.Id != id{
return &CircleLink{},false
}
//头部非空则遍历查找
currentNode := head
flag := false
for{
if currentNode.Id == id{
flag = true
break
}
if currentNode == head.prev{ //找到最后，表示不存在
break
}
currentNode = currentNode.next
}
if !flag{
return &CircleLink{},false
}
return currentNode,true
}
```
**实现步骤4：实现对链表删除指定id的节点**
```go
//删除指定id的节点
func (head *CircleLink) DeleteNodeById( id int ) bool {
if head.IsEmptyLink(){
fmt.Println("无法删除空链表")
return false;
}
node,boolean := head.FindNodeById(id)
if boolean{
//表示删除的头部元素
if node == head {
//处理只有一个头部元素的情况,则把头元素进行id初始化设置并把Data设置为nil
if head.IsHeadEmpty(){
head.prev = nil
head.next = nil
head.Data = nil
head.Id = 0
return true
}
//如果只有头节点和末尾节点两个元素
if head.next.next == head{
nextNode := head.next
head.Id = nextNode.Id
head.Data = nextNode.Data
head.prev = nil
head.next = nil
return true
}
//如果大于2个节点则移动下一个节点作为头节点
nextNodeTmp := head.next
head.Data = nextNodeTmp.Data
head.Id = nextNodeTmp.Id
head.next = nextNodeTmp.next
nextNodeTmp.next.prev = head
return true
}
//删除的元素是末尾元素
if node == head.GetLastNode(){
//如果只有两个元素
//fmt.Println("最后节点:",node.Id,node.Data,node.next.Data,node.prev.Data)
if node.prev == head && node.next == head {
//如果只有两个元素直接在head节点中断开连接
head.prev = nil
head.next = nil
return true
}
head.prev = node.prev
node.prev.next = head
return true
}
//删除的元素并非头节点也并非末尾节点
node.prev.next = node.next
node.next.prev = node.prev
return true
}else{
fmt.Println("找不到要删除的节点")
}
return boolean
}
```
**实现步骤5:根据id修改相关data数据**
```go
//根据id修改相关data数据
func (head *CircleLink) ModifyById(id int,data interface{}) bool {
node,boolean := head.FindNodeById(id)
if boolean {
node.Data = data
}else{
fmt.Println("找不到要修改的id")
}
return boolean
}
```
**实现步骤6:遍历链表**
```go
//遍历整个环形链表
func (head *CircleLink) FetchAll(){
if head.IsEmptyLink(){
fmt.Println("无法遍历空链表")
return;
}
if head.IsHeadEmpty(){
//fmt.Println(head.Id,head.Data)
fmt.Println( "[", head.Id, head.Data , "next:",head.next, " perv:", head.prev, "]" )
return
}
currentNode := head
for{
fmt.Println( "[", currentNode.Id, currentNode.Data , "next:",currentNode.next.Data, " perv:", currentNode.prev.Data, "]" )
if currentNode == head.prev{
break
}
currentNode = currentNode.next
}
}
```
**最后来一波测试**
```go
//约瑟夫问题
package main
import (
"Josephus/instance"
"Josephus/pkg"
)
func main(){
linkNode := pkg.InitHeadNode( instance.NewPerson("张三") )
node3 := &pkg.CircleLink{
Id:3,
Data:instance.NewPerson("李四"),
}
node2 := &pkg.CircleLink{
Id:2,
Data:instance.NewPerson("王五"),
}
node5 := &pkg.CircleLink{
Id:5,
Data:instance.NewPerson("赵六"),
}
node4 := &pkg.CircleLink{
Id:4,
Data:instance.NewPerson("刘七"),
}
linkNode.AddNode(node3)
linkNode.AddNode(node2)
linkNode.AddNode(node5)
linkNode.AddNode(node4)
linkNode.DeleteNodeById(4)
linkNode.FetchAll()
updateData := instance.NewPerson("包青天")
linkNode.ModifyById(3,updateData)
linkNode.FetchAll()
}
```
**以下为完整代码**
```go
//双向环形链表数据结构
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,
}
}
//重置头元素
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
}
//从头节点按顺序插入双向链表节点
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
}
}
//按照id找到节点
func (head *CircleLink) FindNodeById( id int ) (*CircleLink,bool){
if head.IsHeadEmpty() && head.Id == id {
return head,true
}else if head.IsHeadEmpty() && head.Id != id{
return &CircleLink{},false
}
//头部非空则遍历查找
currentNode := head
flag := false
for{
if currentNode.Id == id{
flag = true
break
}
if currentNode == head.prev{ //找到最后，表示不存在
break
}
currentNode = currentNode.next
}
if !flag{
return &CircleLink{},false
}
return currentNode,true
}
//删除指定id的节点
func (head *CircleLink) DeleteNodeById( id int ) bool {
if head.IsEmptyLink(){
fmt.Println("无法删除空链表")
return false;
}
node,boolean := head.FindNodeById(id)
if boolean{
//表示删除的头部元素
if node == head {
//处理只有一个头部元素的情况,则把头元素进行id初始化设置并把Data设置为nil
if head.IsHeadEmpty(){
head.prev = nil
head.next = nil
head.Data = nil
head.Id = 0
return true
}
//如果只有头节点和末尾节点两个元素
if head.next.next == head{
nextNode := head.next
head.Id = nextNode.Id
head.Data = nextNode.Data
head.prev = nil
head.next = nil
return true
}
//如果大于2个节点则移动下一个节点作为头节点
nextNodeTmp := head.next
head.Data = nextNodeTmp.Data
head.Id = nextNodeTmp.Id
head.next = nextNodeTmp.next
nextNodeTmp.next.prev = head
return true
}
//删除的元素是末尾元素
if node == head.GetLastNode(){
//如果只有两个元素
//fmt.Println("最后节点:",node.Id,node.Data,node.next.Data,node.prev.Data)
if node.prev == head && node.next == head {
//如果只有两个元素直接在head节点中断开连接
head.prev = nil
head.next = nil
return true
}
head.prev = node.prev
node.prev.next = head
return true
}
//删除的元素并非头节点也并非末尾节点
node.prev.next = node.next
node.next.prev = node.prev
return true
}else{
fmt.Println("找不到要删除的节点")
}
return boolean
}
//根据id修改相关data数据
func (head *CircleLink) ModifyById(id int,data interface{}) bool {
node,boolean := head.FindNodeById(id)
if boolean {
node.Data = data
}else{
fmt.Println("找不到要修改的id")
}
return boolean
}
//遍历整个环形链表
func (head *CircleLink) FetchAll(){
if head.IsEmptyLink(){
fmt.Println("无法遍历空链表")
return;
}
if head.IsHeadEmpty(){
//fmt.Println(head.Id,head.Data)
fmt.Println( "[", head.Id, head.Data , "next:",head.next, " perv:", head.prev, "]" )
return
}
currentNode := head
for{
fmt.Println( "[", currentNode.Id, currentNode.Data , "next:",currentNode.next.Data, " perv:", currentNode.prev.Data, "]" )
if currentNode == head.prev{
break
}
currentNode = currentNode.next
}
}
```
有疑问加站长微信联系（非本文作者））
