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类型的地址。看实现方式：
typeNodestruct{
Valueinterface{}
next,prev*Node
}
下面就是定义List结构体了，有了上面的分析，List结构体的定义就很好实现了：
typeListstruct{
rootNode//头节点
lengthint//list长度
}
那么在构建好基本的数据结构之后，如何去获取一个List对象呢。先不着急实现，想想在Java语言中怎么实现的：
Personp=newMan();
如上所示，首先获取一个Man类的实例，然后p中有对象的地址/引用。从这些分析我们大概知道如何去创建一个list对象了，最终需要的结果就是获取一个List的引用/地址，并且该List的长度为0。除此之外，需要处理好空List的情况：
//返回List的指针
funcNew()*List{
l:=&List{}//获取List{}的地址
l.length=0//list初始长度为0
l.root.next=&l.root
l.root.prev=&l.root
returnl
}
判空和长度
List的判空和获取长度也是非常基础和重要的，判断是否为空，返回的数据类型是布尔类型的。什么情况下List是为空呢？根据前面的定义，头节点的next指针域指向是头结点本身的地址即为空。另外，判空函数写好了，总不能什么类型的数据都去调用这个函数，我们需要指定调用的数据类型，在本例中当然是List类型的了，为了方便操作，传入一个List的地址即可。
func(l*List)IsEmpty()bool{
returnl.root.next==&l.root
}
分析完毕之后，获取list的长度就简单很多了：
func(l*List)Length()int{
returnl.length
}
头插和尾插
因为在定义List数据结构的时候，就定义了一个root头节点。所以此时，可以很方便的实现头插入和尾插入。考虑能够同时插入多个/一个Node节点，利用Go中的变长参数实现该特性。对插入的Node节点进行循环处理，新节点的指针域和root节点的指针域做相应改变，具体实现方式以及说明在代码中说明：
func(l*List)PushFront(elements...interface{}){
for_,element:=rangeelements{
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:=rangeelements{
n:=&Node{Value:element}
n.next=&l.root//sincenisthelastelement,itsnextshouldbethehead
n.prev=l.root.prev//n'sprevshouldbethetail
l.root.prev.next=n//tail'snextshouldben
l.root.prev=n//head'sprevshouldben
l.length++
}
}
查找
查找最终的效果是返回指定数值的索引，如果不存在的话返回-1即可。对于链表的查找是一个遍历的过程，在此时就需要考虑遍历的起始和终止区间了，不能越界出错。因为是循环链表，终止节点也很好办。具体代码如下所示：
func(l*List)Find(elementinterface{})int{
index:=0
p:=l.root.next
forp!=&l.root&&p.Value!=element{
p=p.next
index++
}
//p不是root
ifp!=&l.root{
returnindex
}
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{}{
ifl.length==0{
//null的表现形式nil
returnnil
}
n:=l.root.next
l.remove(n)
returnn.Value
}
遍历
下面normalIndex函数的作用返回一个正常逻辑的Index，例如处理好一些越界问题：
func(l*List)normalIndex(indexint)int{
ifindex>l.length-1{
index=l.length-1
}
ifindex<-l.length{
index=0
}
//将给定的index与length做取余处理
index=(l.length+index)%l.length
returnindex
}
如下的函数为获取指定范围内的数据，根据传入的参数需要指定start和end，最后返回的应该是一个切片或者数组，具体类型未知：
func(l*List)Range(start,endint)[]interface{}{
//获取正常的start和end
start=l.normalIndex(start)
end=l.normalIndex(end)
//声明一个interface类型的数组
res:=[]interface{}{}
//如果上下界不符合逻辑，返回空res
ifstart>end{
returnres
}
sNode:=l.index(start)
eNode:=l.index(end)
//起始点和重点遍历
forn:=sNode;n!=eNode;{
//res的append方式
res=append(res,n.Value)
n=n.next
}
res=append(res,eNode.Value)
returnres
}
ok,以上即为Go中List的数据结构的实现方式，通过本节，能够学习到许多Go的语法特性。个人认为学习编程，语法是最简单的，应该利用最短的时间在，最有效的掌握。
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作能带来一定的帮助，如果有疑问大家可以留言交流，谢谢大家对毛票票的支持。