探索Go语言中的循环单链表

🕗 发布于 2024-12-05 12:48 开发语言 后端 数据结构 go

简介

循环单链表是一种特殊的链表数据结构，它的最后一个节点指向链表的头节点，形成一个闭环。今天我们将探讨如何在Go语言中实现和操作这种数据结构。

为什么选择循环单链表？

连续访问：在循环单链表中，可以无限循环地遍历数据元素，这在某些应用场景下非常有用，例如游戏中的无限滚动背景或队列管理。
内存效率：由于循环特性，链表的尾节点可以直接链接到头节点，无需额外的指针或标记。

代码实现

以下是我们在Go中实现循环单链表的完整代码：

// -------------------------------------------
// @file      : CircularLinkedList.go
// @author    : Serein
// @contact   : xming9523@gmail.com
// @blog      : https://blog.childish.vip
// @time      : 2024/12/3 21:15:22 星期二
// -------------------------------------------

package main

import "fmt"

// 循环单链表

// CircularListNode 节点结构体定义
type CircularListNode struct {
Val  int               // 节点的值
Next *CircularListNode // 指向下一个节点的指针
}

// CircularLinkList 循环单链表结构体定义
type CircularLinkList struct {
Head *CircularListNode // 链表的头节点
Tail *CircularListNode // 链表的尾节点
}

// NewCircularLinkList 初始化循环单链表
func NewCircularLinkList() *CircularLinkList {
return &CircularLinkList{Head: nil, Tail: nil} // 返回一个新的空循环链表
}

func (l *CircularLinkList) insertNode(val int, atHead bool) {
newNode := &CircularListNode{Val: val} // 创建一个新的节点
// 如果链表为空
if l.Head == nil {
l.Head = newNode     // 新节点作为头节点
l.Tail = newNode     // 也是尾节点
l.Tail.Next = l.Head // 形成循环
return
}
// 在头部插入节点
if atHead {
newNode.Next = l.Head // 新节点的下一个节点是原来的头节点
l.Head = newNode      // 新节点成为新的头节点
l.Tail.Next = l.Head  // 更新尾节点的下一个节点为新的头节点
} else {
// 在尾部插入节点操作
l.Tail.Next = newNode // 当前尾节点的下一个节点是新节点
l.Tail = newNode      // 新节点成为新的尾节点
l.Tail.Next = l.Head  // 是链表保持循环
}
}

// InsertAtHead 在头部插入节点操作
func (l *CircularLinkList) InsertAtHead(val int) {
l.insertNode(val, true) // 调用通用的插入方法，在头部插入
}

// InsertAtTail 在尾部插入节点操作
func (l *CircularLinkList) InsertAtTail(val int) {
l.insertNode(val, false) // 调用通用的插入方法，在尾部插入
}

// InsertAtRandomPosition 在随机位置插入节点
func (l *CircularLinkList) InsertAtRandomPosition(pos int, val int) {
if pos <= 0 || l.Head == nil { // 如果位置无效和链表为空
l.insertNode(val, true) // 直接插入到头部
return
}

// 计算链表的长度
length := 1 // 初始长度为1，因为至少有一个头节点
current := l.Head
for current.Next != l.Head {
length++               // 增加长度计数
current = current.Next // 移动到下一个节点
}

if pos >= length { // 如果位置超过链表长度
l.insertNode(pos, false) // 插入尾部
return
}

current = l.Head
for i := 0; i < pos-1; i++ {
current = current.Next // 移动到指定位置的前一个节点
}
newNode := &CircularListNode{Val: val} // 创建新节点
newNode.Next = current.Next            // 新节点的下一个节点是当前节点的下一个节点
current.Next = newNode                 // 当前节点的下一个节点指向新节点

}
func (l *CircularLinkList) DeleteAtPosition(pos int) {
if l.Head == nil || pos < 0 { // 如果链表为空或位置无效，直接返回
return
}

// 如果删除的是头节点
if pos == 0 {
if l.Head == l.Tail { // 如果只有一个头节点，就直接把头节点和尾节点置空
l.Head = nil
l.Tail = nil
} else {
l.Head = l.Head.Next // 头节点移到下一个节点
l.Tail.Next = l.Head // 更新尾节点的下一个节点为新的头节点
}
return
}

current := l.Head
for i := 0; current.Next != l.Head && i < pos-1; i++ { // 移动到要删除的节点的前一个节点
current = current.Next
}

if current.Next == l.Head { // 如果到达了链表的末尾，返回
return
}

// 删除节点
toDelete := current.Next
current.Next = toDelete.Next // 将当前节点的下一个节点指向删除节点的下一个节点
if toDelete.Next == l.Tail { // 如果删除节点是尾节点
l.Tail = current // 更新尾节点
}

}

// 打印循环单链表的操作
func (l *CircularLinkList) PrintList() {
if l.Head == nil { // 如果链表为空
return
}
current := l.Head
for {
fmt.Println(current.Val) // 打印当前节点的值
current = current.Next   // 移动到下一个节点
if current == l.Head {   // 如果回到头头节点，循环结束
break
}
}
}

func main() {
circularList := NewCircularLinkList()
circularList.InsertAtHead(1)
circularList.InsertAtTail(2)
circularList.InsertAtHead(3)
circularList.InsertAtTail(4)
circularList.InsertAtRandomPosition(2, 5)
circularList.PrintList()
circularList.DeleteAtPosition(2)
fmt.Println("删除后")
circularList.PrintList()

}

关键点解析

节点结构体：CircularListNode定义了每个节点的结构，包含一个值和一个指向下一个节点的指针。
链表结构体：CircularLinkList使用头指针和尾指针来管理整个链表，确保了操作的效率。
插入操作：通过insertNode方法，我们可以灵活地在链表的头部或尾部插入新节点。InsertAtHead和InsertAtTail方法简化了这个过程。
随机位置插入：InsertAtRandomPosition方法允许我们在一个指定位置插入节点。
删除操作：DeleteAtPosition方法展示了如何删除指定位置的节点，并处理了特殊情况，如删除头节点或尾节点。
打印链表：PrintList方法用来遍历并打印整个链表。

运行和测试

在main函数中，我们展示了如何创建一个循环单链表、插入节点、删除节点以及打印链表的状态：

func main() {
    // ... (代码)
}

总结

通过这个实现，我们了解了如何在Go中构建和操作一个循环单链表。循环单链表虽然在某些方面比普通链表复杂，但在特定应用中，它们提供的优点使其成为值得学习的数据结构。通过代码，我们还展示了Go语言在处理复杂数据结构时的简洁性和高效性。

实际应用

循环调度：如操作系统中的轮转调度算法。
循环缓冲区：如在视频播放或数据流中使用。
游戏开发：例如无限循环的游戏地图。

原文地址：https://blog.csdn.net/2303_76247682/article/details/144251881

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：南京邮电大学《2024年812自动控制原理真题》 (完整版）
下一篇：12.04 深度学习-用CNN做图像分类+训练可视化

.NET(C#) 如何配置用户首选项及保存用户设置
.NET(C#) 如何配置用户首选项及保存用户设置
阅读更多2024-12-14
【最新】北大数字普惠金融指数数据集-省市县（2011-2023年）
郭峰,王靖一,王芳,孔涛,张勋,程志云.测度中国数字普惠金融发展:指数编制与空间特征[J].经济学(季刊),2020,19(04):1401-1418.时间跨度：省级和城市级指数时间跨度为2011-2
阅读更多2024-12-14
GESP202412 四级【Recamán】题解（AC）
a11ak−1−kkakak−1−kak−1k小杨想知道 Recamán 数列的前n项从小到大排序后的结果。手动计算非常困难，小杨希望你能帮他解决这个问题。
阅读更多2024-12-14
IDEA遇到EasyConnect中的网络资源无法访问的问题
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。原文链接：https://blog.csdn.net/wanshanyu_/article/de
阅读更多2024-12-14
双目摄像头标定方法
此时已经完成标定，左下角为反投影误差，右边为外参可视化。将双目左右目拍的图像上传（左右目最好不少于20张）此时回到主页面，即可看到成功导出。把这些误差大的删除即可。
阅读更多2024-12-14
Servlet、omcat服务器架构与工作原理
Servlet是运行在服务器端的Java程序，它的主要职责之一是接收并处理来自客户端（如浏览器）的HTTP请求。当客户端发送一个请求到服务器时，Servlet可以解析请求中的信息，例如请求的URL路径
阅读更多2024-12-14
Vue生命周期钩子函数：深入解析与实践
作为高级Vue前端开发人员，对Vue组件的生命周期钩子函数有着深刻的理解是至关重要的。生命周期钩子函数是指在Vue组件的创建、更新、销毁等过程中，Vue自动调用的一系列方法。通过这些钩子函数，我们可以
阅读更多2024-12-14
安卓开发--使用android studio发布APP
app发布
阅读更多2024-12-14
数据结构与算法学习笔记----拓扑排序
@ author: 明月清了个风。
阅读更多2024-12-14
python 将数据保存到现有的Excel文件的新工作表
out_file = ‘query.xlsx’df1 = pd.DataFrame(out_data)若直接写入：df1.to_excel(out_file, index=False, sheet_n
阅读更多2024-12-14