Go 语言数据结构如何实现抄一个list示例详解
目录
- 前言
- list是个啥
- list结构
- Init & New
- InsertAfter & InsertBefore & PushBack & PushFront
- Back & Front
- Remove
- 总结
前言
闲来无事,自己实现一个 Go
提供的list
包
- list是Go提供的一个内置的包
- 内部就是实现了一个双向循环链表以及各种API
目标明确:就是实现一个双向循环链表
文章源码
list是个啥
在开始做之前,还是要先了解一下链表
这个数据结构 ,长话短说:
- 线性表的链式存储结构称为链表,如:
a.next = b a.pre编程v = c b.next = c b.prev = a c.next = a c.prev = b
这就是一个双向循环链表
- 链表可以提升存储空间的利用率,实现了存储空间动态管理的链式存储结构
接下来,我们来看看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 spythontruct { 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 的后/前位www.devze.com置
这里我们先看一个图:
这个图片就是一个双向环形链表,我们要在这个里面进行插入元素操作,比如,我们要插入 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 (l开发者_C开发ist *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的资料请关注我们其它相关文章!
精彩评论