golang定义单向链表

发表于 更新于
醉后不知天在水，满船清梦压星河

简述

单向链表属于链表的一种，也叫单链表，单向即是说它的链接方向是单向的，它由若干个节点组成，每个节点都包含下一个节点的指针。

其实关于链表，大家完全可以把他和数组进行类比学习，只不过数组由于申请的空间必须是连续地，所以有的时候内存地址可能分配不出足够的内存空间。链表的的内存空间可以不连续的特性就可以解决数组的痛点了。

对于链表与数组的使用场景就是，如果你的数据需要经常的查询，那么数组更快。如果你的数据需要频繁的插入删除，链表比数组更快。

  • 创建单链表时无需指定链表的长度，这个比起数组结构更加有优势，而数组纵使实现成动态数组也是需要指定一个更大的数组长度，而且要把原来的数组元素一个个复制到新数组中。
  • 单链表中的节点删除操作很方便，它可以直接改变指针指向来实现删除操作，而某些场景下数组的删除会导致移动剩下的元素。
  • 单链表中的元素访问需要通过顺序访问，即要通过遍历的方式来寻找元素，而数组则可以使用随机访问，这点算是单链表的缺点。

定义

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

// 节点的数据结构
type Node struct {
    E int
    Next *Node
}
// 链表的数据结构
type List struct {
    dummyHead *Node
    size int
}

func (l List) Head() *Node {
    return l.dummyHead
}

func (l List) Size() int {
    return l.size
}
// 初始化一个节点
func initNode (e int) *Node {
    return &Node{
        E:e,
        Next:nil,
    }
}
// 初始化一个空链表
func InitList () *List {
    return &List{
        dummyHead:initNode(0),
        size:0,
    }
}

虽然代码注释里写的是初始化一个空链表，却在里面实实在在地初始化了一个节点出来。这种技术叫做虚拟头结点，他的具体好处如下：

防止单链表是空的而设的，当链表为空的时候,带头结点的头指针就指向头结点。如果当链表为空的时候,单链表没有带头结点,那么它的头指针就为 NULL。

是为了方便单链表的特殊操作，插入在表头或者删除第一个结点。这样就保持了单链表操作的统一性。

单链表加上头结点之后，无论单链表是否为空，头指针始终指向头结点，因此空表和非空表的处理也统一了，方便了单链表的操作，也减少了程序的复杂性和出现 bug 的机会。

对单链表的多数操作应明确对哪个结点以及该结点的前驱。不带头结点的链表对首元结点、中间结点分别处理等；而带头结点的链表因为有头结点，首元结点、中间结点的操作相同，从而减少分支，使算法变得简单，流程清晰。

基本操作

  • 插入操作，其中又分为往一个索引对应的位置插入，往头结点后插入，在链表尾部插入三种插入方法。
  • 删除节点，其中又分为删除一个索引位置的节点，删除一个值对应的节点，删除第一个节点，删除尾节点。
  • 查询节点，同样分为查询某个索引值的节点，查询头部，查询尾部。
  • 修改节点，修改某个索引值对应的节点。
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
// 判断链表是否为空
func (this *List) IsEmpty() bool {
    return this.size == 0
}
// 插入部分
// 在链表的第index索引个元素后插入元素,索引从0开始
func (this *List) AddIndex (index,e int) {
    if index > this.size || index < 0 {
        panic("索引越界，不能插入了")
    }
    prev := this.dummyHead
    node := initNode(e)

    for i:=0;i<index;i++ {
        prev = prev.Next
    }
    // 这里的步骤一定不能反过来，思考一下为什么
    node.Next = prev.Next
    prev.Next = node
    this.size++

}
// 在链表头添加元素
func (this *List) AddFirst (e int) {
    this.AddIndex(0,e)
}
// 在链表尾部添加节点
func (this *List) AddLast (e int) {
    this.AddIndex(this.size,e)
}
// 查询部分
// 在链表中查询是否包括元素e
func (this *List) Contains (e int) bool {
    cur := this.dummyHead.Next
    for cur!=nil {
        if cur.E == e{
            return true
        }
        cur = cur.Next
    }
    return false
}
// 在链表中查询第index个元素
func (this *List) Get (index int) int {
    if index > this.size || index < 0 {
        panic("索引越界，不能查询")
    }
    cur := this.dummyHead.Next
    for i:=0;i<index;i++ {
        cur = cur.Next
    }
    return cur.E
}
func (this *List) GetFirst () int{
    return this.Get(0)
}
func (this *List) GetLast () int{
    return this.Get(this.size-1)
}
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
package main

import (
    "fmt"
    "strings"
)

type Node struct {
    E int
    Next *Node
}

type List struct {
    dummyHead *Node
    size int
}

func (l List) Head() *Node {
    return l.dummyHead
}


func (l List) Size() int {
    return l.size
}
func initNode (e int) *Node {
    return &Node{
        E:e,
        Next:nil,
    }
}
func InitList () *List {
    return &List{
        dummyHead:initNode(0),
        size:0,
    }
}
func (this *List) IsEmpty() bool {
    return this.size == 0
}
// 在链表的第index索引个元素后插入元素,索引从0开始
func (this *List) AddIndex (index,e int) {
    if index > this.size || index < 0 {
        panic("索引越界，不能插入了")
    }
    prev := this.dummyHead
    node := initNode(e)

    for i:=0;i<index;i++ {
        prev = prev.Next
    }
    node.Next = prev.Next
    prev.Next = node
    this.size++

}
// 在链表头添加元素
func (this *List) AddFirst (e int) {
    this.AddIndex(0,e)
}
// 在链表尾部添加节点
func (this *List) AddLast (e int) {
    this.AddIndex(this.size,e)
}
// 在链表中查询第index个元素
func (this *List) Get (index int) int {
    if index > this.size || index < 0 {
        panic("索引越界，不能查询")
    }
    cur := this.dummyHead.Next
    for i:=0;i<index;i++ {
        cur = cur.Next
    }
    return cur.E
}
func (this *List) GetFirst () int{
    return this.Get(0)
}
func (this *List) GetLast () int{
    return this.Get(this.size-1)
}
// 在链表index个位置中放入元素e
func (this *List) Set (index,e int) {
    if index > this.size || index < 0 {
        panic("索引越界，不能置入")
    }
    cur := this.dummyHead.Next
    for i:=0;i<index;i++ {
        cur = cur.Next
    }
    cur.E = e
}
// 在链表中查询是否包括元素e
func (this *List) Contains (e int) bool {
    cur := this.dummyHead.Next
    for cur!=nil {
        if cur.E == e{
            return true
        }
        cur = cur.Next
    }
    return false
}
// 在链表中删除元素
func (this *List) Remove (index int) int {
    if index > this.size || index < 0 {
        panic("索引越界，不能删除")
    }
    prev := this.dummyHead
    for i:=0;i<index;i++ {
        prev = prev.Next
    }
    retNode := prev.Next
    prev.Next = retNode.Next
    this.size--
    return retNode.E
}
func (this *List) RemoveFirst () int{
    return this.Remove(0)
}
func (this *List) RemoveLast () int{
    return this.Remove(this.size-1)
}
// 删除元素E
func (this *List) RemoveElement (e int) {
    prev := this.dummyHead
    for prev.Next != nil {
        if prev.E == e {
            break
        }
        prev = prev.Next
    }
    if prev.Next != nil {
        DelNode := prev.Next
        prev.Next = DelNode.Next
        DelNode = nil
    }
}
// 在Golang中，如果我们想对自建数据结构自定义在Println的时候打印出什么结果
// 就可以使用这种方式去自己构建打印的字符串格式
func (this *List) String () string {
    var builder strings.Builder
    cur := this.dummyHead.Next
    for cur != nil {
        fmt.Fprintf(&builder,"%d -> ",cur.E)
        cur = cur.Next
    }
    fmt.Fprintf(&builder,"NULL")
    return builder.String()
}

func main() {
    list := InitList()
    for i:=0;i<5 ; i++  {
        list.AddLast(i)
    }
    fmt.Println(list)
    fmt.Println(list.Contains(0))
    fmt.Println(list.Get(3))
    fmt.Println(list.RemoveLast())
    fmt.Println(list.GetFirst())
    // 其他功能可以自行测试。
}

链表的应用

逆序一个链表

给定一个带头结点的单链表,请将其逆序。即如果单链表原来为 head -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 。则逆序后变为 head -> 7 -> 6 -> 5 -> 4- > 3 -> 2 -> 1。

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

import (
    "fmt"
    "strings"
)

// 在这个函数前需要将list.go的代码拷贝到这里

func (this *List)Reverse()  {
    var pre *Node
    var cur *Node
    next := this.Head().Next

    for next != nil {
        cur = next.Next
        next.Next = pre
        pre = next
        next = cur
    }
    this.Head().Next = pre
}

func main(){
    list := InitList()
    for i:=0;i<5 ; i++  {
        list.AddFirst(i)
    }
    fmt.Println(list)
    list.Reverse()
    fmt.Println(list)
}

计算两个单链表所代表的的代数之和

给定两个单链表,链表的每个结点代表一位数, 计算两个数的和。例如 : 输入链表 (3->1->5) 和链表 (5->9->2) ，输出: 8->0->8 ，即 513 + 295 = 808 ，注意个位数在链表头。

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

import (
    "fmt"
    "strings"
)

// 在这个函数前需要将list.go的代码拷贝到这里


// 把两个用链表表示的整数相加
func AddTwoList(head1,head2 *Node) *List {
    // 初始化一个新链表
    newHead := InitList()
    // 因为有dummyHead，所以head的下一个节点才是真真正的头结点
    p1 := head1.Next
    p2 := head2.Next
    carry := 0
    for p1 != nil || p2 != nil {
        // 如果p1到头就只需要添加p2，反之同理
        if p1 == nil {
            newHead.AddLast(p2.E+ + carry)
            p2 = p2.Next
        }
        if p2 == nil {
            newHead.AddLast(p1.E + carry)
            p1 = p1.Next
        }
        // 计算本位的值
        temp := (p1.E + p2.E + carry )%10
        newHead.AddLast(temp)
        // 记录进位
        carry = (p1.E + p2.E + carry )/10
        p1 = p1.Next
        p2 = p2.Next
    }
    return newHead
}

// 测试代码和测试结果
func main(){
    list := InitList()
    list2 := InitList()
    for i:=0;i<6 ; i++  {
        list.AddFirst(i)
    }
    for i:=0;i<6 ; i++  {
        list2.AddFirst(i+1)
    }
    fmt.Println(list)
    fmt.Println(list2)
    newlist := AddTwoList(list.Head(),list2.Head())
    fmt.Println(newlist)
}