当前位置：首页 > news >正文

探索Go语言中的循环双向链表

news 来源：原创 2025/5/14 22:14:30

简介

循环双向链表将双向链表的灵活性与循环结构相结合，使得每个节点都有一个指向前一个节点和后一个节点的指针，并且最后一个节点的Next指针指向头节点，形成一个闭环。本文将深入探讨如何在Go语言中实现和操作这种数据结构。

循环双向链表的优点

双向遍历：可以从任一方向遍历链表，使得操作更加灵活。
高效插入删除：由于可以从两个方向操作，插入和删除节点的效率非常高。
循环结构：循环特性使链表的尾部和头部相连，适用于需要循环遍历的情况。

代码实现

下面是我们在Go中实现循环双向链表的完整代码：

// -------------------------------------------
// @file      : CircularDoubleLinkedList.go
// @author    : Serein
// @contact   : xming9523@gmail.com
// @blog      : https://blog.childish.vip
// @time      : 2024/12/3 22:38:10 星期二
// -------------------------------------------package mainimport "fmt"// 循环双链表// CircularDoubleListNode 节点结构体定义
type CircularDoubleListNode struct {Val  int                     // 节点的值Prev *CircularDoubleListNode // 前一个节点指针Next *CircularDoubleListNode // 后一个节点指针
}// CircularDoubleLinkedList 循环双链表结构体定义
type CircularDoubleLinkedList struct {Head *CircularDoubleListNode // 头节点指针Tail *CircularDoubleListNode // 尾节点指针
}// newCircularDoubleLinkedList 初始化循环双链表函数
// 该函数会创建一个空的循环双链表，并初始化Head为nil
func newCircularDoubleLinkedList() *CircularDoubleLinkedList {return &CircularDoubleLinkedList{Head: nil} // 返回一个空的链表结构
}// insertNode 在链表的头部或尾部插入新节点
// atHead 为 true 时，表示在头部插入；否则，在尾部插入
func (l *CircularDoubleLinkedList) insertNode(val int, atHead bool) {// 创建新节点newNode := &CircularDoubleListNode{Val: val}// 如果链表为空时if l.Head == nil {// 新节点指向自己，成为唯一节点newNode.Prev = newNodenewNode.Next = newNode// 将头和尾部指向新节点l.Head = newNodel.Tail = newNodereturn}if atHead {// 在头部插入newNode.Next = l.Head // 新节点的 next 指向当前头节点newNode.Prev = l.Tail // 新节点的 prev 指向尾节点l.Head.Prev = newNode // 原头节点的 prev 指向新节点l.Tail.Next = newNode // 尾节点的 next 指向新节点l.Head = newNode      // 更新头节点为新节点} else {// 在尾部插入newNode.Next = l.Head // 新节点的 next 指向头节点newNode.Prev = l.Tail // 新节点的 prev 指向尾节点l.Tail.Next = newNode // 尾节点的 next 指向新节点l.Head.Prev = newNode // 头节点的 prev 指向新节点l.Tail = newNode      // 更新尾节点为新节点}
}// InsertAtHead 在头部插入节点操作
// 包装了 InsertNode 方法，将 atHead 设置为 true，表示在头部插入
func (l *CircularDoubleLinkedList) InsertAtHead(val int) {l.insertNode(val, true)
}// InsertAtTail 在尾部插入节点操作
// 包装了 InsertNode 方法，将 atHead 设置为 false，表示在头部插入
func (l *CircularDoubleLinkedList) InsertAtTail(val int) {l.insertNode(val, false)
}// InsertAtRandomPosition 在随机位置插入节点函数
// pos 为插入位置，val 为要插入的值
func (l *CircularDoubleLinkedList) InsertAtRandomPosition(pos int, val int) {// 如果位置小于0，或者链表为空，直接在头部插入if l.Head == nil || pos <= 0 { // 检查链表是否为空或位置不合法l.InsertAtHead(val) // 在头部插入新节点return              // 结束函数}// 查找链表长度length := 0current := l.Headfor {length++               // 增加长度计数器current = current.Next // 移动到下一个节点if current == l.Head { // 如果回到头节点，说明遍历完了整个链表break // 结束循环}}// 如果插入位置大于链表长度，插入尾部if pos >= length { // 检查插入位置是否超出了链表长度l.InsertAtTail(val) // 在尾部插入新节点return              // 结束函数}// 从头节点开始遍历链表，找到目标位置current = l.Headfor i := 0; i < pos-1; i++ { // 遍历到插入位置的前一个节点current = current.Next // 移动到下一个节点}// 插入指定位置newNode := &CircularDoubleListNode{Val: val} // 创建新节点newNode.Next = current.Next                  // 新节点的 next 指向当前节点的下一个节点newNode.Prev = current                       // 新节点的 prev 指向当前节点current.Next.Prev = newNode                  // 当前节点的下一个节点的 prev 指向新节点current.Next = newNode                       // 当前节点的 next 指向新节点
}// traverseList 遍历链表并执行给定的操作
func (l *CircularDoubleLinkedList) traverseList(reverse bool, action func(*CircularDoubleListNode)) {// 如果链表为空if l.Head == nil {fmt.Println("链表为空")return}current := l.Head // 初始化当前节点为头节点if reverse {      // 如果是反向遍历// 从尾部开始遍历current = l.Tailfor {action(current)        // 执行指定操作current = current.Prev // 移动到前一个节点if current == l.Tail { // 回到尾节点时结束循环break}}} else {// 从头部开始遍历for {action(current)        // 执行指定操作current = current.Next // 移动到下一个节点if current == l.Head { // 回到头节点时结束循环break}}}
}// PrintListForward 打印循环双链表(从前往后)操作
func (l *CircularDoubleLinkedList) PrintListForward() {l.traverseList(false, func(node *CircularDoubleListNode) {fmt.Println(node.Val) // 打印每个节点的值})
}// PrintListBackward 打印循环双链表(从后往前)操作
func (l *CircularDoubleLinkedList) PrintListBackward() {l.traverseList(true, func(node *CircularDoubleListNode) {fmt.Println(node.Val) // 打印每个节点的值})
}
func main() {circularDoubleList := newCircularDoubleLinkedList()circularDoubleList.InsertAtHead(1)circularDoubleList.InsertAtTail(2)circularDoubleList.InsertAtHead(3)circularDoubleList.InsertAtTail(4)circularDoubleList.InsertAtRandomPosition(2, 5)circularDoubleList.PrintListForward()fmt.Println("----------------")circularDoubleList.PrintListBackward()
}

关键点解析

节点结构体：CircularDoubleListNode定义了每个节点的结构，包含值Val，前一个节点指针Prev和后一个节点指针Next。
链表结构体：CircularDoubleLinkedList使用Head和Tail指针管理链表，但由于循环特性，通常只需要维护一个即可。
初始化：newCircularDoubleLinkedList函数返回一个空的循环双向链表。
插入操作：
- insertNode是一个通用插入函数，可以在链表的头部或尾部插入新节点。
- InsertAtHead和InsertAtTail简化了在头部和尾部的插入操作。
- InsertAtRandomPosition允许我们在指定位置插入新节点。
遍历：
- traverseList函数支持从两个方向遍历链表，根据reverse参数决定遍历方向，并通过回调函数action执行指定操作。
- PrintListForward和PrintListBackward方法分别用于打印链表的正向和反向节点值。

运行和测试

在main函数中，我们展示了如何创建一个循环双向链表，插入节点，并从两个方向遍历打印链表：

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

总结

通过这个实现，我们学习了如何在Go中构建和操作一个循环双向链表。这种数据结构在某些情况下比单向链表或普通双向链表更有用，特别是在需要循环访问或双向操作的情况下。Go语言的简洁性使得这些操作的实现变得直观和高效。

实际应用

循环缓冲区：用于数据流、音乐播放等需要循环访问的场景。
操作系统调度：轮转调度算法可以用循环双向链表实现。
缓存系统：LRU缓存可以利用循环双向链表进行实现。

简介

循环双向链表的优点

代码实现

关键点解析

运行和测试

总结

实际应用

相关文章：