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

x_zhaohu · · 2324 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

原本打算用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中元素抽象成了ElementElement并存在自己读取前后节点的方法。

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中的存储操作方法如下:

如上这些公开的方法都是建立在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中的获取操作

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

List中的删除操作

然而上述方法内部调用了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的思想!(这篇文章,主要就是上面的两张图)

参考文献


有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:x_zhaohu

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

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:1006366459

2324 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传