golang算法练习:单链表/双链表/环形链表

发表于 | 阅读次数：
本文字数： 12k | 阅读时长 ≈ 11 分钟

##

需求

链表，常见且非常灵活的数据模型，可定制性强，可根据需求调整满足不同的使用需求，如FIFO\LIFO，快速查找等，这里分别列举基础的单向链表和双向链表增删改查操作
备注：需求和运行输出结果均已在代码中注释

单向链表

代码

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
package main

import (
	"errors"
	"fmt"
)

type Node struct {
	id   int
	name string
	next *Node
}

type SingleLink struct {
	head *Node
}

func (singleLink *SingleLink) orderInsert(node *Node) {
	// 按Node.id从小到大的顺序，插入链表中
	curNode := singleLink.head
	if curNode.id == 0 {
		// 第一次插入元素的空链表
		singleLink.head = node
	} else {
		// 如果node.id比队首id小，则队首让位后移，要保证队首最小。因为取值比较的时候， 是取curNode.next节点与node进行比较，如果满足大小顺序，
		// 则将node插入curNode和curNode.next之间
		if curNode.id > node.id {
			node.next = curNode
			singleLink.head = node
		} else {
			// 如果node.id不比队首id小，则往后取一位，用后一位与node比较，匹配则插入当前位与后一位中间
			for {
				if curNode.next == nil {
					// 循环到最后一位都没有插入成功，说明node.id比现有链表中的所有node的id都大，则node成为新的队尾
					curNode.next = node
					break
				}
				if curNode.next.id > node.id {
					node.next = curNode.next
					curNode.next = node
					break
				}
				curNode = curNode.next
			}
		}
	}
}

func (singleLink *SingleLink) pop(id int) (node *Node, err error) {
	// 弹出链表中指定id的node
	curNode := singleLink.head
	if curNode.id == id {
		// 要取的是队首
		singleLink.head = singleLink.head.next
		return curNode, nil
	}
	flag := false // 是否查找到的标志
	for {
		if curNode.next == nil {
			break
		}
		if curNode.next.id == id {
			flag = true
			selectNode := curNode.next
			curNode.next = curNode.next.next
			return selectNode, nil
		}
		curNode = curNode.next
	}
	if !flag {
		// 如果循环结束还没有查找到，输出信息
		return nil, errors.New("node not found")
	}
	return
}

func (singleLink *SingleLink) getLength() (number int) {
	curNode := singleLink.head
	if singleLink.head.id == 0 || singleLink.head == nil {
		// 空链表
		return
	} else {
		for {
			number += 1
			curNode = curNode.next
			if curNode == nil {
				break
			}
		}
	}
	fmt.Println("current link length:", number)
	return number
}

func (singleLink *SingleLink) list() {
	if singleLink.head == nil || singleLink.head.id == 0 {
		fmt.Println("link is empty")
	} else {
		curNode := singleLink.head
		for {
			if curNode == nil {
				break
			}
			fmt.Print(*curNode, "==>")
			curNode = curNode.next
		}
	}
	fmt.Println()

}

func main() {
	// 约定空链表的header初始id为0，后面加入的实例id必须大于0
	var originalHead = Node{
		id: 0,
	}
	var s = SingleLink{
		head: &originalHead,
	}
	var node1 = Node{
		id:   1,
		name: "001",
	}
	var node2 = Node{
		id:   2,
		name: "002",
	}
	var node3 = Node{
		id:   3,
		name: "003",
	}
	var node4 = Node{
		id:   4,
		name: "004",
	}
	var node5 = Node{
		id:   5,
		name: "005",
	}

	s.orderInsert(&node4)
	s.list()
	s.orderInsert(&node2)
	s.list()
	s.orderInsert(&node3)
	s.list()
	s.orderInsert(&node5)
	s.list()
	s.orderInsert(&node1)
	s.list()
	s.getLength()
	popNode, err := s.pop(3)
	if err != nil {
		fmt.Println(err)
	}
	fmt.Println("pop node successfully:", *popNode)
	s.list()

	/*
		output:
			{4 004 <nil>}==>
			{2 002 0xc00000a0e0}==>{4 004 <nil>}==>
			{2 002 0xc00000a0c0}==>{3 003 0xc00000a0e0}==>{4 004 <nil>}==>
			{2 002 0xc00000a0c0}==>{3 003 0xc00000a0e0}==>{4 004 0xc00000a100}==>{5 005 <nil>}==>
			{1 001 0xc00000a0a0}==>{2 002 0xc00000a0c0}==>{3 003 0xc00000a0e0}==>{4 004 0xc00000a100}==>{5 005 <nil>}==>
			current link length: 5
			pop node successfully: {3 003 0xc00000a0e0}
			{1 001 0xc00000a0a0}==>{2 002 0xc00000a0e0}==>{4 004 0xc00000a100}==>{5 005 <nil>}==>
	*/
}

问题
单向链表的操作必须从首部开始，那么可不可以灵活一些，比如从尾部开始呢？当然可以，改造成双向链表即可满足

双向链表

代码：
为了以示区别，增删改查全部改为从尾部开始循环

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
package main

import (
	"errors"
	"fmt"
)

type Node struct {
	id   int
	name string
	next *Node
	prev *Node
}

type CircleLink struct {
	head *Node
	tail *Node
}

func (circleLink *CircleLink) orderInsert(node *Node) {
	// 按Node.id从小到大的顺序，插入链表中
	curNode := circleLink.head
	if curNode.id == 0 {
		// 第一次插入元素的空链表
		circleLink.head = node
		circleLink.tail = node
	} else {
		// 如果node.id比队首id小，则队首让位后移，要保证队首最小。因为取值比较的时候， 是取curNode.next节点与node进行比较，如果满足大小顺序，
		// 则将node插入curNode和curNode.next之间
		if curNode.id > node.id {
			node.next = curNode
			curNode.prev = node
			circleLink.head = node
		} else {
			// 如果node.id不比队首id小，则往后取一位，用后一位与node比较，匹配则插入当前位与后一位中间
			for {
				if curNode.next == nil {
					// 循环到最后一位都没有插入成功，说明node.id比现有链表中的所有node的id都大，则node成为新的队尾
					curNode.next = node
					node.prev = curNode
					circleLink.tail = node
					break
				}
				if curNode.next.id > node.id {
					node.next = curNode.next
					node.prev = curNode
					curNode.next.prev = node
					curNode.next = node
					break
				}
				curNode = curNode.next
			}
		}
	}
}

func (circleLink *CircleLink) pop(id int) (node *Node, err error) {
	// 弹出链表中指定id的node.这次从链表尾部往首部循环
	curNode := circleLink.tail
	if curNode.id == id {
		// 要取的是队尾
		circleLink.tail = circleLink.tail.prev
		return curNode, nil
	}
	flag := false // 是否查找到的标志
	for {
		if curNode.prev == nil {
			// 已经从队尾达到队首,全部都没命中
			break
		}
		if curNode.id == id {
			flag = true
			selectNode := curNode
			if curNode == circleLink.head {
				// 如果命中的节点正好是队首
				if circleLink.head.next != nil {
					// 如果队首后面还有节点，则第二个节点置为新的首节点，且第二个节点的prev指向置为nil，这样原head没有被引用，内存会释放出来
					circleLink.head.next.prev = nil
					circleLink.head = circleLink.head.next
				} else {
					// 如果队首之后没有节点了，那么直接首位都置空
					circleLink.head = nil
					circleLink.tail = nil
				}
			} else {
				// 命中的节点在队中间,则取出命中的节点，并维护好其前后指向关系
				curNode.prev.next = curNode.next
				curNode.next.prev = curNode.prev
			}
			return selectNode, nil
		}
		curNode = curNode.prev
	}
	if !flag {
		// 如果循环结束还没有查找到，输出信息
		return nil, errors.New("node not found")
	}
	return
}

func (circleLink *CircleLink) getLength() (number int) {
	curNode := circleLink.tail
	if circleLink.tail.id == 0 || circleLink.tail == nil {
		// 空链表
		return
	} else {
		for {
			number += 1
			curNode = curNode.prev
			if curNode == nil {
				break
			}
		}
	}
	fmt.Println("current link length:", number)
	return number
}

func (circleLink *CircleLink) list() {
	if circleLink.tail == nil || circleLink.tail.id == 0 {
		fmt.Println("link is empty")
	} else {
		curNode := circleLink.tail
		var nodes []*Node
		for {
			if curNode == nil {
				break
			}
			//fmt.Print("<==", *curNode)
			// 从尾部到首部的循环，为了展示链接效果，将节点先加入一个slice中，稍后从slice的后面开始循环展示数据.此时slice是从尾部到首部排序的
			nodes = append(nodes, curNode)
			curNode = curNode.prev
		}
		for i := 0; i < len(nodes); i++ {
			index := len(nodes) - i - 1 // 颠倒一下顺序，现在slice中的顺序和链表顺序恰好是相反的，为了打印的效果，让前面的节点先输出
			fmt.Print("<==>", nodes[index])
		}
	}

	fmt.Println()

}

func main() {
	// 约定空链表的header初始id为0，后面加入的实例id必须大于0
	var originalHead = Node{
		id: 0,
	}
	var s = CircleLink{
		head: &originalHead,
	}
	var node1 = Node{
		id:   1,
		name: "001",
	}
	var node2 = Node{
		id:   2,
		name: "002",
	}
	var node3 = Node{
		id:   3,
		name: "003",
	}
	var node4 = Node{
		id:   4,
		name: "004",
	}
	var node5 = Node{
		id:   5,
		name: "005",
	}

	s.orderInsert(&node4)
	s.list()
	s.orderInsert(&node2)
	s.list()
	s.orderInsert(&node3)
	s.list()
	s.orderInsert(&node5)
	s.list()
	s.orderInsert(&node1)
	s.list()
	s.getLength()
	popNode, err := s.pop(3)
	if err != nil {
		fmt.Println(err)
	}
	fmt.Println("pop node successfully:", *popNode)
	s.list()

	/*
		output:
			<==&{4 004 <nil> <nil>}
			<==&{2 002 0xc0000761e0 <nil>}<==&{4 004 <nil> 0xc000076180}
			<==&{2 002 0xc0000761b0 <nil>}<==&{3 003 0xc0000761e0 0xc000076180}<==&{4 004 <nil> 0xc0000761b0}
			<==&{2 002 0xc0000761b0 <nil>}<==&{3 003 0xc0000761e0 0xc000076180}<==&{4 004 0xc000076210 0xc0000761b0}<==&{5 005 <nil> 0xc0000761e0}
			<==&{1 001 0xc000076180 <nil>}<==&{2 002 0xc0000761b0 0xc000076150}<==&{3 003 0xc0000761e0 0xc000076180}<==&{4 004 0xc000076210 0xc0000761b0}<==&{5 005 <nil> 0xc0000761e0}
			current link length: 5
			pop node successfully: {3 003 0xc0000761e0 0xc000076180}
			<==&{1 001 0xc000076180 <nil>}<==&{2 002 0xc0000761e0 0xc000076150}<==&{4 004 0xc000076210 0xc000076180}<==&{5 005 <nil> 0xc0000761e0}
	*/
}

问题
从尾部开始查询的操作复杂度依旧与首部开始一样，为O(n)，有没有办法降低复杂度？当然可以，按照自定义链节点串联规则，完全可以使用二分等其他查找的方法降低复杂度，这个后面再补充

环形链表

直接以约瑟夫问题，又称丢手帕游戏举例，此场景非常适用于使用环形链表模型，游戏规则见代码顶部注释
代码：

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
package main

import (
	"fmt"
	"math/rand"
)

/*
约瑟夫问题，又叫丢手帕游戏，若干人围成一圈，从头开始，每次递进若干位随机数，然后出列一人，接着再从出列者的下一位开始继续循环，
直到圈内只剩最后一人,游戏结束
*/

type Child struct {
	Id   int
	next *Child
}

type Ring struct {
	Head *Child
	Tail *Child
}

func (ring *Ring) list() {
	curChild := ring.Head
	for {
		fmt.Printf("child %d ==>\t", curChild.Id)
		if curChild.next == ring.Head {
			break
		}
		curChild = curChild.next
	}
	fmt.Println()
}

func (ring *Ring) play() {
	// 开始转圈,第一次是从头开始
	startIndex := 1
	n := 0
	startChild := ring.Head
	for {
		if startChild.next == startChild {
			fmt.Printf("游戏结束，圈圈中的最后一位child是%d号\n", startChild.Id)
			break
		}
		n += 1
		randInt := rand.Intn(10)
		curChild := startChild
		for i := 0; i < randInt-1; i++ {
			// 在出列child的前一位停下，因为是链表关系，所以需要维护好出列child的前一位的指向关系
			curChild = curChild.next
		}
		chooseChild := curChild.next
		if chooseChild == ring.Head {
			ring.Head = chooseChild.next
		}
		curChild.next = chooseChild.next // chooseChild的指针取消，chooseChild会被回收，出列
		fmt.Printf("第%d轮,从第%d号开始,前进%d位,出列的是%d号child,game continue!\n", n, startIndex, randInt, chooseChild.Id)
		startIndex = (randInt + startIndex + 1) % 20
		startChild = chooseChild.next // 下一轮，从chooseChild.next节点开始
	}

}

func ringInit(number int) (ring Ring) {
	// 构建一个指定成员数量的环形链表
	for i := 1; i <= number; i++ {
		var child = Child{
			Id: i,
		}
		fmt.Println(child)
		if i == 1 {
			// 插入第一个节点
			ring.Head = &child
			ring.Tail = &child
			ring.Tail.next = ring.Head // 尾节点下一个指针指向首节点
		} else {
			// 后面的节点，陆续成为新的尾结点
			child.next = ring.Head
			ring.Tail.next = &child
			ring.Tail = &child
		}
	}
	return
}

func main() {
	ring := ringInit(20)
	fmt.Println(*ring.Head, *ring.Tail)
	ring.list()
	ring.play()
}
/*
	output:
		第1轮,从第1号开始,前进1位,出列的是2号child,game continue!
		第2轮,从第3号开始,前进7位,出列的是10号child,game continue!
		第3轮,从第11号开始,前进7位,出列的是18号child,game continue!
		第4轮,从第19号开始,前进9位,出列的是9号child,game continue!
		第5轮,从第9号开始,前进1位,出列的是12号child,game continue!
		第6轮,从第11号开始,前进8位,出列的是3号child,game continue!
		第7轮,从第0号开始,前进5位,出列的是11号child,game continue!
		第8轮,从第6号开始,前进0位,出列的是14号child,game continue!
		第9轮,从第7号开始,前进6位,出列的是4号child,game continue!
		第10轮,从第14号开始,前进0位,出列的是6号child,game continue!
		第11轮,从第15号开始,前进4位,出列的是16号child,game continue!
		第12轮,从第0号开始,前进1位,出列的是19号child,game continue!
		第13轮,从第2号开始,前进2位,出列的是5号child,game continue!
		第14轮,从第5号开始,前进9位,出列的是13号child,game continue!
		第15轮,从第15号开始,前进8位,出列的是20号child,game continue!
		第16轮,从第4号开始,前进4位,出列的是17号child,game continue!
		第17轮,从第9号开始,前进1位,出列的是7号child,game continue!
		第18轮,从第11号开始,前进5位,出列的是1号child,game continue!
		第19轮,从第17号开始,前进7位,出列的是15号child,game continue!
		游戏结束，圈圈中的最后一位child是8号
*/
赏一瓶快乐回宅水吧～
-------------本文结束感谢您的阅读-------------