Golang源码 container 系列二 list链表

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

关于ring,可以参考Golang源码 container 系列一 ring环形链表,list也是个链表,但是稍有差别。

参考【Go】笔记五 | container包中的list与ring

一、源码对比
type Ring struct {
    next, prev *Ring
    Value      interface{} 
}

// Element is an element of a linked list.
type Element struct {
    // Next and previous pointers in the doubly-linked list of elements.
    // To simplify the implementation, internally a list l is implemented
    // as a ring, such that &l.root is both the next element of the last
    // list element (l.Back()) and the previous element of the first list
    // element (l.Front()).
    next, prev *Element

    // The list to which this element belongs.
    list *List

    // The value stored with this element.
    Value interface{}
}

// New creates a ring of n elements.
func New(n int) *Ring {
    if n <= 0 {
        return nil
    }
    r := new(Ring)
    p := r
    for i := 1; i < n; i++ {
        p.next = &Ring{prev: p}
        p = p.next
    }
    p.next = r
    r.prev = p
    return r
}

// List represents a doubly linked list.
// The zero value for List is an empty list ready to use.
type List struct {
    root Element // sentinel list element, only &root, root.prev, and root.next are used
    len  int     // current list length excluding (this) sentinel element
}

// Init initializes or clears list l.
func (l *List) Init() *List {
    l.root.next = &l.root
    l.root.prev = &l.root
    l.len = 0
    return l
}

// New returns an initialized list.
func New() *List { return new(List).Init() }
二、区别

1.经过语句var l list.List声明的变量l的值将会是怎样的?
这个零值将会是一个长度为0的链表。这个链表持有的根元素也将会是一个空壳,其中只会包含缺省的内容。

2.那这样的链表我们可以直接拿来使用吗?
可以的。这被称为“开箱即用”。Go 语言标准库中的很多结构体,都做到了开箱即用。这也是在编写可供别人使用的代码包(或者说.程序库)时我们推荐遵循的最佳实践之一。

3.可以把自己生成的Element类型值传给链表吗?
不会接受,这些方法将不会对链表做出任何改动。因为我们自己生成的值并不在链表中,所以也就谈不上“在链表中移动元素”。更何况链表不允许我们把自己生成的值插入其中。

4.为什么不接受自己生成的Element类型值?
在List包含的方法中,用于插入新元素的那些方法都只接受interface{}类型的值。这些方法在内部会使用Element值包装接收到的新元素。这样做正是为了避免直接使用我们自己生成的元素,主要原因是避免链表的内部关联遭到外界破坏,这对于链表本身以及我们这些使用者来说,都是有益的。

//InsertBefore和InsertAfter分别用于在指定的元素之前和之后插入数据.
//PushFront和PushBack则是向链表最前端和最后端插入数据.
func (l *List) InsertBefore( v interface{}, mark *Element) *Element
func (l *List) InsertAfter (v interface{},mark *Element) *Element
func (l *List) PushFront(v interface{}) *Element
func (l *List) PushBack(v interface{}) *Element

5.Ring与List的区别在哪儿?
container/ring包中的Ring类型实现的是一个循环链表,也就是我们俗称的环。其实List在内部就是一个循环链表。它的根元素永远不会持有任何实际的元素值,而该元素的存在,就是为了连接这个循环链表的首尾两端。

所以也可以说,List的零值是一个只包含了根元素,但不包含任何实际元素值的空链表。两者本质都是循环链表,最主要的不同有下面几种。

  • Ring类型的数据结构仅由它自身即可代表,而List类型则需要由它以及Element类型联合表示。这是表示方式上的不同,也是结构复杂度上的不同。
  • 一个Ring类型的值严格来讲,只代表了其所属的循环链表中的一个元素,而一个List类型的值则代表了一个完整的链表。这是表示维度上的不同。
  • 在创建并初始化一个Ring值的时候,我们可以指定它包含的元素的数量,但是对于一个List值来说,却不能这样做(也没有必要这样做)。循环链表一旦被创建,其长度是不可变的。这是两个代码包中的New函数在功能上的不同,也是两个类型在初始化值方面的第一个不同。
  • 仅通过var r ring.Ring语句声明的r将会是一个长度为1的循环链表,而List类型的零值则是一个长度为0的链表。别忘了List中的根元素不会持有实际元素值,因此计算长度时不会包含它。这是两个类型在初始化值方面的第二个不同。
  • Ring值的Len方法的算法复杂度是 O(N) 的,而List值的Len方法的算法复杂度则是 O(1)的。这是两者在性能方面最显而易见的差别。

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

本文来自:简书

感谢作者:懒皮

查看原文:Golang源码 container 系列二 list链表

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

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