Hike News
Hike News

Golang資料結構-day14-鏈表(Linked list)

introduction

  1. 結構體會有一些自己的字段,但其中有一個字段,是指向自己結構體類型指針類型
  2. 使用此結構體做為類型的變量,被稱為節點
  3. 每個節點包含下一個節點的地址,這樣可把所有的節點都串起來
  4. 通常鏈表中的第一個節點被叫做鏈表頭
    https://zh.wikipedia.org/wiki/%E9%93%BE%E8%A1%A8

範例

1
2
3
4
5
6
type Student struct{
Name string
Age int
Score float64
Next *Student //[1]
}

[1] 結構體的前半部為結構體的一般字段(屬性),Next字段的類型為自身結構體的指針


單向鏈表

又稱單向連結串列,它包含兩個域一個資訊域(一般屬性)和一個指標域(Next字段)。
指標域連結指向鏈表中的下一個節點,而最後一個節點則指向一個空值(nil)
透過Next字段可將使用同種結構體類型的變量全部遍歷

  • 相當於使用一條繩子將所有結構體串起來
    single chain

  • 缺點:要遍歷整張鏈表,需記住鏈表頭的地址;從其他任一節點開始遍歷都無法完整查看整張鏈表

  • 若將最後一個節點的next字段指向鏈表頭地址,則為循環單鏈表

鏈表與陣列

陣列:在固定長度連續內存空間中,通過index訪問各陣列內的元素
鏈表:鏈表的內存空間分配不是連續的,元素之間串聯需通過指針,(Next字段)
且鏈表的長度不固定,可隨時增加或減少


新增與插入節點-尾部插入法

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

import (
"fmt"
)

type Student struct {
Name string
Age int
Score float64
Next *Student
}

func main(){

//創建頭節點
var HeadNode *Student = &Student{
Name : "Curtis",
Age : 18,
Score : 90.0,
}

//創建第二節點
var SecondNode *Student = &Student{
Name : "Tom",
Age : 27,
Score :60,
//[1]
}

//插入 第二節點地址 到 頭節點的Next字段中
HeadNode.Next = SecondNode
}

[1] Next字段不寫的情況下默認為空

tips

  • 請注意!!,此方法新增的節點都只能在末尾插入
  • 讓末尾節點的Next字段,從原本指向空(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
package main

import (
"fmt"
)

type Student struct {
Name string
Age int
Score float64
Next *Student
}

func main(){

var HeadNode *Student = &Student{
Name : "Curtis",
Age : 18,
Score : 90.0,
}

var SecondNode *Student = &Student{
Name : "Tom",
Age : 27,
Score :60,
}

HeadNode.Next = SecondNode

//創建第三個節點
var ThirdNode Student
ThirdNode.Name = "Amy"
ThirdNode.Age = 20
ThirdNode.Score = 70

//插入第三個節點的地址 到第二個節點的Next字段
SecondNode.Next = &ThirdNode

//創建一個變量,接收節點資訊,並指向頭節點
view := HeadNode

//只要節點中的資訊不為空,就會打印節點資訊
for view != nil{
fmt.Println(*view)

//將欲查看的下個節點 指向 已查看完節點的Next字段
view = view.Next
}
}

result

1
2
3
{Curtis 18 90 0xc04206a1e0}
{Tom 27 60 0xc04206a210}
{Amy 20 70 <nil>}

批量創建節點-尾部插入

於main函數中實現

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

import (
"fmt"
"math/rand"
)

type Student struct {
Name string
Age int
Score float64
Next *Student
}

func view(head *Student){
for head != nil{
fmt.Println(*head)
head = head.Next
}
}

func main(){

var HeadNode *Student = &Student{
Name : "Curtis",
Age : 18,
Score : 90.0,
}

//定義一個變量記錄尾部節點的指針
tail := HeadNode

for i:=0;i<10;i++{
//創建新節點
Node := Student{
Name : fmt.Sprintf("Student%d",i),
Age : rand.Intn(100),
Score : rand.Float64() * 100,
}

//尾部節點的Next字段指向新節點的地址
tail.Next = &Node

//將尾部節點替換為新節點的地址,以獲取新節點的指針
tail = &Node
}

//遍歷鏈表節點
view(HeadNode)
}

函數化實現

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

import (
"fmt"
"math/rand"
)

type Student struct {
Name string
Age int
Score float64
Next *Student
}

func view(head *Student){
for head != nil{
fmt.Println(*head)
head = head.Next
}
}

//尾部插入法函數
func loop_tail_insert(Node *Student){
tail := Node
for i:=0;i<10;i++{
Node := Student{
Name : fmt.Sprintf("Student%d",i),
Age : rand.Intn(100),
Score : rand.Float64() * 100,
}
tail.Next = &Node
tail = &Node
}
}

func main() {
var HeadNode *Student = &Student{
Name: "Curtis",
Age: 18,
Score: 90.0,
}
loop_tail_insert(HeadNode)

view(HeadNode)
}

result

1
2
3
4
5
6
7
8
9
10
11
{Curtis 18 90 0xc04206a210}
{Student0 81 94.05090880450125 0xc04206a240}
{Student1 47 43.771418718698015 0xc04206a270}
{Student2 81 68.68230728671094 0xc04206a2a0}
{Student3 25 15.651925473279125 0xc04206a2d0}
{Student4 56 30.091186058528706 0xc04206a300}
{Student5 94 81.36399609900968 0xc04206a330}
{Student6 62 38.065718929968604 0xc04206a360}
{Student7 28 46.88898449024232 0xc04206a390}
{Student8 11 29.310185733681575 0xc04206a3c0}
{Student9 37 21.855305259276427 <nil>}

頭部插入法

於main函數中實現

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

import (
"fmt"
"math/rand"
)

type Student struct {
Name string
Age int
Score float64
Next *Student
}

func view(head *Student){
for head != nil{
fmt.Println(*head)
head = head.Next
}
}

func main(){
var HeadNode *Student = &Student{
Name : "Curtis",
Age : 18,
Score : 90.0,
}

//新建一個變量來記錄 原舊頭節點的指針
Head := HeadNode

for i:=0;i<10;i++{

//創建節點
NewNode := Student{
Name : fmt.Sprintf("stu%d",i),
Age : rand.Intn(100),
Score : rand.Float64() * 100,

//新的節點指向舊的頭節點
Next : Head,
}

//將 舊的頭節點 替換成 新的頭節點 的指針
Head = &NewNode

}

//遍歷鏈表節點
view(Head)
}

函數化實現

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

import (
"fmt"
"math/rand"
)

type Student struct {
Name string
Age int
Score float64
Next *Student
}

func view(head *Student){
for head != nil{
fmt.Println(*head)
head = head.Next
}
}

//頭部插入法函數
func loop_head_insert(Node *Student)(*Student){
Head := Node
for i:=0;i<10;i++{
NewNode := Student{
Name : fmt.Sprintf("stu%d",i),
Age : rand.Intn(100),
Score : rand.Float64() * 100,
Next : Head,
}
Head = &NewNode
}
return Head
}

func main(){

var HeadNode *Student = &Student{
Name : "Curtis",
Age : 18,
Score : 90.0,
}

NewHead := loop_head_insert(HeadNode)

//遍歷鏈表節點
view(NewHead)
}

result

1
2
3
4
5
6
7
8
9
10
11
{stu9 37 21.855305259276427 0xc04206a3c0}
{stu8 11 29.310185733681575 0xc04206a390}
{stu7 28 46.88898449024232 0xc04206a360}
{stu6 62 38.065718929968604 0xc04206a330}
{stu5 94 81.36399609900968 0xc04206a300}
{stu4 56 30.091186058528706 0xc04206a2d0}
{stu3 25 15.651925473279125 0xc04206a2a0}
{stu2 81 68.68230728671094 0xc04206a270}
{stu1 47 43.771418718698015 0xc04206a240}
{stu0 81 94.05090880450125 0xc04206a210}
{Curtis 18 90 <nil>}

刪除節點

紀錄要被刪除節點的上一節點地址,並將上一節點的next字段替換為要刪除節點的next字段(亦就是下一節點的地址)

於main函數中實現

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

import (
"fmt"
"math/rand"
)

type Student struct {
Name string
Age int
Score float64
Next *Student
}

func view(head *Student){
for head != nil{
fmt.Println(*head)
head = head.Next
}
}

func loop_tail_insert(Node *Student){
tail := Node
for i:=0;i<10;i++{
Node := Student{
Name : fmt.Sprintf("Student%d",i),
Age : rand.Intn(100),
Score : rand.Float64() * 100,
}
tail.Next = &Node
tail = &Node
}
}

func main() {
var HeadNode *Student = &Student{
Name: "Curtis",
Age: 18,
Score: 90.0,
}

loop_tail_insert(HeadNode)

//紀錄頭節點位置
Head := HeadNode

//要刪除的節點特徵
choice := "Curtis"

//遍歷節點找到要刪除的節點
for Head != nil{

//確定第一個節點是否為刪除的節點
if Head.Name == choice {
Head = Head.Next
HeadNode = Head
break

//當前節點 的 下一節點的字段符合特徵
} else if Head.Next.Name == choice{

//將當前節點的Next字段指向要被刪除節點的Next字段
Head.Next =Head.Next.Next
break
}
//否則當前節點 更新為 當前節點的Next字段指向的內存地址
Head = Head.Next
}
//重新遍歷鏈表
view(HeadNode)
}

函數化實現

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

import (
"fmt"
"math/rand"
)

type Student struct {
Name string
Age int
Score float64
Next *Student
}

func view(head *Student){
for head != nil{
fmt.Println(*head)
head = head.Next
}
}

func loop_tail_insert(Node *Student){
tail := Node
for i:=0;i<10;i++{
Node := Student{
Name : fmt.Sprintf("Student%d",i),
Age : rand.Intn(100),
Score : rand.Float64() * 100,
}
tail.Next = &Node
tail = &Node
}
}

func del (Node *Student,choice string)*Student{
Head := Node
for Head != nil{
if Head.Name == choice{
Head = Head.Next
Node.Next = nil
return Head
}else if Head.Next.Name == choice{
Head.Next =Head.Next.Next
break
}
Head = Head.Next

}
return Node
}

func main() {
var HeadNode *Student = &Student{
Name: "Curtis",
Age: 18,
Score: 90.0,
}

loop_tail_insert(HeadNode)

//返回新節點
New_Node := del(HeadNode,"Curtis")

view(New_Node)
}

result

1
2
3
4
5
6
7
8
9
10
{Student0 81 94.05090880450125 0xc042074240}
{Student1 47 43.771418718698015 0xc042074270}
{Student2 81 68.68230728671094 0xc0420742a0}
{Student3 25 15.651925473279125 0xc0420742d0}
{Student4 56 30.091186058528706 0xc042074300}
{Student5 94 81.36399609900968 0xc042074330}
{Student6 62 38.065718929968604 0xc042074360}
{Student7 28 46.88898449024232 0xc042074390}
{Student8 11 29.310185733681575 0xc0420743c0}
{Student9 37 21.855305259276427 <nil>}

節點插入

找到要被插入的節點,讓新節點指向原本的Next字段,在讓當前節點指向新節點

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

import (
"fmt"
"math/rand"
)

type Student struct {
Name string
Age int
Score float64
Next *Student
}

func view(head *Student){
for head != nil{
fmt.Println(*head)
head = head.Next
}
}

func loop_tail_insert(Node *Student){
tail := Node
for i:=0;i<10;i++{
Node := Student{
Name : fmt.Sprintf("Student%d",i),
Age : rand.Intn(100),
Score : rand.Float64() * 100,
}
tail.Next = &Node
tail = &Node
}
}

func insert (HeadNode *Student,InsertNode *Student,choice string){
for HeadNode != nil {
if HeadNode.Name == choice {
InsertNode.Next = HeadNode.Next
HeadNode.Next = InsertNode
break
}
HeadNode = HeadNode.Next
}
}

func main() {
var HeadNode *Student = &Student{
Name: "Curtis",
Age: 18,
Score: 90.0,
}

loop_tail_insert(HeadNode)

var InseretNode *Student = &Student{
Name: "Insert",
Age: 9,
Score: 0.0,
}

insert(HeadNode,InseretNode,"Student5")

//重新遍歷鏈表
view(HeadNode)
}

result

1
2
3
4
5
6
7
8
9
10
11
12
{Curtis 18 90 0xc042074210}
{Student0 81 94.05090880450125 0xc042074240}
{Student1 47 43.771418718698015 0xc042074270}
{Student2 81 68.68230728671094 0xc0420742a0}
{Student3 25 15.651925473279125 0xc0420742d0}
{Student4 56 30.091186058528706 0xc042074300}
{Student5 94 81.36399609900968 0xc0420743f0}
{Insert 9 0 0xc042074330}
{Student6 62 38.065718929968604 0xc042074360}
{Student7 28 46.88898449024232 0xc042074390}
{Student8 11 29.310185733681575 0xc0420743c0}
{Student9 37 21.855305259276427 <nil>}

雙向鏈表

每個節點有兩個連線:一個指向前一個節點(prev字段),(當此「連線」為第一個「連線」時,指向空值(nil)或者空列表)
而另一個指向下一個節點(next字段),(當此「連線」為最後一個「連線」時,指向空值(nil)或者空列表)

  • 在任何節點皆能遍歷整張列表

double_direct_chain