清风细雨楼

Golang中List的实现方法示例详解
脚本专栏 2024/12/27 佚名
3 1
清风细雨楼 Design By www.eepep.com

前言

为了快速回顾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的语法特性。个人认为学习编程，语法是最简单的，应该利用最短的时间在，最有效的掌握。

总结

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

清风细雨楼 Design By www.eepep.com
广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！
清风细雨楼 Design By www.eepep.com
www.eepep.com 清风细雨楼
120,135影音资源
344,641技术资源
22,817软件资源
435,032站长资源

更新日志

友情链接

杰晶网络 DDR爱好者之家 桃源资源网 杰网资源 富贵资源网 南强小屋 铁雪资源网 幽灵资源网 万梅资源网 狼山资源网 白云岛资源网 昆仑资源网 相思资源网 明霞山资源网 内蒙古资源网 黑松山资源网 茶园资源网 饿虎岗资源网 大旗谷资源网 常春岛资源网 岱庙资源网 兴国资源网 快活林资源网 蝙蝠岛资源网 帝王谷资源网 白云城资源网 伏龙阁资源网 清风细雨楼 天枫庄资源网 圆月山庄资源网 无争山庄资源网 神水资源网 移花宫资源网 神剑山庄资源网 无为清净楼资源网 金钱帮资源网 丐帮资源网 华山资源网 极乐门资源网 小李飞刀资源网 凤求凰客栈 风云阁资源网 金狮镖局 鸳鸯亭资源网 千金楼资源网 更多链接
清风细雨楼 Design By www.eepep.com