使用Golang实现双向环形链表

JimPang · 2018-08-30 11:10:32 · 1932 次点击 · 预计阅读时间 1 分钟 · 大约8小时之前开始浏览

这是一个创建于 2018-08-30 11:10:32 的文章，其中的信息可能已经有所发展或是发生改变。

什么是双向环形链表？

双向环形链表属于线性表的其中一种结构,也被称为双向循环链表,以下是根据个人的理解使用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
    }
}

实现步骤4：实现对链表的按照id找到节点

//按照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的节点

//删除指定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数据

//根据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:遍历链表

//遍历整个环形链表
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
    }
}

最后来一波测试

//约瑟夫问题
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()
}

以下为完整代码

//双向环形链表数据结构
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
    }
}