go源码解读-list

发表于 | 分类于 ，

list

  • go语言中的列表采用双向链表来实现
  • 实现过程中主要依赖于两个结构体，Element和List对象
  • 显然list是线程不安全的包

Element详解

  • Element中包含四个字段，类似于Java中的成员变量
    • next为当前元素的下一个元素
    • pre为当前元素的上一个元素
    • &l.root为链表最后一个元素的下一个元素，同时也是链表第一个元素的上个元素，形如一个环
    • list标识当前元素归属于哪个链表
    • Value采用interface{}类型，可以保存任意的数据结构，也就是说go中的链表可以保存一个类似[‘abc’,12,12.03]这样的数据
1
2
3
4
5
6
7
8
// Element is an element of a linked list.
type Element struct {
	next, prev *Element
  list *List
	Value interface{}
}
  • Element结构体实现了两个方法
    • Next()方法返回当前节点的下一个节点数据
    • Prev()方法返回当前节点的上一个节点数据
    • 两个方法都屏蔽掉了list.root的情况，也就是如果找到的节点是根节点，则不做返回
1
2
3
4
5
6
7
8
9
10
11
12
13
func (e *Element) Next() *Element {
	if p := e.next; e.list != nil && p != &e.list.root {
		return p
	}
	return nil
}
func (e *Element) Prev() *Element {
	if p := e.prev; e.list != nil && p != &e.list.root {
		return p
	}
	return nil
}

List

  • 链表包含两个元素
    • root 根节点，只用在&root, root.prev, root.next这三种情况
    • len 链表中的节点数量，不包含根节点
1
2
3
4
5
6
// List represents a doubly linked list.
// The zero value for List is an empty list ready to use.
type List struct {
	root Element // sentinel list element, only &root, root.prev, and root.next are used
	len  int     // current list length excluding (this) sentinel element
}

初始化列表

  • list提供一个可外部调用的初始化方法New,实际上是调用了List的Init()方法
  • Init方法返回一个空列表，也就是root的前后节点都指向自己，并且列表长度为0
1
2
3
4
5
6
7
8
9
10
// New returns an initialized list.
func New() *List { return new(List).Init() }
// Init initializes or clears list l.
func (l *List) Init() *List {
	l.root.next = &l.root
	l.root.prev = &l.root
	l.len = 0
	return l
}

Len, Front, Back方法

  • Len返回list中的元素数量，获取复杂度O(1)
  • Front方法返回列表第一个元素，也就是l.root.next
  • Back方法返回列表最后一个元素，也就是l.root.prev
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func (l *List) Len() int { return l.len }
func (l *List) Front() *Element {
	if l.len == 0 {
		return nil
	}
	return l.root.next
}
func (l *List) Back() *Element {
	if l.len == 0 {
		return nil
	}
	return l.root.prev
}

Remove方法

  • Remove方法移除列表中指定元素，这个地方会对e.list做校验，如果不符合则不会进入remove方法
  • remove方法完成移除元素e的操作，将e.next和e.prev设置为nil，防止内存泄露
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func (l *List) Remove(e *Element) interface{} {
	if e.list == l {
		// if e.list == l, l must have been initialized when e was inserted
		// in l or l == nil (e is a zero Element) and l.remove will crash
		l.remove(e)
	}
	return e.Value
}
// remove removes e from its list, decrements l.len, and returns e.
func (l *List) remove(e *Element) *Element {
	e.prev.next = e.next
	e.next.prev = e.prev
	e.next = nil // avoid memory leaks
	e.prev = nil // avoid memory leaks
	e.list = nil
	l.len--
	return e
}

插入操作

  • lazyInit方法，懒加载，延迟初始化一个空链表
  • insertValue方法是对insert的一层封装
  • insert方法将节点e插入到节点at后面
  • PushFront 将节点插入到root节点之后
  • PushBach 将节点插入到root.prev之后
  • InsertBefore 将节点插入到mark节点之前
  • InsertAfter 将节点插入到mark节点之后
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
func (l *List) PushFront(v interface{}) *Element {
	l.lazyInit()
	return l.insertValue(v, &l.root)
}
func (l *List) PushBack(v interface{}) *Element {
	l.lazyInit()
	return l.insertValue(v, l.root.prev)
}
func (l *List) InsertBefore(v interface{}, mark *Element) *Element {
	if mark.list != l {
		return nil
	}
	return l.insertValue(v, mark.prev)
}
func (l *List) InsertAfter(v interface{}, mark *Element) *Element {
	if mark.list != l {
		return nil
	}
	// see comment in List.Remove about initialization of l
	return l.insertValue(v, mark)
}
func (l *List) lazyInit() {
	if l.root.next == nil {
		l.Init()
	}
}
func (l *List) Init() *List {
	l.root.next = &l.root
	l.root.prev = &l.root
	l.len = 0
	return l
}
func (l *List) insertValue(v interface{}, at *Element) *Element {
	return l.insert(&Element{Value: v}, at)
}
func (l *List) insert(e, at *Element) *Element {
	n := at.next
	at.next = e
	e.prev = at
	e.next = n
	n.prev = e
	e.list = l
	l.len++
	return e
}

移动节点操作

  • move为节点移动的核心方法，将节点e移动到节点at后面
  • MoveToFront将节点e移动到root节点之后
  • MoveToBack将节点e移动到root.prev节点之后
  • MoveBefore将节点移动到mark节点之前,这个地方如果e.next == mark的时候是不需要移动的
  • MoveAfter将节点移动到mark节点之后,这个地方如果mark.next == e 也是不需要移动的
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
func (l *List) MoveToFront(e *Element) {
	if e.list != l || l.root.next == e {
		return
	}
	// see comment in List.Remove about initialization of l
	l.move(e, &l.root)
}
func (l *List) MoveToBack(e *Element) {
	if e.list != l || l.root.prev == e {
		return
	}
	// see comment in List.Remove about initialization of l
	l.move(e, l.root.prev)
}
func (l *List) MoveBefore(e, mark *Element) {
	if e.list != l || e == mark || mark.list != l {
		return
	}
	l.move(e, mark.prev)
}
func (l *List) MoveAfter(e, mark *Element) {
	if e.list != l || e == mark || mark.list != l {
		return
	}
	l.move(e, mark)
}
// move moves e to next to at and returns e.
func (l *List) move(e, at *Element) *Element {
	if e == at {
		return e
	}
	e.prev.next = e.next
	e.next.prev = e.prev
	n := at.next
	at.next = e
	e.prev = at
	e.next = n
	n.prev = e
	return e
}

列表方法

  • PushBackList方法将other列表插入到l列表root.prev之后
  • PushFrontList方法将other列表插入到l列表root节点之后
1
2
3
4
5
6
7
8
9
10
11
12
13
func (l *List) PushBackList(other *List) {
	l.lazyInit()
	for i, e := other.Len(), other.Front(); i > 0; i, e = i-1, e.Next() {
		l.insertValue(e.Value, l.root.prev)
	}
}
func (l *List) PushFrontList(other *List) {
	l.lazyInit()
	for i, e := other.Len(), other.Back(); i > 0; i, e = i-1, e.Prev() {
		l.insertValue(e.Value, &l.root)
	}
}
Donate comment here