Go数据结构和算法-链表
- 单向链表实现及增删改查
- 双向链表实现及增删改查
- 循环链表实现及增删改查
链表是一个有序(FIFO)的列表
单链表
带头节点的单向链表
头节点的作用: 不存放数据，用来标识链表头，为了方便的对单链表进行增删改查
单链表实现
next指向下一个节点
type heroNode struct {
number int
name string
nickname string
next *heroNode
}
给单链表新增节点
直接在链表尾部插入
思路: 判断当前节点是否为最后一个节点,如果是则插入，不是则遍历下个节点
func insert(head *heroNode, newHeroNode *heroNode) {
for {
// 如果 true 表示找到链表末尾; 并赋值插入
if head.next == nil {
head.next = newHeroNode
return
} else {
// 当前node不是，则进入下一个node
head = head.next
}
}
}
根据编号从小到大排列插入指定位置
前提: 节点已是从小到大排列顺序
思路: 带插入节点newHeroNode.number编号小于head.next.number则找到位置
func insertById(head *heroNode, newHeroNode *heroNode) {
for {
// 如果 true 表示找到链表末尾; 并赋值
if head.next == nil {
head.next = newHeroNode
return
} else if newHeroNode.number < head.next.number {
newHeroNode.next = head.next
head.next = newHeroNode
return
} else if newHeroNode.number == head.next.number {
fmt.Println("存在相同id，不允许插入")
return
} else {
// 当前node不是，则进入下一个node
head = head.next
}
}
}
删除单链表中指定节点
思路: 当前所在节点在待删除节点前一位,将当前节点的next直接指向待删除节点中的next(取代待删除节点)
func deleteById(head *heroNode, number int) {
for {
// 没找到符合指定条件的节点
if head.next == nil {
fmt.Println("不存在de序号: ", number)
return
} else if number == head.next.number {
// 实现
if head.next.next != nil {
head.next = head.next.next
} else {
head.next = nil
}
return
} else {
// 当前node不是，则进入下一个node
head = head.next
}
}
}
更新单链表中指定节点
func update(head *heroNode, newHeroNode *heroNode) {
for {
// 没找到
if head.next == nil {
fmt.Println("不存在de序号: ", newHeroNode.number)
return
} else if newHeroNode.number == head.next.number {
// 实现更新
newHeroNode.next = head.next.next
head.next = newHeroNode
return
} else {
head = head.next
}
}
}
查询单链表中所有节点信息
func listHeroNode(head *heroNode) {
for {
// 1. 判断当前 node 是否为末尾 node ( 当前 node 的 next 的值是否是空指针 nil)
if head.next == nil {
return
}
// 2. 不是则输出 info
fmt.Printf("排名: %d \t 姓名: %s \t 昵称: %s \n", head.next.number, head.next.name, head.next.nickname)
// 3. "移至"下一个节点
head = head.next
}
}
测试
func main() {
// 1. 先创建一个头节点，
head := &heroNode{}
// 2. 创建一个新的heroNode
hero1 := &heroNode{
number: 1,
name: "宋江",
nickname: "及时雨",
}
hero2 := &heroNode{
number: 2,
name: "林冲",
nickname: "豹子头",
}
hero3 := &heroNode{
number: 3,
name: "卢俊义",
nickname: "玉麒麟",
}
hero4 := &heroNode{
number: 4,
name: "吴用",
nickname: "智多星",
}
// 3. 增
insertById(head, hero3)
insertById(head, hero1)
insertById(head, hero2)
insertById(head, hero4)
// insertById(head, hero4)
// 4. 查
listHeroNode(head)
// 5. 删
deleteById(head, 4)
// 6. 改
heroUpdate := &heroNode{
number: 2,
name: "林不冲",
nickname: "狮子头",
}
update(head, heroUpdate)
// 4. 查
fmt.Println()
listHeroNode(head)
}
运行结果如下：
双向链表
带头节点的双向链表
双向链表实现
pre 指向前一个节点 next 指向下一个节点
type heroNode struct {
number int
name string
nickname string
pre *heroNode
next *heroNode
}
给双链表新增节点
直接在双向链表尾部插入
思路: 找到链表的最后一个节点, 描述 head.next 和 newHeroNode.pre
func insert(head *heroNode, newHeroNode *heroNode) {
for {
// 如果 true 表示找到链表末尾; 并赋值
if head.next == nil {
head.next = newHeroNode
newHeroNode.pre = head
return
} else {
// 当前node不是，则进入下一个node
head = head.next
}
}
}
根据编号从小到大排列插入指定位置
前提: 节点已是从小到大排列顺序
思路: head.next.number > newHeroNode.number
func insertById(head *heroNode, newHeroNode *heroNode) {
for {
// 如果 true 表示找到链表末尾;
if head.next == nil {
head.next = newHeroNode
newHeroNode.pre = head
return
} else if newHeroNode.number <= head.next.number {
head.next.pre = newHeroNode
newHeroNode.next = head.next
newHeroNode.pre = head
head.next = newHeroNode
return
} else if newHeroNode.number == head.next.number {
fmt.Println("存在相同id，不允许插入")
return
} else {
// 当前node不是，则进入下一个node
head = head.next
}
}
}
删除双链表中指定节点
思路:
当前所在节点在待删除节点前一位
- 将待删除节点的下一个节点的pre指向当前节点
- 将当前节点
head.next指向待删除节点的下一个节点，即head.next.next
func deleteById(head *heroNode, number int) {
for {
// 没找到
if head.next == nil {
fmt.Println("不存在de序号: ", number)
return
} else if number == head.next.number {
// 实现
if head.next.next != nil {
head.next.next.pre = head
head.next = head.next.next
} else {
head.next = nil
}
return
} else {
// 当前node不是，则进入下一个node
head = head.next
}
}
}
更新双链表中指定节点
思路: 找到符合条件的节点 newHeroNode.number == head.next.number
func update(head *heroNode, newHeroNode *heroNode) {
for {
// 没找到
if head.next == nil {
fmt.Println("不存在de序号: ", newHeroNode.number)
return
} else if newHeroNode.number == head.next.number {
// 实现4步关联
// 修改待更新节点的下个节点的pre
head.next.next.pre = newHeroNode
// 更新节点
newHeroNode.pre = head
newHeroNode.next = head.next.next
// 修改当前节点的next
head.next = newHeroNode
return
} else {
head = head.next
}
}
}
查询双链表中所有节点信息
func listHeroNode(head *heroNode) {
for {
// 1. 判断当前 node 是否为末尾 node ( 当前 node 的 next 的值是否是空指针 nil)
if head.next == nil {
return
}
// 2. 不是则输出 info
fmt.Printf("prev排名: %d \t 姓名: %s \t 昵称: %s \n", head.number, head.name, head.nickname)
fmt.Printf("curr排名: %d \t 姓名: %s \t 昵称: %s \n", head.next.number, head.next.name, head.next.nickname)
if head.next.next != nil {
fmt.Printf("next排名: %d \t 姓名: %s \t 昵称: %s \n", head.next.next.number, head.next.next.name, head.next.next.nickname)
}
fmt.Println("---------")
// 3. 将当前node下的next传给head
head = head.next
}
}
main函数
func main() {
// 1. 先创建一个头节点，
head := &heroNode{}
// 2. 创建一个新的heroNode
hero1 := &heroNode{
number: 1,
name: "宋江",
nickname: "及时雨",
}
hero2 := &heroNode{
number: 2,
name: "林冲",
nickname: "豹子头",
}
hero3 := &heroNode{
number: 3,
name: "卢俊义",
nickname: "玉麒麟",
}
hero4 := &heroNode{
number: 4,
name: "吴用",
nickname: "智多星",
}
// 3. 在尾部新增节点
insert(head, hero1)
// insert(head, hero2)
insert(head, hero3)
insert(head, hero4)
// 3.1 指定位置新增节点
listHeroNode(head)
insertById(head, hero2)
// 4. 查
listHeroNode(head)
// 删
fmt.Println("删除操作")
deleteById(head, 3)
listHeroNode(head)
// 改
fmt.Println("更新操作")
// 6. 改
heroUpdate := &heroNode{
number: 2,
name: "林不冲",
nickname: "狮子头",
}
update(head, heroUpdate)
listHeroNode(head)
}
循环链表
无头无尾，首节点和末节点连接在一起
循环链表实现
给循环链表新增节点
删除循环链表中指定节点
更新循环链表中指定节点
查询循环链表中所有节点信息
- 原文作者：zhutou
- 原文链接：https://flygar.org/2020/03/21/golang-.html
- 版权声明：本作品采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可，非商业转载请注明出处（作者，原文链接），商业转载请联系作者获得授权。
