49
Go语言源码阅读(4) - container/list | 链表
source link: https://www.tuicool.com/articles/BzYrArF
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
是双向链表。
实现上，有哨兵 root
节点，即当链表为空时，还有一个哨兵元素。
实现多态的方式是 Element
结构体内有一个 interface{}
数据成员，可以用来存储任意类型的数据。其余链表和链表元素的代码都是系统库提供的。
container/list/example_test.go
演示了如何申请一个List，并对它进行一些插入操作后，如何遍历访问该List。
有一点非常值得思考，就是Go语言没有构造函数，从而导致的一些问题。
当一个结构体变量在使用前需要对它的数据成员做一些非zero out的初始化时（Go语言会对所有数据成员做zero out），
要么是提供一个New接口，接口返回一个结构体的指针类型，内部实现是实例化结构体变量后，然后做Init操作。但是从语意上来讲，这种变量是分配在堆上的。
要么是提供一个Init接口，坏处是要么用户在栈上声明了结构体变量时，还需要手动调用Init函数，增加了使用时成本。要么是在其他的方法内部做lazy init，这又增加了结构体的实现复杂度，以及小小的性能（毕竟lazy init每次都要判断是否已经init了）。
List
提供的对外接口有：
常规操作：
// 初始化List，这个接口并不是在使用List前非调用不可的，因为部分List的操作会在操作前判断List是否已经Init并做懒初始化
// 如果先清空一个List，也可以对List调用Init方法
func (l *List) Init() *List
// 返回一个*List变量
func New() *List
// 获取List的长度
// List中会持续记录更新数据成员len，所以获取长度的复杂度是`O(1)`的。
func (l *List) Len() int
// 获取头部元素
func (l *List) Front() *Element
// 获取尾部元素
func (l *List) Back() *Element
// 头部插入
func (l *List) PushFront(v interface{}) *Element
// 尾部插入
func (l *List) PushBack(v interface{}) *Element
// 某个元素前插入
func (l *List) InsertBefore(v interface{}, mark *Element) *Element
// 某个元素后插入
func (l *List) InsertAfter(v interface{}, mark *Element) *Element
// 删除某个元素
func (l *List) Remove(e *Element) interface{}
wrap类型的操作，对常规操作做的组合封装：
// 将某个元素移动到头部 func (l *List) MoveToFront(e *Element) // 将某个元素移动到尾部 func (l *List) MoveToBack(e *Element) // 将某个元素<e>移动到另一个元素<mark>的前面，注意，只是移动e，不移动mark func (l *List) MoveBefore(e, mark *Element) // 将某个元素移动到另一个元素的后面 func (l *List) MoveAfter(e, mark *Element)
最后，还支持链表的拼接操作：
// 将<other>链表插入<l>链表之后 func (l *List) PushBackList(other *List) // 插到前面 func (l *List) PushFrontList(other *List)
Element提供的接口：
// 可访问的数据成员，可强转成用户存入的类型
Value interface{}
// 前一个元素
func (e *Element) Prev() *Element
// 后一个元素
func (e *Element) Next() *Element
基于 Go 1.11.4
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK