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

2017-06-15 本文已影响293人 x_zhaohu

原本打算用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{})流程图：

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

pushfront.png

假设上面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中的移动操作

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

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

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