数据结构——Golang实现单链表

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

内容简介:转载请注明出处:列表是由结点构成,head指针指向第一个成为表头结点,而终止于最后一个指向nuLL的指针。

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

数据结构——Golang实现单链表

Golang

1. 单链表

1.1. 定义

单向链表 (单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始;链表是使用指针进行构造的列表;又称为结点列表,因为链表是由一个个结点组装起来的;其中每个结点都有指针成员变量指向列表中的下一个结点;

列表是由结点构成,head指针指向第一个成为表头结点,而终止于最后一个指向nuLL的指针。

1.2. 优点

  1. 单个结点创建非常方便,普通的线性内存通常在创建的时候就需要设定数据的大小
  2. 结点的删除非常方便,不需要像线性结构那样移动剩下的数据
  3. 结点的访问方便,可以通过循环或者递归的方法访问到任意数据,但是平均的访问效率低于线性表。

2. Golang 实现

2.1. 相关结构体

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

具体定义如下:

// 节点数据
type SingleObject interface{}

// 单链表节点
type SingleNode struct {
    Data SingleObject
    Next *SingleNode
}

// 单链表
type SingleList struct{
    mutex *sync.RWMutex
    Head *SingleNode
    Tail *SingleNode
    Size uint
}

2.2. 链表初始化

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

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

2.3. 新增节点

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

另外新增时,若为第一个节点需特殊处理一下。下面请看代码:

// 添加节点到链表尾部
func (list *SingleList)Append(node *SingleNode) bool {
    if node == nil{
        return false
    }
    list.mutex.Lock()
    defer list.mutex.Unlock()
    if list.Size == 0{
        list.Head = node
        list.Tail = node
        list.Size = 1
        return true
    }

    tail := list.Tail
    tail.Next = node
    list.Tail = node
    list.Size += 1
    return true
}

// 插入节点到指定位置
func (list *SingleList)Insert(index uint, node *SingleNode) bool {
    if node == nil {
        return false
    }

    if index > list.Size{
        return false
    }

    list.mutex.Lock()
    defer list.mutex.Unlock()

    if index == 0{
        node.Next = list.Head
        list.Head = node
        list.Size += 1
        return true
    }
    var i uint
    ptr := list.Head
    for i = 1; i < index; i ++ {
        ptr = ptr.Next
    }
    next := ptr.Next
    ptr.Next = node
    node.Next = next
    list.Size += 1
    return true
}

2.4. 删除节点

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

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

    list.mutex.Lock()
    defer list.mutex.Unlock()

    if index == 0 {
        head := list.Head.Next
        list.Head = head
        if list.Size == 1{
            list.Tail = nil
        }
        list.Size -= 1
        return true
    }

    ptr := list.Head
    var i uint
    for i = 1; i < index; i++{
        ptr = ptr.Next
    }
    next := ptr.Next
    
    ptr.Next = next.Next
    if index == list.Size - 1 {
        list.Tail = ptr
    }
    list.Size -= 1
    return true
}

2.6. 查询节点

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

// 获取指定位置的节点,不存在则返回nil
func (list *SingleList)Get(index uint) *SingleNode{
    if list == nil || list.Size == 0 || index > list.Size - 1 {
        return nil
    }

    list.mutex.RLock()
    defer list.mutex.RUnlock()
    
    if index == 0{
        return list.Head
    }
    node := list.Head
    var i uint
    for i = 0; i < index; i ++ {
        node = node.Next
    }
    return node
}

2.7. 打印链表

最后,我们增加一个打印链表的功能,方便我们看整个链表的内容:

// 输出链表
func (list *SingleList)Display(){
    if list == nil {
        fmt.Println("this single list is nil")
        return
    }
    list.mutex.RLock()
    defer list.mutex.RUnlock()
    fmt.Printf("this single list size is %d \n", list.Size)
    ptr := list.Head
    var i uint
    for i = 0; i < list.Size; i++{
        fmt.Printf("No%3d data is %v\n", i + 1, ptr.Data)
        ptr = ptr.Next
    }
}

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


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

查看所有标签

猜你喜欢:

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

你的灯亮着吗?

你的灯亮着吗?

高斯 (Donald C. Gause)、温伯格 (Gerald M.Weinberg) / 俞月圆 / 人民邮电出版社 / 2014-1-1 / CNY 25.00

本书以别具一格的视角和幽默风趣的语言讨论了解决问题时有可能遇到的多种困难,并就如何训练思维能力指点迷津。本书分六个主题,每个主题都由若干生动有趣和发人深省的小故事组成,巧妙地引导读者先确认真正的问题,然后明确问题该由谁解决,再确定问题的根源,最后决定到底想不想解决这个问题。 本书适合所有业界人士以及想要探索问题解决之道的虚心读者细细品味。一起来看看 《你的灯亮着吗?》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

SHA 加密
SHA 加密

SHA 加密工具

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具