Go

Container 3兄弟-List

Go有提供幾種 List、Heap、Ring
來依序玩看看

List

因為上篇講Array & Slice, 這兩種底層都需要連續的記憶體空間來配置.
List則是可以非連續空間的容器, 也可以支援快速增刪元素.
List由多個節點所組成的, 節點之間透過一些變數紀錄彼此的關係.
且List並沒有限制每個節點的元素類型. 所以可以是任意類型.
但後續轉換時就要注意.

List有多種實現方式 :

  • Single Linked List
  • Double Linked List : Go內建這個類型, 相較於single linked list, 在增刪元素時不需要移動元素, 可以原地增刪. 還能夠雙向走訪.

這是List 的source code, 可以看到有next, prev這兩個ptr, 指向前後各一個元素的位置.
呼叫Init()時, prev, next都指向root節點.

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
// Element is an element of a linked list.
type Element struct {
// Next and previous pointers in the doubly-linked list of elements.
// To simplify the implementation, internally a list l is implemented
// as a ring, such that &l.root is both the next element of the last
// list element (l.Back()) and the previous element of the first list
// element (l.Front()).
next, prev *Element

// The list to which this element belongs.
list *List

// The value stored with this element.
Value interface{}
}

// 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
}

// 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
}

// New returns an initialized list.
func New() *List { return new(List).Init() }

初始化List

1
2
3
4
5
// 透過New(), New會去呼叫Init()
變數名稱 := list.New()

// 透過聲明來初始化
var 變數名稱 list.List

插入新元素

PushFront、PushBack 可以在List的最前面或最後面增加元素.
PushFront 是對目前List的root節點前面在多一個元素; 看原始碼會發現呼叫了insertValue(), 第二個參數是root, 然後又呼叫了insert(&Element, root), 第一個參數是新增的元素, 第二個參數是該新增元素要插入在誰的後面, 這裡是安插在root後面.
PushBack 是對目前List的尾巴節點後面多一個元素.

InsertBefore、InsertAfter則是在被標記的元素前或後增加元素.

原始碼

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
// insert inserts e after at, increments l.len, and returns e.
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
}

// insertValue is a convenience wrapper for insert(&Element{Value: v}, at).
func (l *List) insertValue(v interface{}, at *Element) *Element {
return l.insert(&Element{Value: v}, at)
}

// PushFront inserts a new element e with value v at the front of list l and returns e.
func (l *List) PushFront(v interface{}) *Element {
l.lazyInit()
return l.insertValue(v, &l.root)
}

// PushBack inserts a new element e with value v at the back of list l and returns e.
func (l *List) PushBack(v interface{}) *Element {
l.lazyInit()
return l.insertValue(v, l.root.prev)
}

// InsertBefore inserts a new element e with value v immediately before mark and returns e.
// If mark is not an element of l, the list is not modified.
// The mark must not be nil.
func (l *List) InsertBefore(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.prev)
}

// InsertAfter inserts a new element e with value v immediately after mark and returns e.
// If mark is not an element of l, the list is not modified.
// The mark must not be nil.
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)
}
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
package main

import (
"container/list"
"fmt"
)

func traverse(list *list.List) {
// 走訪list
fmt.Printf("root -> ")
for el := list.Front(); el != nil; el = el.Next() {
fmt.Printf("%v -> ", el.Value)
}
}
func main() {
// 宣告一個List, 並且初始化
list := list.New()

// 最後面新增20
list.PushBack(20)

// 最前面新增10
list.PushFront("10")

// 最後面新增25, 並且保存該新增元素到變數上
element := list.PushBack(25)

// 在該元素後面新增26
list.InsertAfter("26", element)

// 在該元素前面新增26
list.InsertBefore(24, element)

traverse(list)

fmt.Println("\n---------------------")
// element 換到第一個元素的後面
list.MoveAfter(element, list.Front())
traverse(list)

fmt.Println("\n---------------------")
// element 換到第一個元素的前面
list.MoveBefore(element, list.Front())
traverse(list)

fmt.Println("\n---------------------")
// element 換到最後面
list.MoveToBack(element)
traverse(list)

fmt.Println("\n---------------------")
// element 換到最前面
list.MoveToFront(element)
traverse(list)

fmt.Println("\n---------------------")
// 移除該元素
list.Remove(element)
traverse(list)
}
/*
root -> 10 -> 20 -> 24 -> 25 -> 26 ->
---------------------
root -> 10 -> 25 -> 20 -> 24 -> 26 ->
---------------------
root -> 25 -> 10 -> 20 -> 24 -> 26 ->
---------------------
root -> 10 -> 20 -> 24 -> 26 -> 25 ->
---------------------
root -> 25 -> 10 -> 20 -> 24 -> 26 ->
---------------------
root -> 10 -> 20 -> 24 -> 26 ->
*/

走訪List

走訪List需要配合Front()取得第一個元素, 開始往下走訪.
每次就呼叫目前元素的Next(), 只要元素不是nil 就能繼續往下走.
也能逆向往前走, 改用Prev()就可.

取得List長度

1
list.Len()

List vs Slice

比較新增元素、插入元素、走訪的速度

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
package main

import (
"container/list"
"fmt"
"time"
)

func main() {
t := time.Now()
sli := make([]int, 10)
for i := 0; i < 1*100000*1000; i++ {
sli = append(sli, 1)
}
fmt.Println("Slice 新增元素耗費:" + time.Now().Sub(t).String())

// 比较走訪
t = time.Now()
for _ = range sli {
}
fmt.Println("走訪Slice耗費:" + time.Now().Sub(t).String())

// 比較插入元素
t = time.Now()
slif := sli[:100000*500]
slib := sli[100000*500:]
slif = append(slif, 10)
slif = append(slif, slib...)
fmt.Println("Slice 的插入元素耗費 : " + time.Now().Sub(t).String())

// 比較刪除元素
t = time.Now()
index := 100000
_ = append(sli[:index], sli[index+1:]...)
fmt.Println("Slice 的刪除元素耗費 : " + time.Now().Sub(t).String())

sli = make([]int, 10)

// ---------Slice end, start list
fmt.Println("------------------------------")

t = time.Now()
l := list.New()
for i := 0; i < 1*100000*1000; i++ {
l.PushBack(1)
}
fmt.Println("List 新增元素耗費: " + time.Now().Sub(t).String())

t = time.Now()
for e := l.Front(); e != nil; e = e.Next() {
}
fmt.Println("走訪List耗費:" + time.Now().Sub(t).String())

var em *list.Element
i := 0
// 找到1/3處的元素
for e := l.Front(); e != nil; e = e.Next() {
i++
if i == l.Len()/3 {
em = e
break
}
}
// 因為是記算插入元素的速度, 所以忽略查找的時間
t = time.Now()
l.InsertAfter(2, em)
fmt.Println("List 的插入元素耗費 : " + time.Now().Sub(t).String())

// 比較刪除元素
t = time.Now()
l.Remove(em)
fmt.Println("List 的刪除元素耗費:" + time.Now().Sub(t).String())

}
/*
Slice 新增元素耗費:1.749752738s
走訪Slice耗費:35.548381ms
Slice 的插入元素耗費 : 46.402953ms
Slice 的刪除元素耗費 : 92.097862ms
------------------------------
List 新增元素耗費: 17.721431965s
走訪List耗費:364.763942ms
List 的插入元素耗費 : 2.17µs
List 的刪除元素耗費:73ns
*/

結論

對於資料量很多的情境下,
如果很頻繁的插入或是刪除, List的成本低到幾乎可以不計算.
但如果頻繁的新增或是走訪查找, Slice的效能高過List許多.

首圖是參考該文章的, 該文有講單鏈, 雙鏈跟環鏈, 有機會再分享

鐵人賽連結

分享到