使用Golang实现双向环形链表

JimPang · · 1064 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。
**什么是双向环形链表?** `双向环形链表`属于线性表的其中一种结构,也被称为双向循环链表,以下是根据个人的理解使用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 } } ```

有疑问加站长微信联系(非本文作者))

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

1064 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传