container 中的容器

container包中有三个非常常用的数据结构（容器），分别是：list（双向链表）、ring（双向循环链表）、heap（堆）。我们简要了解一下前面两个容器。

list

• container/list 包中包含两个程序实体：List 和 Element，他们之间的关系一目了然。
• List 会将输入数据包装成一个 Element，并放在链中。
• 但是，List 只接受它自己生成的 Element，也就是说，你不能手动制造一个 Element 添加到 List 中。
• 链表有如下方法：

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)

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

• 链表之所以不能接受程序员手构造的元素，一部分原因是：每个元素都会保存它所属的链表的指针。
• 而之所以这么做，一方面是避免链表内部关联，遭到外界破坏。另一方面，它为链表的延迟初始化提供了方便。

延迟初始化

• 延迟初始化可以分散集中初始化操作带来的计算和空间消耗。
• 它的缺点在于：调用链表的时候，需要判断链表是否已经初始化，这是浪费。
• go 通过在 Element 中存储 root 的指针，可以方便地判断链表是否初始化。

ring

• Ring 类型是一个循环链表，其实 List 的内部也是一个循环链表。但是二者依然后很大不同。
• List 的根元素不会有元素值，它的存在是为了连接链表的首尾两端。

Ring 和 LIst 的不同

• Ring 不需要 Element 类型帮忙表示。
• 一个 Ring 代表了其所在的循环链表中的一个元素。
• Ring 初始化的时候可以指定元素的数量，List 则没有必要。
• var r ring.Ring 会声明一个长度为 1 的循环链表，如果是 List，则长度为 0。
• 求 len，Ring 的复杂度为 O(n)， List 的复杂度为O(1)。