开发者学堂课程【Go 语言核心编程 - 数据结构和算法：数据结构和算法-单链表的有序插入】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/627/detail/9836
数据结构和算法-单链表的有序插入
内容简介：
一、单链表有序插入的必要性
二、代码实现
三、代码说明
四、代码运行及修改与改进
一、单链表有序插入的必要性
(1）出现问题
在上一节中讲了单链表的添加和显示，在上一节所写的代码中存在部分问题，首先在上一节代码的基础上在相应位置添加第三个人的代码，如下:
//2.创建一个新的 HeroNode
hero1 := &HeroNode{
no : 1,
name : “宋江”,
nickname : “及时雨”，
}hero2 := &HeroNode{
no : 2,
name : “卢俊义”,
nickname : “玉麒麟”，
}
hero3 := &HeroNode{
no : 3,
name : “林冲”,
nickname : “豹子头”，
}
还有一处是在最后的位置添加，如下:
//3.加入
InsertHeroNode(head,hero1)
InsertHeroNode(head,hero2)
InsertHeroNode(head,hero3)
//4.显示
ListHeroNode(head)
将添加修改后的代码保存并运行，结果如下:
D：\goproject\src\go_code\chapter20\singlelink\go run main.go
[1,宋江，及时雨1==>[2，卢俊义，玉麒麟1==>[3,林冲，豹子头1==>
(2）发现问题
从运行结果看并没有什么问题，因为按照顺序添加的，所以在显示的时候的确就是按照123的顺序运行的，但是如果在添加的时候，不小心写成了以下这种代码:
//3.加入
InsertHeroNode(head,hero3)
InsertHeroNode(head,hero1)
InsertHeroNode(head,hero2)
//4.显示
ListHeroNode(head)
在现实生活中有这样的情况，比如将来在实际开发中，对方给了一个结点，这个结点的编号在传递的时候它不是按照从小到大的顺序传过来的，但是它却要求你按照链表要形成一个顺序来排列，那么现在来运行一下将顺序打乱后的代码，运行结果如下:
D：\goproject\src\go_code\chapter20\singlelink\go run main.go
[3,林冲，豹子头1==>[1，宋江，及时雨1==>[2,卢俊义，玉麒麟1==>
(3）解决问题
可以看到这个列表，是三排在第一名的，一排在第二名，那这就不对了，有时候就是要求必须在添加时就按照这个顺序去排，也就是说，如果先加三，那么一和二就应该插入到中间去，所以要对这个插入的方法进行一个改进，那改进的时候，不动原先的代码，单独的再写一份 insert Hero 的结点。
二、代码实现
打开 VSCode ，找到 chapter20/singlelink/main.go ，修改代码完之后的代码如下：
package main
import (
“fmt”
)
//定义一个 HeroNode
type HeroNode struct {
no int
Name string
nickname string
next *HeroNode //这个表示指向下一个结点
}
//给链表插入一个结点
//编写第一种插入方式，在单链表的最后加入
func InsertHeroNode(head *HeroNode, newHeroNode *HeroNode) {
//思路
//1.先控制该链表的最后这个结点
//2.创建一个辅助结点[跑龙套，帮忙]
temp := head
for {
if temp.next == nil {
break
}
temp = temp.next //让 temp 不断的指向下一个结点
}
//3.将 newHeroNode 加入到链表的最后
temp.next = newHeroNode
}
//给链表插入一个结点
//编写第2种插入方式，根据 no 的编号从小到大插入..
func InsertHeroNode2(head *HeroNode, newHeroNode *HeroNode) {
//思路
//1.找到适当的结点
//2.创建一个辅助结点[跑龙套，帮忙]
temp := head
flag := true
//让插入的结点的 no ，和 temp 的下一个结点的 no 比较
for {
if temp.next == nil { //说明到链表的最后
break
} else if temp.next.no > newHeroNode.no {
//说明 newHeroNode 就应该插入到 temp 后面
break
} else if temp.next.no == newHeroNode.nc {
//说明我们链表中已经有这个 no ，就不然插入.
flag = false
break
}
temp = temp.next
}
if !flag {
fmt.Println(“对不起，已经存在 no=”， newHeroNode.no)
return
} else {
newHeroNode.next = temp.next
temp.next = newHeroNode
}
}
//显示链表的所有结点信息
func ListHeroNode(head *HeroNode) {
//1.创建一个辅助结点[跑龙套，帮忙]
temp := head
//先判断该链表是不是一个空的链表
if temp.next == nil {
fmt.Println(“空空如也。。。。”)
}
//2.遍历这个链表
for {
fmt.Printf(“[%d, %s, %s]==>”, temp.next.no,
temp.next.name, temp.next.nickname)
//判断是否链表后
temp = temp.next
if temp.next == nil {
break
}
}
}
func main() {
//1.先创建一个头结点，
head := &HeroNode{}
//2.创建一个新的 HeroNode
hero1 := &HeroNode{
no : 1,
name : “宋江”,
nickname : “及时雨”，
}
hero2 := &HeroNode{
no : 2,
name : “卢俊义”,
nickname : “玉麒麟”，
}
hero3 := &HeroNode{
no : 3,
name : “林冲”,
nickname : “豹子头”，
}
//3.加入
InsertHeroNode2(head,hero3)
InsertHeroNode2(head,hero1)
InsertHeroNode2(head,hero2)
//4.显示
ListHeroNode(head)
}
三、代码说明
说明①:在单链表最后要根据 Hero 的 no 进行编号，编号从小到大排序，就是小的排前边，从小到大到进行插入。
这个是一个非常经典的案例，以前在开发中就有这个要求，幸好我还会这个东西，不然就蔫菜了，如果说就放到数据库里面先放一下，然后 orderby ，是不允许 orderby 的，先放到数据库，先浪费三条数据，然后再查回来，Orderby 又是三条数据，假设这个服务器10万个人，那10万乘六，多少条连接过去了，10万成60万个的语句，服务器扛得住吗？
如果走内存，60万条数据全部没有了，肯定效率高，如果觉得费内存，现在几乎没人还在乎内存，现在有的是内存，内存不值钱了，随便买，以前两个计算机刚出来的时候，内存很值钱，但是现在不值钱，现在内存也花不多少钱，所以公司这点钱还是出得起的，那这个时候，根据它的编号排序，还是老规矩，这个不是找到列表最后结点，而是要找到适当的结点。
说明②:什么时候才能找到这个适当的结点？
来看一下示意图，如下:
假设宋江是一号，假设卢俊义它的编号是四号，现在要插入一个结点，它的编号是二号，想想这个怎么加，假设，现在我要插入的一个节点是二号，它在等待给它找一个位置，temp 始终有一个特别核心的作用，就是一定要让 temp 去找到下一个结点去跟它比对，才能加的进去，因为如果不通过 temp 找下一个结点的话，即使找到这个点，也没有机会加进去了。
打比方让这个 temp 去找， temp 不停的移动，移动到宋江的位置，发现2比1要大，所以这个不能确定，然后看底下的卢俊义，卢俊义是四号，它比你大，而且它原先一直保持一个有序的，所以应该插入到卢俊义的前面，那么这时还有机会插吗？结点已经跑到后面了，再想把它插在前面，那是不可能的，所以一定要在一定要在宋江的位置，就是在进行比对的时候，一定要在宋江的位置，就知道它就应该插到宋江的后面，再让宋江的节点指向它，就让它插进去了。
说明③:假设二结点要加到宋江的位置，应该怎么做?因为这个是单链表，还比较简单，如果先让宋江下结点先指向2，那这个链表就断掉了，因为一旦让宋江下结点指向2，而它又不知道卢俊义是谁，这时链表就断掉了，应该先让2结点指向卢俊义，因为 temp 刚好是指向宋江的，所以先把这个现先连起来，即 newNode.next = temp.next，如果 next 最后相当于白做了一次也无所谓；然后下一根线就再重新让宋江指向2，那这个又怎么写？
即 temp.next = newNode，其中顺序绝对不能颠倒，颠倒就完蛋了，因为如果让 next 先指向它的话，那 next 它下面那个点就找不到了。具体参考下图:
四、代码运行及修改与改进
(1）运行初代码
将以上代码保存并运行，运行结果为:
D：\goproject\src\go_code\chapter20\singlelink\go run main.go
[1,宋江，及时雨1==>[2，卢俊义，玉麒麟1==>[3,林冲，豹子头1==>
可以从运行结果看出，不管怎么插入，运行结果都是按照从小到大的顺序运行的。
(2）按照从大到小的顺序运行代码
如果想让此是按照从大到小的顺序运行，只需修改一处，即:
} else if temp.next.no < newHeroNode.no {
//说明newHeroNode就应该插入到temp后面
break
} else if temp.next.no == newHeroNode.nc {
//说明我们链表中已经有这个 no ，就不然插入.
flag = false
break
上文代码只修改了一处，即将“>”改成了”<”.修改后保存并运行，结果如下:
D：\goproject\src\go_code\chapter20\singlelink\go run main.go
[3,林冲，豹子头1==>[2，卢俊义，玉麒麟1==>[1,宋江，及时雨1==>
(3）添加一个相同的结点代码运行
那如果添加一个相同的结点，即添加一个新的 Hero4 ，但是在3结点添加，如下代码:
//2.创建一个新的 HeroNode
hero1 := &HeroNode{
no : 1,
name : “宋江”,
nickname : “及时雨”，
}
hero2 := &HeroNode{
no : 2,
name : “卢俊义”,
nickname : “玉麒麟”，
}
hero3 := &HeroNode{
no : 3,
name : “林冲”,
nickname : “豹子头”，
}
hero4 := &HeroNode{
no : 3,
name : “吴用”,
nickname : “智多星”，
}
//3.加入
InsertHeroNode2(head,hero3)
InsertHeroNode2(head,hero1)
InsertHeroNode2(head,hero2)
InsertHeroNode2(head,hero4)
//4.显示
ListHeroNode(head)
}
修改完成之后保存并运行，结果如下:
D：\goproject\src\go_code\chapter20\singlelink\go run main.go
对不起，已经存在no = 3
[1,宋江，及时雨1==>[2，卢俊义，玉麒麟1==>[3,林冲，豹子头1==>
(4)允许有相同编号的存在代码运行
如果允许有相同编号的存在，也是只修改一处位置，如下:
} else if temp.next.no >= newHeroNode.no {
//说明 newHeroNode 就应该插入到 temp 后面
break
} else if temp.next.no == newHeroNode.nc {
//说明我们链表中已经有这 no，就不然插入.
flag = false
Break
上文代码只修改了一处，即将“>”改成了”>=”.修改后保存并运行，运行结果如下:
D：\goproject\src\go_code\chapter20\singlelink\go run main.go
[1,宋江，及时雨1==>[2，卢俊义，玉麒麟1==>[3,吴用，智多星1==>[3.林冲，豹子头1==>
