golang container包List和Ring

one_zheng · · 527 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

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的典型应用场景是构造定长环回队列,比如网页上的轮播;

本文来自:简书

感谢作者:one_zheng

查看原文:golang container包List和Ring

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:muxilin131420 备注:入群;或加QQ群:977810755

527 次点击  
加入收藏 微博
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传