golang标准库 —— container包

container包实现了三个复杂的数据结构:堆(heap),链表(list),环(ring)

链表-List

List结构体为链表本身,Element结构体是链表下的每一个元素。

Element

Element 结构体包含上一个元素和下一个元素的指针指向,所属List的指向,以及当前Element的值。

Element 提供了两个方法,获取上一个元素和下一个元素。

List

List本身包含了root Element主节点以及链表的长度。

创建一个List

创建List时,会进行初始化将root的上下节点都指向root本身。

回过头来我们会发现Element获取上下元素时会判断,下一个或者上一个元素是否root本身,如果是这回返回nil

List操作抽象

链表的操作我们都可以抽象为insertremove

insert,在指定节点插入某个节点。

  • 将上一个节点的next指向插入节点,将下一个节点的的prev指向插入节点
  • 将插入节点的next指向下一个节点,将插入节点的的prev指向上一个节点
  • 列表长度++, 插入节点指向list

remove, 操作起来就更简单了,直接将上下两个节点互指就可以了,然后放置内存泄漏清空删除节点的指向关系。

有了insertremove两个操作以后,我们可以扩展衍生到所有操作。在这里找几个比较典型的例子来说,

  • 移动至最前端:先将指定节点移除,然后将节点插入到root节点后

  • 移动至最后个节点:将节点移除,然后插入到root节点的上一个几点。

我们可以套用l.insert(l.remove(e), &Element{}),然后将节点移动到任意各节点去。

环-Ring

结构体Ring指的是环上的节点。相比于List它并没有元素与结构之分。Ring首位相连,形成一个环。

New

创建一个拥有10各节点的环。

Link & Unlink

Link将两个环相连,原理与链表的插入类似。

  • 将环A的尾与环B的头相连
  • 将环A的头与环B的尾相连

Unlink移除环中的某一段。

这里它的使用了一个技巧,先用Move方法获取第N+1个节点,然后将该节点传入Link方法,是第一个节点与第第N+1个节点相连,那么第2个节点到第N个节点就被删除了。

Do

循环ring操作。

堆-heap

heap下只有interface,并没有struct的实现,所以需要我们去实现。

heap.Interface嵌套了sort.Interface,所以我们一共需要实现5个方法,

我们自定义一个IntHeap,然后让其完成heap的一系列操作。

在定义好结构体,以及实现接口之后,我们对其进行操作,发现IntHeap自动实现了最小堆的功能。

为什么会这样呢?

主要因为heap中有两个函数up上浮和down下沉。

当我们操作heap的时候,会根据情况自动调用updown方法,完成最小堆的排序。

updown方法中,调用了我们实现的LessSwap方法取做相关操作。

参考:

  • https://books.studygolang.com/The-Golang-Standard-Library-by-Example/chapter03/03.3.html
  • https://ieevee.com/tech/2018/01/29/go-heap.html