• 企业400电话
  • 微网小程序
  • AI电话机器人
  • 电商代运营
  • 全 部 栏 目

    企业400电话 网络优化推广 AI电话机器人 呼叫中心 网站建设 商标✡知产 微网小程序 电商运营 彩铃•短信 增值拓展业务
    Golang中List的实现方法示例详解

    前言

    为了快速回顾Go基本的语法知识,打算用Go中的基本语法以及特性来实现一些常见的数据结构和排序算法,通过分析如何实现一些基本的数据结构,可以很快学习Go的语法特性。记忆更加深刻,掌握更加迅速。这是我认为学习一门新语言入门最好的方式。这也是方便自己以后需要用Go来写东西的一种前期准备,到时候就不用去翻一些教程了。系列博文的第一篇就从如何实现List开始。

    需求

    大家都知道基本链表得有以下特性:链表的初始化、链表的长度、节点的插入、删除、查找等一些常见的基本操作,最后写好之后,需要测试。关于测试,我之前写过Go的系列笔记中有叙述,不再重复。

    实现

    初始化

    有语言基础的人都知道,链表是由节点连接而成,这其中在定义一个List数据结构之外,还需要定义一个Node类型的数据结构。先说Node类型的数据结构,首先List按照正常的设计应该是可以存储基本类型的数据的,这就要求Node中的Value至于的类型不能固定,此时你可能反驳道:在Java中我们不是可以传入Int、String类型到List吗?其实这就是在走偏了,现在的工作是实现List这种数据结构。所以不能对其Value值域有任何类型限制,在Go中'空接口'恰好能够满足这种须需求。另外在List中一个Node需要两个指针域,分别指向前后节点的地址。在Go中这种需求,可以通过 *来实现,简单理解为其可以存储地址。如*Int就是int类型的地址。看实现方式:

    type Node struct {
     Value interface{} 
     next, prev *Node 
    }

    下面就是定义List结构体了,有了上面的分析,List结构体的定义就很好实现了:

    type List struct {
     root Node // 头节点
     length int // list长度
    }

    那么在构建好基本的数据结构之后,如何去获取一个List对象呢。先不着急实现,想想在Java语言中怎么实现的:

    Person p = new Man();

    如上所示,首先获取一个Man类的实例,然后p中有对象的地址/引用。从这些分析我们大概知道如何去创建一个list对象了,最终需要的结果就是获取一个List的引用/地址,并且该List的长度为0。除此之外,需要处理好空List的情况:

    // 返回List的指针
    func New() *List {
     l := List{}// 获取List{}的地址
     l.length = 0// list初始长度为0
     l.root.next = l.root
     l.root.prev = l.root
     return l
    }

    判空和长度

    List的判空和获取长度也是非常基础和重要的,判断是否为空,返回的数据类型是布尔类型的。什么情况下List是为空呢?根据前面的定义,头节点的next指针域指向是头结点本身的地址即为空。另外,判空函数写好了,总不能什么类型的数据都去调用这个函数,我们需要指定调用的数据类型,在本例中当然是 List类型的了,为了方便操作,传入一个List的地址即可。

    func (l *List) IsEmpty() bool {
     return l.root.next == l.root
    }

    分析完毕之后,获取list的长度就简单很多了:

    func (l *List) Length() int {
     return l.length
    }

    头插和尾插

    因为在定义List数据结构的时候,就定义了一个root头节点。所以此时,可以很方便的实现头插入和尾插入。考虑能够同时插入多个/一个Node节点,利用Go中的变长参数实现该特性。对插入的Node节点进行循环处理,新节点的指针域和root节点的指针域做相应改变,具体实现方式以及说明在代码中说明:

    func (l *List) PushFront(elements ...interface{}) {
     for _, element := range elements {
     n := Node{Value: element} // 注释一
     n.next = l.root.next // 新节点的next是root节点的next
     n.prev = l.root // 新节点的prev存储的是root的地址
     l.root.next.prev = n // 原来root节点的next的prev是新节点
     l.root.next = n // 头插法 root 之后始终是新节点
     l.length++ // list 长度加1
     }
    }

    注释1处拿出来分析:结构体初始化方式 Node{Value:element} , 是获取结构体地址的方式。此时需要一个地址类型的变量来存储结构体的地址,此时看看声明方式为 :n这里就学习到了Go中临时变量的声明方式啦。并且该临时变量不需要指明数据类型。尾插法就很简单了,参见如下所示代码:

    func (l *List) PushBack(elements ...interface{}) {
     for _, element := range elements {
     n := Node{Value: element}
     n.next = l.root // since n is the last element, its next should be the head
     n.prev = l.root.prev // n's prev should be the tail
     l.root.prev.next = n // tail's next should be n
     l.root.prev = n // head's prev should be n
     l.length++
     }
    }

    查找

    查找最终的效果是返回指定数值的索引,如果不存在的话返回-1即可。对于链表的查找是一个遍历的过程,在此时就需要考虑遍历的起始和终止区间了,不能越界出错。因为是循环链表,终止节点也很好办。具体代码如下所示:

    func (l *List) Find(element interface{}) int {
     index := 0
     p := l.root.next
     for p != l.root  p.Value != element {
     p = p.next
     index++
     }
     // p不是root
     if p != l.root {
     return index
     }
    
     return -1
    }

    删除

    链表的删除操作逻辑很清晰,将一个Node的节点与前后节点断开即可,同时前后节点和Node节点本身指针域也要做相应修改,最后别忘记将链表的长度减少相应长度。

    func (l *List) remove(n *Node) {
     n.prev.next = n.next
     n.next.prev = n.prev
     n.next = nil
     n.prev = nil
     l.length--
    }

    删除并返回List中的第一个数据:

    func (l *List) Lpop() interface{} {
     if l.length == 0 {
     // null的表现形式nil
     return nil
     }
     n := l.root.next
     l.remove(n)
     return n.Value
    }

    遍历

    下面normalIndex函数的作用返回一个正常逻辑的Index,例如处理好一些越界问题:

    func (l *List) normalIndex(index int) int {
     if index > l.length-1 {
     index = l.length - 1
     }
    
     if index  -l.length {
     index = 0
     }
     // 将给定的index与length做取余处理
     index = (l.length + index) % l.length
     return index
    }

    如下的函数为获取指定范围内的数据,根据传入的参数需要指定start和end,最后返回的应该是一个切片或者数组,具体类型未知:

    func (l *List) Range(start, end int) []interface{} {
     // 获取正常的start和end
     start = l.normalIndex(start)
     end = l.normalIndex(end)
     // 声明一个interface类型的数组
     res := []interface{}{}
     // 如果上下界不符合逻辑,返回空res
     if start > end {
     return res
     }
     
     sNode := l.index(start)
     eNode := l.index(end)
     // 起始点和重点遍历
     for n := sNode; n != eNode; {
     // res的append方式
     res = append(res, n.Value)
     n = n.next
     }
     res = append(res, eNode.Value)
     return res
    }

    ok,以上即为Go中List的数据结构的实现方式,通过本节,能够学习到许多Go的语法特性。个人认为学习编程,语法是最简单的,应该利用最短的时间在,最有效的掌握。

    总结

    以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作能带来一定的帮助,如果有疑问大家可以留言交流,谢谢大家对脚本之家的支持。

    您可能感兴趣的文章:
    • 基于golang中container/list包的用法说明
    • golang使用grpc+go-kit模拟oauth认证的操作
    • golang中for range的取地址操作陷阱介绍
    • golang如何去除多余空白字符(含制表符)
    • 用golang如何替换某个文件中的字符串
    • golang正则之命名分组方式
    • 解决golang中container/list包中的坑
    上一篇:使用dep 配置golang 开发环境的操作方法
    下一篇:Golang中Set类型的实现方法示例详解
  • 相关文章
  • 

    © 2016-2020 巨人网络通讯 版权所有

    《增值电信业务经营许可证》 苏ICP备15040257号-8

    Golang中List的实现方法示例详解 Golang,中,List,的,实现,方法,