您的位置: 首页  >  文章  >  怎么在Golang中实现一个List

怎么在Golang中实现一个List

分类: 文章 • 2022-08-01 15:28:26

这期内容当中小编将会给大家带来有关怎么在Golang中实现一个List，文章内容丰富且以专业的角度为大家分析和叙述，阅读完这篇文章希望大家可以有所收获。

实现方式：

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
}

上述就是小编为大家分享的怎么在Golang中实现一个List了，如果刚好有类似的疑惑，不妨参照上述分析进行理解。如果想知道更多相关知识，欢迎关注行业资讯频道。

相关推荐