链表
介绍链表的定义以及 Golang 实现。
概念性的东西
定义
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
简单分类
- 单链表，就是链表是单向的，可以一直往下找到下一个数据节点，它只有一个方向，它不能往回找。
- 双链表，每个节点既可以找到它之前的节点，也可以找到之后的节点，是双向的。
- 循环链表，就是它一直往下找数据节点，最后回到了自己那个节点，形成了一个回路。循环单链表和循环双链表的区别就是，一个只能一个方向走，一个两个方向都可以走。
GO语言实现
单链表
定义存储结构
1
2
3
4
| type LinkNode struct {
data int
next *LinkNode
}
|
初始化
1
2
3
| func InitLink() *LinkNode {
return &LinkNode{}
}
|
一些可能需要的函数
判断链表是否为空
因为很多时候需要判断链表是否为空，这里将其进行封装
1
2
3
4
5
6
| func (l *LinkNode) IsLinkNil() bool {
if l == nil{
return true
}
return false
}
|
求链表的长度
1
2
3
4
5
6
7
8
| func (l *LinkNode) LinkLength() int {
for i := 1; ; i++ {
if l.next == nil{
return i
}
l = l.next
}
}
|
打印
1
2
3
4
5
6
7
8
9
| func (l *LinkNode) print() {
for true {
fmt.Printf("%d ", l.data)
if l.next == nil {
break
}
l = l.next
}
}
|
插入
在插入时要考虑链表是否为空，为空直接插入
1
2
3
4
| func (l *LinkNode) add(data int) {
l.data = data
l.next = nil
}
|
头插法
因为go语言的特性，在方法中l = node的话只会在调用方生效而被调用方不生效，所以返回插入的节点使其变成头节点
对方法接收器的赋值仅传播到被调用方，不传播到调用方
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| func (l *LinkNode) addByHead(data int) *LinkNode {
if l.IsLinkNil() {
l.add(data)
return l
}
node := &LinkNode{
data: data,
next: l,
}
return node
}
|
尾插法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| func (l *LinkNode) addByTail(data int) {
if l.IsLinkNil() {
l.add(data)
return
}
for true {
if l.next == nil {
break
}
l = l.next
}
l.next = &LinkNode{
data: data,
next: nil,
}
}
|
按位置插入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| func (l *LinkNode) addByAddr(data int, addr int) {
if l.IsLinkNil() {
l.add(data)
return
}
if addr < 2 {
fmt.Println("请选择头插法或重新选择插入位置")
return
}
for i := 1; i < addr-1; i++ {
l = l.next
}
temp := l.next
l.next = &LinkNode{
data: data,
next: temp,
}
}
|
查询
按值查询
查询是否有该值，并返回位置，没有则返回0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| func (l *LinkNode) selectByData(data int) int {
var addr = 1
if l.IsLinkNil(){
return -1
}
for true {
if l.data == data {
break
}
if l.next == nil {
return 0
}
addr++
}
return addr
}
|
按位置查询
查询指定位置的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| func (l *LinkNode) selectByAddr(addr int) int {
if l.IsLinkNil() {
return -1
}
if l.LinkLength() < addr{
return 0
}
for i := 0; i < addr - 1; i++ {
l = l.next
}
return l.data
}
|
删除
主要是要判断各种情况的发生
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
| func (l *LinkNode) moveByAddr(addr int) *LinkNode {
if l.IsLinkNil() {
return nil
}
if addr < 2 {
res := l.next
l = nil
return res
}
for i := 1; i < addr-2; i++ {
l = l.next
}
if l.next.next == nil {
temp := l.next
l.next = nil
temp = nil
return temp
}
temp := l.next.next
remove := l.next
remove = nil
l.next = temp
return remove
}
|
双向链表与单链表类似，只是多了个前驱节点，不进行赘述。
循环链表
go标准库的实现
定义存储结构
1
2
3
4
| type Ring struct {
prev, next *Ring
data int
}
|
初始化
1
2
3
4
5
| func (r *Ring) init() *Ring {
r.prev = r
r.next = r
return r
}
|
一些可能需要的函数
打印
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| func (r *Ring) print() {
if r.isRingNil() {
fmt.Println("链表为空")
return
}
head := r
fmt.Print("链表中的元素有:")
for true {
fmt.Printf("%d ", r.data)
if r.next == head {
fmt.Println()
break
}
r = r.next
}
}
|
插入
判断是否插入的节点为空，为空则不链接
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| func (r *Ring) Link(s *Ring) *Ring {
if r.next == nil {
return r.init()
}
n := r.Next()
if *s != (Ring{}) {
p := s.Prev()
r.next = s
s.prev = r
n.prev = p
p.next = n
}
return 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
| func (r *Ring) Move(n int) *Ring {
if r.next == nil {
return r.init()
}
switch {
case n < 0:
for ; n < 0; n++ {
r = r.prev
}
case n > 0:
for ; n > 0; n-- {
r = r.next
}
}
return r
}
func (r *Ring) UnLink(n int) *Ring {
if n <= 0 {
return nil
}
return r.Link(r.Move(n + 1))
}
|
其他操作都是大同小异的。
