数据结构和算法-03

链表

简介

引用百度百科的一段话：

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

到目前为止，我依然很不理解为什么链表中表示某个数据单元用的是结点而不是节点

单链表

单链表的结点存储地址是放在前结点的指针域中。单链表中的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
50
51


package main

import "fmt"

type Hero struct {
	ID       int
	Name     string
	NickName string
	Next     *Hero
}

func NewHero(id int, name string, nickname string) *Hero {
	return &Hero{
		ID:       id,
		Name:     name,
		NickName: nickname,
	}
}

func (h *Hero) InsertHero(NewHero *Hero) {
	// 通过定义临时结点来遍历整个链表
	tmp := h
	for {
		// 遇到 指针域 为空，说明已经到了链表的结尾，退出遍历进行赋值
		if tmp.Next == nil {
			break
		}
		// 不断遍历新的结点
		tmp = tmp.Next
	}
	tmp.Next = NewHero
}

func (h *Hero) ListHeros() {
	tmp := h
	for {
		fmt.Printf("%v --> ", tmp)
		if tmp.Next == nil {
			break
		}
		tmp = tmp.Next
	}
	fmt.Println()
}

func main() {
	head := NewHero(0, "", "")
	hero01 := NewHero(1, "宋江", "及时雨")
	head.InsertHero(hero01)
	head.ListHeros()
}

顺序插入结点

通过比较结点中的某个特定元素，来进行顺序插入。当完成比对时，一定要先将当前结点的指针值赋给新插入结点的指针，然后再将新结点的值赋给当前结点。否则，容易造成单链表的结点丢失。

 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


func (h *Hero) SeqInsert(NewHero *Hero) {
	tmp := h
	// head结点为空时，直接插入数据
	if tmp.Next == nil && tmp.ID == 0 {
		tmp.Next = NewHero
		return
	}
	for {
		// 新加入结点的ID，在整个链表中最大
		if tmp.Next == nil && tmp.ID < NewHero.ID {
			tmp.Next = NewHero
			break
			// 循环到最后一个，退出循环
		} else if tmp.Next == nil {
			break
			// 新加入的结点ID大于当前结点ID，小于下一个结点ID时，进行插入操作
		} else if NewHero.ID > tmp.ID && NewHero.ID < tmp.Next.ID {
			NewHero.Next = tmp.Next 
			tmp.Next = NewHero
			break
			// ID相等时，不进行任何操作
		} else if tmp.ID == NewHero.ID {
			break
		}
		tmp = tmp.Next
	}

}
func main() {
	head := NewHero(0, "", "")
	hero01 := NewHero(10, "宋江", "及时雨")
	hero02 := NewHero(20, "林冲", "豹子头")
	hero03 := NewHero(21, "卢俊义", "玉麒麟")
	head.SeqInsert(hero03)
	head.SeqInsert(hero01)
	head.SeqInsert(hero02)
	head.ListHeros()
}

删除指定结点

通过指定结点元素，对比下一个结点指定元素的值来定位结点。将匹配到的结点的指针域的值赋给当前结点的指针域即可。

 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


func (h *Hero) DeleteNode(id int) {
	tmp := h
	flag := false
	for {
		if tmp.Next == nil {
			break
		}
		if tmp.Next.ID == id {
			flag = true
			break
		}
		tmp = tmp.Next
	}
	if flag {
		tmp.Next = tmp.Next.Next
	} else {
		fmt.Println("no found!")
	}
}

func main() {
	head := NewHero(0, "", "")
	hero01 := NewHero(10, "宋江", "及时雨")
	hero02 := NewHero(20, "林冲", "豹子头")
	hero03 := NewHero(21, "卢俊义", "玉麒麟")
	head.SeqInsert(hero01)
	head.SeqInsert(hero03)
	head.SeqInsert(hero02)
	head.ListHeros()
	head.DeleteNode(10)
	head.DeleteNode(101)
	head.ListHeros()
}

双向链表

双向链表是指在链表结点的元素中既有包含下一个结点的指针域，也有包含上一个结点的指针域。