CRCMS

高山仰止,景行行止,虽不能至,心向往之

大道至简


单向链表优化

说明

Golang 单向链表 中是通过不断修改next来实现链表
本章通过一个虚拟head方法来优化链表,其原理就是,创建时直接创建headnext,head第一个值始终是nil
通过headnext来作为初始值,并且对原有链表进行相关优化

实现代码

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
type node struct {
value interface{}
next *node
}

type LinkedList struct {
dummyHead *node
length int
}

func newNode(value interface{}, next *node) *node {
return &node{
value: value,
next: next,
}
}

func NewLinkedList() *LinkedList {
return &LinkedList{
// 一个虚拟的head value,只使用next
dummyHead: newNode(nil, newNode(nil, nil)),
length: 0,
}
}

// 添加元素
func (l *LinkedList) Add(index int, value interface{}) {
l.checkIndexRange(index)

//移动指针到指定下标
prev := l.dummyHead
for i := 0; i < index; i++ {
// 不断的移动链表指针
// dummyHead 有个虚拟value,其实是从dummyHead的next作为第一个值
prev = prev.next
}

// 每当数据更改时,自动修改其head,移动head头指针(往前增加),而不是直接修改next(不是往后增加)
prev.next = newNode(value, prev.next)
l.length ++
}

// 删除元素
func (l *LinkedList) Delete(index int) interface{} {
l.checkIndexRange(index)

prev := l.dummyHead
var current *node
for i := 0; i <= index; i++ {
// 保存当前值
// dummyHead 有个虚拟value,其实是从dummyHead的next作为第一个值
current = prev.next

// 需要删除的值
if i == index {
if current.next != nil {
// 移除指定索引,移动指针
// 当前值的next就等于当前的next,这样就移除了current
prev.next = current.next
} else {
prev.next = nil
}
} else {
prev = current
}
}

l.length --

return current.value
}

// 通过指定索引获取值
func (l *LinkedList) Index(index int) interface{} {
l.checkIndexRange(index)

prev := l.dummyHead
for i := 0; i <= index; i++ {
prev = prev.next
}

return prev.value
}

// 在链表开头插入值
func (l *LinkedList) Unshift(value interface{}) {
l.Add(0, value)
}

// 在链表结尾插入值
func (l *LinkedList) Push(value interface{}) {
l.Add(l.length, value)
}

// 弹出链表最后一个值
func (l *LinkedList) Pop() interface{} {
return l.Delete(l.length - 1)
}

// 弹出链表第一个值
func (l *LinkedList) Shift() interface{} {
return l.Delete(0)
}

//
func (l *LinkedList) Length() int {
return l.length
}

func (l *LinkedList) checkIndexRange(index int) {
if index < 0 || index > l.length {
panic(`下标越界`)
}
}

测试

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 TestNewLinkedList(t *testing.T) {
list := NewLinkedList()
list.Add(0,"a")
list.Push("b")
list.Add(2,"c")
list.Add(3,"d")

assert.Equal(t,"a",list.Index(0).(string))
assert.Equal(t,"b",list.Index(1).(string))
assert.Equal(t,"c",list.Index(2).(string))
assert.Equal(t,"d",list.Index(3).(string))

// 中间追加
list.Add(2,"e")

assert.Equal(t,"e",list.Index(2).(string))
assert.Equal(t,"c",list.Index(3).(string))
assert.Equal(t,"d",list.Index(4).(string))
assert.Equal(t,5,list.Length())

assert.Equal(t,"a",list.Index(0).(string))
assert.Equal(t,"b",list.Index(1).(string))
assert.Equal(t,"e",list.Index(2).(string))
assert.Equal(t,"c",list.Index(3).(string))
assert.Equal(t,"d",list.Index(4).(string))


assert.Equal(t,"e",list.Delete(2))
assert.Equal(t,4,list.Length())

assert.Equal(t,"a",list.Index(0).(string))
assert.Equal(t,"b",list.Index(1).(string))
assert.Equal(t,"c",list.Index(2).(string))
assert.Equal(t,"d",list.Index(3).(string))

assert.Equal(t,"d",list.Pop())
assert.Equal(t,3,list.Length())
assert.Equal(t,"a",list.Index(0).(string))
assert.Equal(t,"b",list.Index(1).(string))
assert.Equal(t,"c",list.Index(2).(string))

assert.Equal(t,"a",list.Shift())
assert.Equal(t,2,list.Length())
assert.Equal(t,"b",list.Index(0).(string))
assert.Equal(t,"c",list.Index(1).(string))
}