Hike News
Hike News

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

Golang 本文总阅读量次

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
50
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
13
{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

Golang