golang container包List和Ring

container/list

 这个包包含了两个公开的程序实体：List和Element。前者实现了一个双向链表（以下简称链表），而后者则代表了链表中元素的结构。

//这是一个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 *List

    // The value stored with this element.
    //存储的值，使用interface来代替泛型
    Value interface{}
}
//返回list的下一个元素
func (e *Element) Next() *Element{}
//返回list的上一个元素
func (e *Element) Prev() *Element{}

//list结构
type List struct {
//根元素，就是头节点，头节点的next，prev指向当前的元素
    root Element // sentinel list element, only &root, root.prev, and root.next are used
    len  int     // current list length excluding (this) sentinel element
}

list中的方法
// insert inserts e after at, increments l.len, and returns e.
//插入e元素再at元素之后，就是指定插入
func (l *List) insert(e, at *Element) *Element{}

// insertValue is a convenience wrapper for insert(&Element{Value: v}, at).
//插入一个值到at元素中
func (l *List) insertValue(v interface{}, at *Element) *Element{}

// remove removes e from its list, decrements l.len, and returns e.
//删除list中的e元素
func (l *List) remove(e *Element) *Element{}
// PushFront inserts a new element e with value v at the front of list l and returns e.
//插入一个元素在root的头
func (l *List) PushFront(v interface{}) *Element{}
//// PushBack inserts a new element e with value v at the back of list l and returns e.
//插入一个元素在list的末尾
func (l *List) PushBack(v interface{}) *Element{}

// InsertBefore inserts a new element e with value v immediately before mark and returns e.
// If mark is not an element of l, the list is not modified.
//插入一个新元素的值为v在mark之前并返回这个元素，若这个元素不是当前的list
func (l *List) InsertBefore(v interface{}, mark *Element) *Element{}
// InsertAfter inserts a new element e with value v immediately after mark and returns e.
// If mark is not an element of l, the list is not modified.
//插入一个元素，值为v，在mark的后面，并返回这个元素，如果mark不是当前list的元素，则list时不能修改的
func (l *List) InsertAfter(v interface{}, mark *Element) *Element{}

注意:语句var l list.List会是一个长度为0的链表。这个链表持有的根元素root也是一个空壳，其中只会包含缺省的内容。但这样的链表我们可以直接拿来使用，这被称为 开箱即用 。

其实单凭一个l是无法正常运行的，但关键不在这里，而在于它的 延迟初始化 机制。所谓的延迟初始化，你可以理解为把初始化操作延后，仅在需要的时候才运行。延迟初始化的优点在于 延后 ，它可以分散初始化操作带来的计算量和存储空间消耗。

container/ring

 ring包实现的是一个循环链表，也就是我们俗称的环。

// A Ring is an element of a circular list, or ring.
// Rings do not have a beginning or end; a pointer to any ring element
// serves as reference to the entire ring. Empty rings are represented
// as nil Ring pointers. The zero value for a Ring is a one-element
// ring with a nil Value.
//
//环形链表的数据结构时一个环形list的元素或者圆环，
//一个圆环链表是一个圆形list或者圆的元素，没有开始和结束，
type Ring struct {
    next, prev *Ring
    Value      interface{} // for use by client; untouched by this library
}

// Next returns the next ring element. r must not be empty.
//返回圆环的下一个元素，圆环必须不为空
func (r *Ring) Next() *Ring{}
// Prev returns the previous ring element. r must not be empty.
//返回这个圆环的上一个元素
func (r *Ring) Prev() *Ring{}
//当n<0时，反向移动元素，n>0时，正向移动元素
func (r *Ring) Move(n int) *Ring{}
//New creates a ring of n elements.
//新创建n个集合的圆环
func New(n int) *Ring{}
//统计 圆环长度
func (r *Ring) Len() int{}
//Link连接r和s，并返回r原本的后继元素r.Next()。r不能为空。如果r和s指向同一个环形链表，则会删除掉r和s之间的元素，删掉的元素构成一个子链表，返回指向该子链表的指针（r的原后继元素）；如果没有删除元素，则仍然返回r的原后继元素，而不是nil。如果r和s指向不同的链表，将创建一个单独的链表，将s指向的链表插入r后面，返回s原最后一个元素后面的元素（即r的原后继元素）。
func (r *Ring) Link(s *Ring) *Ring{}
//删除链表中n % r.Len()个元素，从r.Next()开始删除。如果n % r.Len() == 0，不修改r。返回删除的元素构成的链表，r不能为空。
func (r *Ring) Unlink(n int) *Ring {}
//对链表中任意元素执行f操作，如果f改变了r，则该操作造成的后果是不可预期的。
func (r *Ring) Do(f func(interface{}))

使用场景：

1.list的典型应用场景是构造FIFO队列；

2.ring的典型应用场景是构造定长环回队列，比如网页上的轮播；