Golang 的原生实现容器似乎不如 Java 的原生种类那么多，所以有些常见的容器可以直接使用 GoDS，目前原生实现的有堆、列表、环，下面逐一介绍。

也可以直接参考 容器数据类型：heap、list 和 ring

heap

标准库 heap 包中没有可以导出的已经实现好的堆，需要实现 heap.Interface 以得到我们自己的堆，以文件 container/heap/example_intheap_test.go 为例，看看最小堆是如何实现的

  1. // An IntHeap is a min-heap of ints.
  2. type IntHeap []int
  4. func (h IntHeap) Len() int           { return len(h) }
  5. func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
  6. func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
  8. func (h *IntHeap) Push(x interface{}) {
  9.     // Push and Pop use pointer receivers because they modify the slice's length,
  10.     // not just its contents.
  11.     *h = append(*h, x.(int))
  12. }
  14. func (h *IntHeap) Pop() interface{} {
  15.     old := *h
  16.     n := len(old)
  17.     x := old[n-1]
  18.     *h = old[0 : n-1]
  19.     return x
  20. }

前三个方法是 sort.Interface 的接口，后两个是堆独特的。不论最大堆还是最小堆，都是用数组保存的，同时需要比较与排序的功能。同时堆的接口定义的方法并不是由调用者直接调用的，使用入堆和出堆需要使用 heap.Push(h Interface, x interface{}) 和 heap.Pop(h Interface) interface{}

  1. // Note that Push and Pop in this interface are for package heap's
  2. // implementation to call. To add and remove things from the heap,
  3. // use heap.Push and heap.Pop.

那么实际上两个方法的实现是为了维护数组，我们查看上述最小堆的实现代码可以知道：压入加在数组最后，之后会调用 up(h Interface, j int) 上浮到堆的合适位置，弹出会把堆根的数与数组最后一个交换，然后数组长度减一，堆根的数调用 down(h Interface, i0, n int) 下沉到堆的合适位置。

list

注释直白地介绍了，list 包实现了一个双向链表，需要遍历链表就如下使用，也是非常的直观清晰。

  1. // Package list implements a doubly linked list.
  2. //
  3. // To create a new list
  4. l := list.New()
  5. // To iterate over a list (where l is a *List):
  6. for e := l.Front(); e != nil; e = e.Next() {
  7.     // do something with e.Value
  8. }

看一下这个双向链表是如何构造的，分为 Element 和 List，也就是构成链表的基本元素和链表本身（如果自己实现一个，也应该分为这两部分）

  • Element
    • 存放了前一个和后一个元素的指针，因为这是一个双向链表
    • 当前元素所属的具体链表（可能考虑到不同链表会使用含有同样值的元素）
    • 具体的值，使用 interface{} 接口表明可以存储任何值

  • List

    • 链表的根节点

    • 除去根节点的链表总长度 ```go // 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{} }

// 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 }

  1. 对外暴露可用方法，功能就不一一列出了，看名称与注释可得。
  3. | 方法名 | 返回值 |
  4. | --- | --- |
  5. | Init() | *List |
  6. | Len() | int |
  7. | Front() | *Element |
  8. | Back() | *Element |
  9. | Remove(e *Element) | interface{} |
  10. | PushFront(v interface{}) | *Element |
  11. | PushBack(v interface{}) | *Element |
  12. | InsertBefore(v interface{}, mark *Element) | *Element |
  13. | InsertAfter(v interface{}, mark *Element) | *Element |
  14. | MoveToFront(e *Element) | / |
  15. | MoveToBack(e *Element) | / |
  16. | MoveBefore(e, mark *Element) | / |
  17. | MoveAfter(e, mark *Element) | / |
  18. | PushBackList(other *List) | / |
  19. | PushFrontList(other *List) | / |
  21. <a name="7TSEz"></a>
  22. ## ring
  23. 与双向链表的区别为环的每个元素都代表环自身，没有头和尾之分，所以只需要维护一个结构即可。
  24. ```go
  25. // A Ring is an element of a circular list, or ring.
  26. // Rings do not have a beginning or end; a pointer to any ring element
  27. // serves as reference to the entire ring. Empty rings are represented
  28. // as nil Ring pointers. The zero value for a Ring is a one-element
  29. // ring with a nil Value.
  30. //
  31. type Ring struct {
  32.     next, prev *Ring
  33.     Value      interface{} // for use by client; untouched by this library
  34. }