[回收站] Go语言源码阅读(4) - container/list | 链表

发表于 | 分类于
| 字数统计: 966

是双向链表。

实现上，有哨兵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并没有提供类似clear的方法，所以必须循环遍历删除。
这里有个坑，就是遍历时调用Remove删除自身Element时，自身Element的Next将被修改为nil，所以需要在调用Remove之前，把Next记录下来，才能继续访问下一个元素。

额外的开销

由于list是通过在应用层提供的item之外包装一层Element对象的方式实现的，所以即使你是同一个item不停的插入和删除list，依然会不停的new Element和删除Element，这点还是挺糟糕的。

List提供的对外接口有：

常规操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 初始化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类型的操作，对常规操作做的组合封装：

1
2
3
4
5
6
7
8
9
10
11
// 将某个元素移动到头部
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)

最后，还支持链表的拼接操作：

1
2
3
4
5
// 将<other>链表插入<l>链表之后
func (l *List) PushBackList(other *List)

// 插到前面
func (l *List) PushFrontList(other *List)

Element提供的接口：

1
2
3
4
5
6
7
8
// 可访问的数据成员，可强转成用户存入的类型
Value interface{}

// 前一个元素
func (e *Element) Prev() *Element

// 后一个元素
func (e *Element) Next() *Element

基于Go 1.11.4

本文完，作者yoko，尊重劳动人民成果，转载请注明原文出处： https://pengrl.com/p/51973/

0%