登录
首页 >  Golang >  Go教程

Go语言数据结构怎么实现抄一个list示例

来源:亿速云

时间:2023-04-28 14:21:35 498浏览 收藏

“纵有疾风来,人生不言弃”,这句话送给正在学习Golang的朋友们,也希望在阅读本文《Go语言数据结构怎么实现抄一个list示例》后,能够真的帮助到大家。我也会在后续的文章中,陆续更新Golang相关的技术文章,有好的建议欢迎大家在评论留言,非常感谢!

这篇文章主要介绍了Go语言数据结构怎么实现抄一个list示例的相关知识,内容详细易懂,操作简单快捷,具有一定借鉴价值,相信大家阅读完这篇Go语言数据结构怎么实现抄一个list示例文章都会有所收获,下面我们一起来看看吧。

list是个啥

在开始做之前,还是要先了解一下链表这个数据结构 ,长话短说:

  • 线性表的链式存储结构称为链表,如:

a.next = b
a.prev = c
b.next = c
b.prev = a
c.next = a
c.prev = b

这就是一个双向循环链表

  • 链表可以提升存储空间的利用率,实现了存储空间动态管理的链式存储结构

接下来,我们来看看Go官方都为这个list提供了哪些操作,我们逐一实现

Go语言数据结构怎么实现抄一个list示例

  • New:创建一个链表

  • Init:初始化一个链表

  • Back:返回链表中的最后一个元素

  • Front:返回链表中的第一个元素

  • InsertAfter(e,at):将e加入at元素后

  • InsertBefore(e,at):将e加入at元素前

  • Len:返回list的长度

  • PushBack(e):将e成为链表的最后一个元素

  • PushFront(e):将e成为链表的第一个元素

  • Remove(e):将list上的e删除

list结构

定义list结构,以及list内部node节点的结构,这里采用struct实现

type Element struct {
	prev, next *Element
	Value      any
}
type List struct {
	root Element
	len  int
}

Init & New

Init就是提供初始化一个环链表的方法,并返回这个环形链表

之所以把 Init 和 New 放在一起,是因为在 New 函数中其实就是对 Init 的一层包装,这样就可以实现Go中的包名.New方法,比如:errors.New()

// 初始化一个 环list
func (list *List) Init() *List {
	// 形成环
	list.root.next = &list.root
	list.root.prev = &list.root
	list.len = 0
	return list
}
func NewList() *List {
	return new(List).Init()
}

InsertAfter & InsertBefore & PushBack & PushFront

这两个方法的作用类似,就是将 e 插入到 at 的后/前位置

这里我们先看一个图:

Go语言数据结构怎么实现抄一个list示例

这个图片就是一个双向环形链表,我们要在这个里面进行插入元素操作,比如,我们要插入 e 到 e1 前面我们应该怎么做?

  • 将e的下一个变为e1:e.next = e1

  • 将e的上一个变为e1的上一个:e.prev = e1.prev

  • 将e的上一个的下一个变为自己:e.prev.next = e

  • 将e的下一个的上一个变为自己:e.next.prev = e

这样就完成了插入,回到方法实现上,一个是插入之后,一个插入之前,那么我们是不是可以看作是相同操作,其实都已插入操作,只是位置的变化。

这时候想象一下,比如让你 e 插入 at 之前,但是只提供了,参数1插入参数2后面的操作,如何办到呢?

将 e 插入到 at 的前一个的后面,是不是就ok了,就相当于自己让别人插个队,你在我前面的后面站就行了

// Insert 插入:将 currentElement 插入至 originElement 后
func (list *List) Insert(currentElement, originElement *Element) *Element {
	currentElement.next = originElement.next
	currentElement.prev = originElement
	currentElement.prev.next = currentElement
	currentElement.next.prev = currentElement
	list.len++
	return currentElement
}
// InsertAfter 插入在之后
func (list *List) InsertAfter(currentElement, originElement *Element) *Element {
	return list.Insert(currentElement, originElement)
}
// InsertBefore 插入在之前
func (list *List) InsertBefore(currentElement, originElement *Element) *Element {
	return list.Insert(currentElement, originElement.prev)
}

这样一来,好像把 PushBack 和 PushFront都实现了,这就是封装的好处

// PushBack 插入一个元素在最后
func (list *List) PushBack(originElement *Element) *Element {
	list.InsertBefore(originElement, &list.root)
	return originElement
}
// PushFront 插入一个元素在最前
func (list *List) PushFront(originElement *Element) *Element {
	list.InsertAfter(originElement, &list.root)
	return originElement
}

Back & Front

这两个方式抽象上说,也是一样的功能,一个是返回链表最后一个,另一个是返回链表第一个,因为这里提供了头结点,所以特别简单

最后一个节点 = 头结点.prev

第一个节点 = 头结点.next

// Back 返回最后一个元素
func (list *List) Back() *Element {
	if list.len == 0 {
		return nil
	}
	// 头结点的上一个就是最后一个
	return list.root.prev
}
// Front 返回第一个元素
func (list *List) Front() *Element {
	if list.len == 0 {
		return nil
	}
	// 头结点的下一个就是第一个元素
	return list.root.next
}

Remove

Remove方法就是提供了,删除链表上的某个元素,怎么样才能删除某个节点呢,本质也就是让前后的节点相互链表,我就被排挤出来了,这样就可以实现删除

  • 将要删除的元素 e.next.prev = e.prev

  • 将要删除的元素 e.prev.next = e.next

// Remove 删除某个元素
func (list *List) Remove(originElement *Element) (any,error) {
	if originElement == &list.root {
		return nil, errors.New("the origin Element can not be list.root")
	}
	for e := list.root.next; e != &list.root; e = e.next {
		if e == originElement {
			e.prev.next = e.next
			e.next.prev = e.prev
			return e.Value, nil
		} else {
			continue
		}
	}
	return nil, errors.New("the origin Element dose not belong to the list")
}

关于“Go语言数据结构怎么实现抄一个list示例”这篇文章的内容就介绍到这里,感谢各位的阅读!相信大家对“Go语言数据结构怎么实现抄一个list示例”知识都有一定的了解,大家如果还想学习更多知识,欢迎关注golang学习网行业资讯频道。

今天关于《Go语言数据结构怎么实现抄一个list示例》的内容介绍就到此结束,如果有什么疑问或者建议,可以在golang学习网公众号下多多回复交流;文中若有不正之处,也希望回复留言以告知!

声明:本文转载于:亿速云 如有侵犯,请联系study_golang@163.com删除
相关阅读
更多>
最新阅读
更多>
课程推荐
更多>