数据结构——Golang实现双向链表

栏目: Go · 发布时间: 5年前

内容简介:转载请注明出处:双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。结构如下图:

转载请注明出处: 数据结构——Golang实现双向链表

数据结构——Golang实现双向链表

Golang

1. 双向链表

双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。

结构如下图:

数据结构——Golang实现双向链表

image.png

2. Golang 实现

2.1. 相关结构体

首先需要先定义一下链表相关的结构,DoubleObject用于每个节点的数据,为interface{}结构,DoubleNode为链表中的节点,DoubleList双链表,为了多协程读写安全,所以在链表中加了读写锁。

具体定义如下:

// 节点数据
type DoubleObject interface{}

// 双链表节点
type DoubleNode struct {
    Data DoubleObject
    Prev *DoubleNode
    Next *DoubleNode
}

// 双链表
type DoubleList struct{
    mutex *sync.RWMutex
    Size uint
    Head *DoubleNode
    Tail *DoubleNode
}

2.2. 链表初始化

定义完结构,接下来就需要对双链表进行初始化了。代码如下:

// 双链表初始化
func (list *DoubleList)Init()  {
    list.mutex = new(sync.RWMutex)
    list.Size = 0
    list.Head = nil
    list.Tail = nil
}

2.3. 查询节点

根据指定的位置索引,查询出节点内容。

// Get 获取指定位置的节点
func (list *DoubleList)Get(index uint) *DoubleNode {
    if list.Size == 0 || index > list.Size - 1 {
        return nil
    }
    if index == 0{
        return list.Head
    }
    node := list.Head
    var i uint
    for i = 1; i <= index; i ++{
        node = node.Next
    }
    return node
}

2.4. 新增节点

链表节点的新增分为两种,一种是在链表后面追加节点,该方式,我们称为append;另外一种方式是在指定位置插入节点,我们叫做insert。

// Append 向双链表后面追加节点
func (list *DoubleList)Append(node *DoubleNode) bool {
    if node == nil{
        return false
    }
    list.mutex.Lock()
    defer list.mutex.Unlock()
    if list.Size == 0 {
        list.Head = node
        list.Tail = node
        node.Next = nil
        node.Prev = nil
    } else {
        node.Prev = list.Tail
        node.Next = nil
        list.Tail.Next = node
        list.Tail = node
    }
    list.Size++
    return true
}

// Insert 向双链表指定位置插入节点
func (list *DoubleList)Insert(index uint, node *DoubleNode) bool {
    if index > list.Size || node == nil{
        return false
    }

    if index == list.Size{
        return list.Append(node)
    }

    list.mutex.Lock()
    defer list.mutex.Unlock()
    if index == 0{
        node.Next = list.Head
        list.Head = node
        list.Head.Prev = nil
        list.Size++
        return true
    }
    
    nextNode := list.Get(index)
    node.Prev = nextNode.Prev
    node.Next = nextNode
    nextNode.Prev.Next = node
    nextNode.Prev = node
    list.Size++
    return true
}

2.5. 删除节点

有了新增功能自然就少不了删除,此外,删除节点时,如果指定的位置是链表的头部或尾部,都需要特殊处理下。看代码:

// Delete 删除指定位置的节点
func (list *DoubleList) Delete (index uint) bool {
    if index > list.Size - 1 {
        return false
    }

    list.mutex.Lock()
    defer list.mutex.Unlock()
    if index == 0 {
        if list.Size == 1{
            list.Head = nil
            list.Tail = nil
        } else {
            list.Head.Next.Prev = nil
            list.Head = list.Head.Next
        }
        list.Size--
        return true
    }
    if index == list.Size - 1{
        list.Tail.Prev.Next = nil
        list.Tail = list.Tail.Prev
        list.Size--
        return true
    }

    node := list.Get(index)
    node.Prev.Next = node.Next
    node.Next.Prev = node.Prev
    list.Size--
    return true
}

2.6. 打印链表

最后,我们增加一个打印链表的功能,方便我们看整个链表的内容,这里增加了两种打印方法,一个是从头到尾打印,另一个是从尾到头打印:

// Display 打印双链表信息
func (list *DoubleList)Display(){
    if list == nil || list.Size == 0 {
        fmt.Println("this double list is nil or empty")
        return
    }
    list.mutex.RLock()
    defer list.mutex.RUnlock()
    fmt.Printf("this double list size is %d \n", list.Size)
    ptr := list.Head
    for ptr != nil {
        fmt.Printf("data is %v\n", ptr.Data)
        ptr = ptr.Next
    }
}

// Reverse 倒序打印双链表信息
func (list *DoubleList)Reverse(){
    if list == nil || list.Size == 0 {
        fmt.Println("this double list is nil or empty")
        return
    }
    list.mutex.RLock()
    defer list.mutex.RUnlock()
    fmt.Printf("this double list size is %d \n", list.Size)
    ptr := list.Tail
    for ptr != nil {
        fmt.Printf("data is %v\n", ptr.Data)
        ptr = ptr.Prev
    }
}

3. 源码

github源码

转载请注明出处: 数据结构——Golang实现双向链表


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

迷茫的旅行商

迷茫的旅行商

[美] William J. Cook / 隋春宁 / 人民邮电出版社 / 2013-10-1 / 49.00

假设一名旅行商打算拜访一张城市列表中的所有城市,每座城市只去一次,最后回到出发地。要怎么走才能让路线最短呢?这就是旅行商问题,乍一听很简单,在应用数学界却是一道研究极其热烈的难题,时至今日仍无人能解。本书中,William J. Cook将带领读者踏上一场数学之旅,跟随旅行商的脚步,从19世纪初爱尔兰数学家W. R. Hamilton最初定义该问题开始,一路奔向当今最前沿、最顶尖的解题尝试。 ......一起来看看 《迷茫的旅行商》 这本书的介绍吧!

随机密码生成器
随机密码生成器

多种字符组合密码

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具