4. golang数据结构之单向链表

1. 链表的介绍

链表是有序的列表，但是它在内存中的存储如下：

 2. 单链表的介绍

单链表的示意图：

 说明：一般来说，为了比较好的对单链表进行增删改查的操作，我们都会给他设置一个头结点，头结点的作用主要是用来标识链表头，本身这个结点不存放数据。

3. 单链表的应用案例

案例的说明：

使用带head头的单向链表实现 — 王者荣耀排行榜管理

完成对英雄任务的增删改查操作，注：删除和修改，查找

第一种方法：在添加英雄时，直接添加到链表的尾部

代码实现：

package main
import (
	"fmt"
)

// 定义一个HeroNode
type HeroNode struct {
	no int
	name string
	nickname string
	next *HeroNode // 这个表示指向下一个结点
}

// 给链表插入一个结点
// 1.1 编写第1种插入方法，在单链表的最后加入 [简单，实用的较少，实用价值不高]
func InsertHeroNode1(head *HeroNode, newHeroNode *HeroNode) {
	// 思路
	// 1. 先找到该链表的最后这个结点
	// 2. 创建一个辅助结点：
	temp := head
	for {
		if temp.next == nil {
			break
		}
		temp = temp.next
	}
	// 3.  将newHeroNode加入到链表的最后
	temp.next = newHeroNode
}

// 1.2 编写第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.no {
			// 说明，我们的链表中已经有这个no，不让插入
			flag = false
			break
		}
		temp = temp.next
	}
	if !flag {
		fmt.Println("对不起，已经存在no=",newHeroNode.no)
		return
	} else {
		newHeroNode.next = temp.next
		temp.next = newHeroNode
	}
}

// 2. 显示链表的所有结点信息
func ListHeroNode(head *HeroNode) {
	// 1. 创建一个辅助结点[跑龙套、帮忙的]
	temp := head
	// 2. 先判断该链表是不是一个空链表
	if temp.next == nil {
		fmt.Println("这是一个空链表....")
		return
	}
	fmt.Println("链表的结点信息如下：")
	// 3. 遍历这个链表
	for {
		fmt.Printf("[%d, %s, %s]",temp.next.no,temp.next.name,temp.next.nickname)
		temp = temp.next
		// 判断是否链表尾
		if temp.next == nil {
			break
		}
	}
	fmt.Println()
}
// 3. 删除一个结点
func DelHeroNode(head *HeroNode, id int) {
	temp := head
	flag := false
	// 找到要删除结点的no，和temp的下一个结点的no比较
	for {
		if temp.next == nil { // 说明到链表的最后
			break
		} else if temp.next.no == id {
			// 说明我们找到了
			flag = true
			break
		}
		temp = temp.next
	}
	if flag { // 找到，删除
		temp.next = temp.next.next // 如果没有被指向的结点会被当成垃圾销毁掉
	} else {
		fmt.Println("sorry, 要删除的id不存在")
	}
}
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: "急急国王",
	}
	// hero4 := &HeroNode {
	// 	no: 3,
	// 	name: "成吉思汗",
	// 	nickname: "哈士奇",
	// }
	// 3. 加入
	InsertHeroNode2(head,hero3)
	InsertHeroNode2(head,hero2)
	InsertHeroNode2(head,hero1)
	// InsertHeroNode2(head,hero4)
	// 4. 显示
	ListHeroNode(head)
	// 5. 删除
	DelHeroNode(head,2)
	ListHeroNode(head)
}