探索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 mainimport "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.Headfor current.Next != l.Head {length++               // 增加长度计数current = current.Next // 移动到下一个节点}if pos >= length { // 如果位置超过链表长度l.insertNode(pos, false) // 插入尾部return}current = l.Headfor 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 = nill.Tail = nil} else {l.Head = l.Head.Next // 头节点移到下一个节点l.Tail.Next = l.Head // 更新尾节点的下一个节点为新的头节点}return}current := l.Headfor i := 0; current.Next != l.Head && i < pos-1; i++ { // 移动到要删除的节点的前一个节点current = current.Next}if current.Next == l.Head { // 如果到达了链表的末尾，返回return}// 删除节点toDelete := current.Nextcurrent.Next = toDelete.Next // 将当前节点的下一个节点指向删除节点的下一个节点if toDelete.Next == l.Tail { // 如果删除节点是尾节点l.Tail = current // 更新尾节点}}// 打印循环单链表的操作
func (l *CircularLinkList) PrintList() {if l.Head == nil { // 如果链表为空return}current := l.Headfor {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方法用来遍历并打印整个链表。