GO语言学习:container包中的list和ring

2018/12/05 11:21
阅读数 130

1.List

  container/list 包

  MoveBefore和MoveAfter分别用于把给定的元素移动到一个元素的前面和后面.

  MoveToFront和MoveToBack分别用于把给定的元素移动到链表的最前端和最后端.

  给定的元素都是*Element类型,*Element类型是Element的指针类型,*Element的值就是元素的指针.

  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)

  

  在List包含的方法中,用于新插入元素的那些方法只接受interface{} 类型的值,这些方法在内部会使用Element值,包装接收到的新元素.(避免直接使用我们自己生成的元素,避免链表内部关联遭到内部破坏)

  Front和Back分别用于获取链表最前端和最后端的元素.

  InsertBefore和InsertAfter分别用于在指定的元素之前和之后插入数据.

  PushFront和PushBack则是向链表最前端和最后端插入数据.

 

  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

  这些方法会把一个Element的值的指针作为结果返回,这就是链表留给我们的安全“接口”.

 

  List这个结构体有2个字段,一是Element类型的字段root,另一个是int类型的len,前者代表根元素,后者代表长度 ,包级私有.

  root和len都会被赋予相应的零值,len为0,root为Element{}.

 

  Element类型包含了几个包级私有的字段,分别用于存储前一个元素,后一个元素,以及所属链表的指针值,还有一个公开的名叫value的字段,用来存储该元素的实际值,他是interface{}类型,在Element类型中这些的零值都是nil.

2.Ring

  container/ring

  Ring是一个循环链表,也就是我们俗称的环

3.区别

  Ring的数据结构仅由他自己表示,而List类型则需要他自己和Element类型联合表示. 这是表示方式上的不同,也是数据结构上的不同.

  一个Ring的值只代表了其所属循环链表中的一环,而一个List的值则代表一个完整的链表.这是维度上的不同.

  创建并初始化一个Ring的值得时候,我们可以指定包含的元素的个数,但对于一个List来说却不能这样,循环链表一旦被创建,其长度不可变.

  var r ring.Ring  : r代表一个长度为1的循环链表,var l list.List  : l代表一个长度为0的链表, List中根元素不会持有任何实际元素值,因此计算长度的时候并不会计算它.

  Ring 值得len方法的算法复杂度是O(n),而List的len方法的算法复杂度是O(1).

  

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部