极客时间已完结课程限时免费阅读

08 | container包中的那些容器

08 | container包中的那些容器-极客时间

08 | container包中的那些容器

2018-08-29 郝林 来自北京
《Go语言核心36讲》
课程介绍

讲述：黄洲君

时长09:40大小13.28M

我们在上次讨论了数组和切片，当我们提到数组的时候，往往会想起链表。那么 Go 语言的链表是什么样的呢？
Go 语言的链表实现在标准库的container/list代码包中。这个代码包中有两个公开的程序实体——List和Element，List 实现了一个双向链表（以下简称链表），而 Element 则代表了链表中元素的结构。
那么，我今天的问题是：可以把自己生成的Element类型值传给链表吗？
我们在这里用到了List的四种方法。
MoveBefore方法和MoveAfter方法，它们分别用于把给定的元素移动到另一个元素的前面和后面。
MoveToFront方法和MoveToBack方法，分别用于把给定的元素移动到链表的最前端和最后端。
在这些方法中，“给定的元素”都是*Element类型的，*Element类型是Element类型的指针类型，*Element的值就是元素的指针。
func (l *List) MoveBefore(e, mark *Element)
func (l *List) MoveAfter(e, mark *Element)
func (l *List) MoveToFront(e *Element)
func (l *List) MoveToBack(e *Element)
具体问题是，如果我们自己生成这样的值，然后把它作为“给定的元素”传给链表的方法，那么会发生什么？链表会接受它吗？
这里，给出一个典型回答：不会接受，这些方法将不会对链表做出任何改动。因为我们自己生成的Element值并不在链表中，所以也就谈不上“在链表中移动元素”。更何况链表不允许我们把自己生成的Element值插入其中。

问题解析

在List包含的方法中，用于插入新元素的那些方法都只接受interface{}类型的值。这些方法在内部会使用Element值，包装接收到的新元素。
这样做正是为了避免直接使用我们自己生成的元素，主要原因是避免链表的内部关联，遭到外界破坏，这对于链表本身以及我们这些使用者来说都是有益的。
List的方法还有下面这几种：
Front和Back方法分别用于获取链表中最前端和最后端的元素，
InsertBefore和InsertAfter方法分别用于在指定的元素之前和之后插入新元素，PushFront和PushBack方法则分别用于在链表的最前端和最后端插入新元素。
func (l *List) Front() *Element
func (l *List) Back() *Element
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
这些方法都会把一个Element值的指针作为结果返回，它们就是链表留给我们的安全“接口”。拿到这些内部元素的指针，我们就可以去调用前面提到的用于移动元素的方法了。
知识扩展
1. 问题：为什么链表可以做到开箱即用？
List和Element都是结构体类型。结构体类型有一个特点，那就是它们的零值都会是拥有特定结构，但是没有任何定制化内容的值，相当于一个空壳。值中的字段也都会被分别赋予各自类型的零值。
广义来讲，所谓的零值就是只做了声明，但还未做初始化的变量被给予的缺省值。每个类型的零值都会依据该类型的特性而被设定。
比如，经过语句var a [2]int声明的变量a的值，将会是一个包含了两个0的整数数组。又比如，经过语句var s []int声明的变量s的值将会是一个[]int类型的、值为nil的切片。
那么经过语句var l list.List声明的变量l的值将会是什么呢？[1] 这个零值将会是一个长度为0的链表。这个链表持有的根元素也将会是一个空壳，其中只会包含缺省的内容。那这样的链表我们可以直接拿来使用吗？
答案是，可以的。这被称为“开箱即用”。Go 语言标准库中很多结构体类型的程序实体都做到了开箱即用。这也是在编写可供别人使用的代码包（或者说程序库）时，我们推荐遵循的最佳实践之一。那么，语句var l list.List声明的链表l可以直接使用，这是怎么做到的呢？
关键在于它的“延迟初始化”机制。
所谓的延迟初始化，你可以理解为把初始化操作延后，仅在实际需要的时候才进行。延迟初始化的优点在于“延后”，它可以分散初始化操作带来的计算量和存储空间消耗。
例如，如果我们需要集中声明非常多的大容量切片的话，那么那时的 CPU 和内存空间的使用量肯定都会一个激增，并且只有设法让其中的切片及其底层数组被回收，内存使用量才会有所降低。
如果数组是可以被延迟初始化的，那么计算量和存储空间的压力就可以被分散到实际使用它们的时候。这些数组被实际使用的时间越分散，延迟初始化带来的优势就会越明显。
实际上，Go 语言的切片就起到了延迟初始化其底层数组的作用，你可以想一想为什么会这么说的理由。
延迟初始化的缺点恰恰也在于“延后”。你可以想象一下，如果我在调用链表的每个方法的时候，它们都需要先去判断链表是否已经被初始化，那这也会是一个计算量上的浪费。在这些方法被非常频繁地调用的情况下，这种浪费的影响就开始显现了，程序的性能将会降低。
在这里的链表实现中，一些方法是无需对是否初始化做判断的。比如Front方法和Back方法，一旦发现链表的长度为0, 直接返回nil就好了。
又比如，在用于删除元素、移动元素，以及一些用于插入元素的方法中，只要判断一下传入的元素中指向所属链表的指针，是否与当前链表的指针相等就可以了。
如果不相等，就一定说明传入的元素不是这个链表中的，后续的操作就不用做了。反之，就一定说明这个链表已经被初始化了。
原因在于，链表的PushFront方法、PushBack方法、PushBackList方法以及PushFrontList方法总会先判断链表的状态，并在必要时进行初始化，这就是延迟初始化。
而且，我们在向一个空的链表中添加新元素的时候，肯定会调用这四个方法中的一个，这时新元素中指向所属链表的指针，一定会被设定为当前链表的指针。所以，指针相等是链表已经初始化的充分必要条件。
明白了吗？List利用了自身以及Element在结构上的特点，巧妙地平衡了延迟初始化的优缺点，使得链表可以开箱即用，并且在性能上可以达到最优。
问题 2：Ring与List的区别在哪儿？
container/ring包中的Ring类型实现的是一个循环链表，也就是我们俗称的环。其实List在内部就是一个循环链表。它的根元素永远不会持有任何实际的元素值，而该元素的存在就是为了连接这个循环链表的首尾两端。
所以也可以说，List的零值是一个只包含了根元素，但不包含任何实际元素值的空链表。那么，既然Ring和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) 的。这是两者在性能方面最显而易见的差别。
其他的不同基本上都是方法方面的了。比如，循环链表也有用于插入、移动或删除元素的方法，不过用起来都显得更抽象一些，等等。
总结
我们今天主要讨论了container/list包中的链表实现。我们详细讲解了链表的一些主要的使用技巧和实现特点。由于此链表实现在内部就是一个循环链表，所以我们还把它与container/ring包中的循环链表实现做了一番比较，包括结构、初始化以及性能方面。
思考题
container/ring包中的循环链表的适用场景都有哪些？
你使用过container/heap包中的堆吗？它的适用场景又有哪些呢？
在这里，我们先不求对它们的实现了如指掌，能用对、用好才是我们进阶之前的第一步。好了，感谢你的收听，我们下次再见。
[1]：List这个结构体类型有两个字段，一个是Element类型的字段root，另一个是int类型的字段len。顾名思义，前者代表的就是那个根元素，而后者用于存储链表的长度。注意，它们都是包级私有的，也就是说使用者无法查看和修改它们。
像前面那样声明的l，其字段root和len都会被赋予相应的零值。len的零值是0，正好可以表明该链表还未包含任何元素。由于root是Element类型的，所以它的零值就是该类型的空壳，用字面量表示的话就是Element{}。
Element类型包含了几个包级私有的字段，分别用于存储前一个元素、后一个元素以及所属链表的指针值。另外还有一个名叫Value的公开的字段，该字段的作用就是持有元素的实际值，它是interface{}类型的。在Element类型的零值中，这些字段的值都会是nil。

参考阅读

切片与数组的比较

切片本身有着占用内存少和创建便捷等特点，但它的本质上还是数组。切片的一大好处是可以让我们通过窗口快速地定位并获取，或者修改底层数组中的元素。
不过，当我们想删除切片中的元素的时候就没那么简单了。元素复制一般是免不了的，就算只删除一个元素，有时也会造成大量元素的移动。这时还要注意空出的元素槽位的“清空”，否则很可能会造成内存泄漏。
另一方面，在切片被频繁“扩容”的情况下，新的底层数组会不断产生，这时内存分配的量以及元素复制的次数可能就很可观了，这肯定会对程序的性能产生负面的影响。
尤其是当我们没有一个合理、有效的”缩容“策略的时候，旧的底层数组无法被回收，新的底层数组中也会有大量无用的元素槽位。过度的内存浪费不但会降低程序的性能，还可能会使内存溢出并导致程序崩溃。
由此可见，正确地使用切片是多么的重要。不过，一个更重要的事实是，任何数据结构都不是银弹。不是吗？数组的自身特点和适用场景都非常鲜明，切片也是一样。它们都是 Go 语言原生的数据结构，使用起来也都很方便. 不过，你的集合类工具箱中不应该只有它们。这就是我们使用链表的原因。
不过，对比来看，一个链表所占用的内存空间，往往要比包含相同元素的数组所占内存大得多。这是由于链表的元素并不是连续存储的，所以相邻的元素之间需要互相保存对方的指针。不但如此，每个元素还要存有它所属链表的指针。
有了这些关联，链表的结构反倒更简单了。它只持有头部元素（或称为根元素）基本上就可以了。当然了，为了防止不必要的遍历和计算，链表的长度记录在内也是必须的。
戳此查看 Go 语言专栏文章配套详细代码。
分享给需要的人，Ta购买本课程，你将得18元
生成海报并分享

赞 29

提建议

© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
上一篇
07 | 数组和切片
下一篇
09 | 字典的操作和约束
unpreview
 写留言

精选留言(37)

  • 李皮皮皮皮皮
    2018-08-29
    1.list可以作为queue和 stack的基础数据结构 2.ring可以用来保存固定数量的元素，例如保存最近100条日志，用户最近10次操作 3.heap可以用来排序。游戏编程中是一种高效的定时器实现方案
    共 3 条评论
    122
  • 陌上人 .
    2018-11-28
    老师,之后的课可不可以多加一些图形解释,原理性的知识只用文字确实有些晦涩难懂
    共 9 条评论
    106
  • 传说中的成大大
    2020-03-04
    关于 container包中的链表list 和环ring的知识总结 按我的思考 1. 为什么go语言会出现list这个包 首先一个语言或者新技术的出现肯定是为了解决一些疑难杂症 在go语言中数组的特点非常鲜明 固定不可变 访问方便,但是如果不适合动态增长，所以出现了slice切片 切片是对数组的一层封装为了解决数组动态扩容问题， 但是实际上底层依赖的还是数组，但是问题来了 如果slice切片 在添加或者删除元素的时候如果没一个好的策略 扩容或者缩容过后旧的切片没有释放 则会造成内存泄漏 就是c语言的malloc 久而久之 内存越来越少 程序就会崩溃, 而List的出现就是为了解决动态扩容或者缩容的后遗症 因为依赖指针这个东西 所以删除和增加都非常方便 2. 延迟初始化机制 延迟初始化机制 主要是为了解决像数组这种 声明的时候就分配了内存空间的问题，有的时候我们只需要声明，但还不需要使用它，这个时候没有必要分配内存空间，再如文中提到的 在同一时刻声明大量的内存空间的话 那么cpu的使用和内存空间的使用将会激增 所以我们需要延迟初始化机制(设计模式中的单例模式也提到了延迟初始化问题,避免声明出来没人使用的尴尬局面) 3. list关于延迟初始化机制的一些处理 延迟初始化机制的缺点就在于在使用的时候需要判断是否已经初始化了,如果使用比较频繁的话，就会造成大量的计算浪费(cpu浪费) 所以list当中关于延迟初始化机制的处理方案如下 3.1 在插入新元素时 需要检查是否已经初始化好了 3.2 在移动 或者将已有元素再修改位置插入时 需要判断元素身上的链表是否和要操作的链表的指针相同 如果不相同说明元素不存在该链表中 如果相同则说明这个链表肯定已经初始化好了 4. ring包和list包的区别 首先从源码来看 type Ring struct { next, prev *Ring Value } type Element struct { next, prev *Element list *List //它所属的链表的指针 Value interface{} } type List struct { root element len int } 从源码的定义分析得出 ring 的元素就是ring结构体(只代表了一个元素) 而list的元素 是list+element(代表了一个链表) list在创建的时候不需要指定元素也没有必要,因为它会不停的增长 而ring的创建需要指定元素个数 且不再增长 并且list的还存在一个没有实际意义的根元素 该根元素还可以用来连接首位两端 使其成为一个循环链表 关于文中 两个结论的思考 结论1 go语言中切片实现了数组的延迟初始化机制 我的思考是 因为切片延迟初始化了， 所以他的底层数组在切片声明时也没有被初始化出来 结论2 ring 使用len方法是o(n) 而list使用len方法是o(1) 还没看讲解我就去翻看了源码(我比较喜欢的一句话是源码之下无秘密),从上面两个结构体的声明和list的insert方法可以看出 因为list的根元素这个根元素也代表了链表(突然想明白ring和list的第二点区别) 在这个根元素上存放了一个len数据表示链表的长度 insert时这个长度会执行+1,所以执行len方法时只需要取出这个长度即可从而达到了o(1)的时间复杂度 而ring结构体中却不存在这样的len所以需要遍历完整个环,所以时间复杂度为o(n) 关于思考题 1. ring包从实现来分析得出 适合用来执行长度固定的循环事件 2. heap包 则适合用来做堆排序 求第k大 第k小等问题 还有就是前面某些同学提到的优先调度问题 关于优先调度问题我觉得思路大概如下 首先维护一个堆 然后针对每个要调度的事件 分配一个优先级 然后从下到上执行堆化过程 让优先级(最低或者最高的放到堆的顶部) 当处理完成之后 再把堆尾部的事件放到堆顶部 然后执行从上往下进行堆化维护好堆的顺序 再执行逻辑
    展开
    共 4 条评论
    47
  • louis
    2019-04-23
    郝老师，这里不太理解什么叫“自己生成的Element类型值”？把自己生成的Element类型值传给链表——这个能不能再通俗点描述？

    作者回复: 比如你用 list.New 函数创建了一个 List 类型的双向链表，然后通过它的一些方法往里面塞了一些元素。可以往里面塞的元素的方法有 PushFront、PushBack、InsertAfter、InsertBefore 等。 但是你发现没有，这些方法接受的新元素的类型都是 interface{} 的。也就是说，这个 List 类型的链表只接受 interface{} 类型的新元素值。 而当新元素值进入链表之后，链表会把它们再包装成 list.Element 类型的值。你看，那些往里塞元素值的方法返回的都是被包装后的 *list.Element 类型的元素值。 当你像我这样浏览了 container/list.List 类型的相关 API 之后，就应该可以明白我问这个问题的背景了。 这个 List 类型只会接受 interface{} 类型的新元素值，并且只会吐出 *list.Element 类型的已有元素值。显然，任何移动已有元素值或者删除已有元素值的方法，都只会接受该链表自己吐出来的“Element 值”。因此，对于我们自己生成的“Element 值”，这个链表的任何方法都是不会接受的。 当然了，如果你之前完全没用过 List 类型，可能会觉得这个问题有些突兀。但是当你看完下面的详细解释之后，我相信你就会有所了解了。 我们这个专栏的一个风格就是：“先抛出问题，然后再解释前因后果”。目的就是，逼迫大家在碰到问题之后自己先去了解背景并试着找找答案，然后再回来看我的答案。这样的话，你对这些知识点的记忆会更牢固，不容易忘。 我非常希望这个专栏能成为大家的“枕边书”，而不是听听音频就放在一边的那种。所以才有了这样的结构设计。如果你们能在今后碰到问题时想起这个专栏，到这里翻一翻并能找到答案的线索，那我就太高兴了。

    共 5 条评论
    40
  • Err
    2018-10-23
    我觉得写一个实际的例子能帮助更好理解
    39
  • melon
    2018-08-29
    list的一个典型应用场景是构造FIFO队列；ring的一个典型应用场景是构造定长环回队列，比如网页上的轮播；heap的一个典型应用场景是构造优先级队列。
    共 1 条评论
    22
  • fliter
    2018-08-29
    为什么不把list像slice，map一样作为一种不需要import其他包就能使用的数据类型？是因为使用场景较后两者比较少吗

    作者回复: 这需要一个过程，之前list也不是标准库中的一员。况且也没必要把太多的东西多做到语言里，这样反倒不利于后面的扩展。

    共 2 条评论
    10
  • 云学
    2018-08-31
    在内存上，和ring的区别是list多了一个特殊表头节点，充当哨兵
    8
  • 会网络的老鼠
    2018-08-30
    现在大家写golang程序，一般用什么IDE？
    共 2 条评论
    8
  • 后端进阶
    2018-09-06
    前面的网友，goland了解一下，超赞的ide
    共 1 条评论
    7
  • Geek_a8be59
    2019-06-26
    您好 能否出一个list 链表生成的一个图解，现在我看源码用图去模拟生成 一直搞混掉，特别是在初始化的时候prev和next都指向自身的root 这个很迷糊 比如: c.PushBack("123") c.PushFront("456") c.PushFront("789") 根据个人图解应该是789-》456-》nil，为什么能遍历出来很不清楚。能否有一个从初始化到最后生成的样例看一下 万分感谢
    展开

    作者回复: 按照你这三行代码，应该是 789 -> 456 -> 123 啊，你那个“789-》456-》ni”是怎么出来的？ 这个链表里所谓的 root 就是用来表示链表两端的尽头的。所以，这个链表的末端实际上并不是 nil ，而是 root。只是在 Element 的 Next 方法中，如果发现它的 next 字段的值等于 root，就会返回 nil 而已。 明白了吗？

    共 2 条评论
    6
  • 李斌
    2018-10-30
    用 vscode 就蛮好的，我之前是八年 vim 党，写 golang 时硬生生地被掰成 vscode

    作者回复: 嗯，也算是与时俱进吧，未来有脑机接口了，也就用不着这些了。

    共 2 条评论
    5
  • Zer0
    2019-08-06
    不能把自己生成的Element传给List主要是因为Element的list成员是不开放的，我们不能操作，而在List上操作Element的时候是会判断Element的list成员是否是自己。是这样吗？

    作者回复: ✅

    4
  • 雷朝建
    2021-04-02
    老师， 我看了一下list.go的源码，发现一个疑问是：延迟初始化的含义就是调用lazyInit，它的一个判断条件是：l.root.next==nil； 但是我们在使用list时候，不是先调用New函数吗？那么不应该会出现l.root.next为nil的情况的。 什么时候回出现l.root.next==nil, 从而导致源码中每次的PushFront等操作调用lazyInit呢？

    作者回复: List 是一个 struct 啊，有了 lazyInit 你就可以直接 var myList list.List 了啊。这不是就做到开箱即用了吗？

    3
  • jackstraw
    2019-07-09
    我尝试打印了 “var l = list.New()” 与 “var l list.List”两种方式的l类型，发现是不一样的，但是下面的操作却都是可以的 func main() { //l := list.New() var l list.List e4 := l.PushBack(4) e1 := l.PushFront(1) l.InsertBefore(3, e4) l.InsertAfter(2, e1) //travel(l) travel(&l) }
    展开

    作者回复: 当然不一样，list.New 返回的是指针值。另外你可以再看看讲结构体和方法那篇文章。

    3
  • 杨震
    2020-08-25
    以后再有课的话 希望老师多加点图 虽然费点事 但应该更多为学员着想吧。文字阐述一点也不直观。

    作者回复: OK。

    2
  • Sky
    2019-06-12
    这一讲没有实例代码

    作者回复: 建议大家在阅读这一篇文章时对照着 container 包的文档看。对这几个类型的 API 有一定了解之后，使用就是水到渠成的事情了。 自己先试一试，如果有具体的问题，可以来这里问。

    2
  • lesserror
    2021-07-27
    对于这一讲的内容，确实要用IDE（例如Goland）打开源码文件一边阅读一边对着课中的文字，一边推敲、实验。 几个源码文件都是一两百来行，读起来不吃力。（前提是已经有了Go的基础）
    1
  • KK
    2020-07-19
    关于list的结构，画个图会更加直观
    1
  • lixiaofeng
    2019-12-20
    func flist(){ link := list.New() for i:=1; i< 11; i++ { link.PushBack(i) } for p:= link.Front(); p!=link.Back(); p=p.Next(){ fmt.Println("Number", p.Value) } } #链表的常用方法 func (e *Element) Next() *Element func (e *Element) Prev() *Element func (l *List) Init() *List New() *List { return new(List).Init() } func (l *List) Len() int { return l.len } func (l *List) Front() *Element func (l *List) Back() *Element func (l *List) Remove(e *Element) interface{} func (l *List) PushFront(v interface{}) *Element func (l *List) PushBack(v interface{}) *Element func (l *List) InsertBefore(v interface{}, mark *Element) *Element func (l *List) InsertAfter(v interface{}, mark *Element) *Element func (l *List) MoveToFront(e *Element) func (l *List) MoveToBack(e *Element) func (l *List) MoveBefore(e, mark *Element) func (l *List) MoveAfter(e, mark *Element) func (l *List) PushBackList(other *List) func (l *List) PushFrontList(other *List)
    展开
    1