《Go源码解读篇》之常见数据结构(list)

原本打算用Go实现Java中常见的集合,简单实现ArrayList后,之后翻官网的package,发现了container/list,发现其实现十分的简洁,所以学习记录如下:

List实现准备工作

如果想实现一个list,首先想到解决问题:

• 数据类型怎么处理?
• Go中有没有像Java中Object似的,万能的数据类型呢?

多亏Go中存在interface{}这样万能的数据类型,问题就迎刃而解啦!

来看看我的ArrayList实现设计:

type ArrayList struct {
 size int32
 data []interface{}
}

我利用slice来实现简单的list(单向链表)操作,再看看官网的实现:

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

哈哈,这么一对比,我都有些害羞啦!官网上更面向对象化,把List中元素抽象成了Element,Element并存在自己读取前后节点的方法。

Element中获取操作

• 获取自身的Value
• 获取前驱节点
• 获取后继节点

Go的特点之一就是,其访问权限用首字母大小写来区分,Element可以直接获取其Value,而前后节点则分别提供了方法:

func (e *Element) Next() *Element {
 if p := e.next; e.list != nil && p != &e.list.root {
 return p
 }
 return nil
}
func (e *Element) Prev() *Element {
 if p := e.prev; e.list != nil && p != &e.list.root {
 return p
 }
 return nil
}

好不好奇,为什么类型是*Element? 当然是修改其值啦!
指针传递对象的引用,而非指针则是对对象的copy,指针使用规则如下:

• 只要需要修改对象的时候,才必须使用指针,它不是Go语言的约束,而是一种自然约束。
• 有时对象很小,用指针传递并不划算

List的初始化

List通过调用New()方法来初始化一个list,New()方法实现如下代码,Init()中将root.next,root.prev全都指向了root,这将在为下面的实现做铺垫

//Init initializes or clears list l
func (l *List) Init() *List {
 l.root.next = &l.root // next ---> root
 l.root.prev = &l.root // next ---> root
 //l.root.list = l //
 l.len = 0
 return l
}
func New() *List {
 //new 申请内存初始化
 list := new(List)
 return list.Init()
}

执行完上New()后,会产生一个类似{{0x000001, 0x000001, nil, nil}, 0}对象(0x000001只是个栗子),然而这个地址就是Element.list,保证list中的一致性。

List中的存储操作

List中的存储操作方法如下:

• func (l List) InsertAfter(v interface{}, mark Element) *Element :在mark元素后添加元素
• func (l List) InsertBefore(v interface{}, mark Element) *Element:在mark元素前添加元素
• func (l List) PushBack(v interface{}) Element :在list尾添加元素
• func (l List) PushBackList(other List):在list尾添加元素列表
• func (l List) PushFront(v interface{}) Element :在list头添加元素
• func (l List) PushFrontList(other List):在list头添加元素列表

如上这些公开的方法都是建立在insert(e, at *Element)和insertValue(v interface{}, at *Element)方法之上的,代码如下:

//insert e after at
func (l *List) insert(e, at *Element) *Element {
 n := at.next
 at.next = e
 e.prev = at
 e.next = n
 n.prev = e
 e.list = l
 l.len++
 fmt.Println("l.root.prev:", l.root.prev, " l.root.next:", l.root.next)
 return e
}
func (l *List) insertValue(v interface{}, at *Element) *Element {
 //创建新的节点
 return l.insert(&Element{Value: v}, at)
}

需要说明的是,insert(e, at *Element)实现是将e放到at后面啦,这对理解后面的代码很有帮助。
附上PushBack(v interface{})流程图:

由于PushFront(v interface{})执行过程与PushBack(v interface{})相反,所以附上其图如下,仔细观察,便知道其区别:

假设上面Element的地址分别为0x001,0x002,0x003,分别将2,3放入列表中.
如上方法实现很简单,都在建立"insertValue(v interface{}, at *Element)"之上的,所以不在文章中贴代码啦!

List中的获取操作

• func (l List) Back() Element :获取最后节点
• func (l List) Front() Element:获取第一个节点

一开始初始化的节点,就是存放头结点和尾节点指针用的,所以Back()操作返回其l.root.prev,Front()操作返回其l.root.next就搞定啦!

List中的删除操作

• func (l List) Remove(e Element) interface{}

然而上述方法内部调用了remove(e *Element), 代码如下:

func (l *List) remove(e *Element) *Element {
 e.prev.next = e.next
 e.next.prev = e.prev
 //avoid memory leaks
 e.prev = nil
 e.next = nil
 e.list = nil
 l.len--
 return e
}

该方法的作用就是修改需要删除节点的前驱和后继节点,最后将其前后节点指针置空,防止内存异常。

List中的移动操作

• func (l List) MoveAfter(e, mark Element)
• func (l List) MoveBefore(e, mark Element)
• func (l List) MoveToBack(e Element)
• func (l List) MoveToFront(e Element)

所以移动操作,都是借助insertValue(v interface{}, e *Element)和remove(e *Element)方法搞定的,使用的真是巧妙,具体查看源码吧!

注意:list不是协程安全的。

总体来说,通过翻阅list源码,掌握了它代码实现的list存储结构,更体会到了OOD的思想!(这篇文章,主要就是上面的两张图)

参考文献

• https://golang.org/pkg/container/list/#pkg-overview
• https://golang.org/src/container/list/list.go?s=922:955#L21

本文来自:简书

感谢作者:x_zhaohu

查看原文:《Go源码解读篇》之常见数据结构(list)

• 编辑
• 预览