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).