深入探讨Go语言中的双向链表

简介

双向链表是链表家族中的一种高级结构，每个节点不仅指向下一个节点，还指向上一个节点。今天，我们将学习如何在Go语言中实现和操作这种灵活的数据结构。

双向链表的优缺点

• 优点：

  • 可以从任一方向遍历链表，灵活性高。
  • 插入和删除操作非常高效，因为可以轻松地调整前后节点的链接。
  • 可以在不遍历整个链表的情况下访问特定位置的节点。

• 缺点：

  • 需要额外的内存来存储两个指针，占用内存较大。
  • 比单链表实现复杂，代码量更多。

代码实现

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

// -------------------------------------------
// @file      : DoubleLinkedList.go
// @author    : Serein
// @contact   : [e-mail]
// @blog      : https://blog.childish.vip
// @time      : 2024/12/3 20:55:58 星期二
// -------------------------------------------package mainimport ("fmt"
)// 双链表// DoubleListNode 节点结构体定义
// 每个节点包含一个值（Val），以及指向前后节点的指针（Prev 和 Next）
type DoubleListNode struct {Val  int             // 节点的值Prev *DoubleListNode // 指向前一个节点的指针Next *DoubleListNode // 指向后一个节点的指针
}// DoubleLinkList 双链表结构体定义
// 双链表包含头节点（Head）和尾节点（Tail）
type DoubleLinkList struct {Head *DoubleListNode // 链表头部指针Tail *DoubleListNode // 链表尾部指针
}// NewDoubleLinkList 初始化双链表函数
// 创建一个空链表，返回其指针
func NewDoubleLinkList() *DoubleLinkList {return &DoubleLinkList{Head: nil, Tail: nil} // 初始化头尾指针为nil，表示空链表
}// insertNode 通用的插入节点函数，既可以在头部插入，也可以在尾部插入
// 该函数可以在头部或尾部插入节点，atHead参数控制插入位置
func (l *DoubleLinkList) insertNode(val int, atHead bool) {newNode := &DoubleListNode{Val: val}// 如果链表为空，新节点就是头部也是尾部if l.Head == nil {newNode.Prev = nil // 新节点没有前驱newNode.Next = nil // 新节点没有后继l.Head = newNode   // 头部指向新节点l.Tail = newNode   // 尾部指向新节点return}// 如果在头部插入if atHead {newNode.Next = l.Head // 新节点的 Next 指向当前头节点newNode.Prev = nil    // 新节点没有前驱节点l.Head.Prev = newNode // 当前节点的前驱指向新节点l.Head = newNode      // 跟新头部节点为新指针} else {// 在尾部插入newNode.Prev = l.Tail // 新节点的 Prev 指向当前节点newNode.Next = nil    // 新节点没有后继节点l.Tail.Next = newNode // 当前尾节点的 Next 指向新节点l.Tail = newNode      // 跟新尾节点尾新节点}
}// InsertAtHead 在头部插入节点操作
// 通过调用通用的插入函数，指定在头部插入
func (l *DoubleLinkList) InsertAtHead(val int) {l.insertNode(val, true) // 在头部插入节点
}// InsertAtTail 在尾部插入节点
// 通过调用通用的插入函数，指定在尾部插入
func (l *DoubleLinkList) InsertAtTail(val int) {l.insertNode(val, false) // 在尾部插入节点
}// InsertAtRandomPosition 在随机位置插入节点函数
// 如果位置超出了链表长度，则在尾部插入
func (l *DoubleLinkList) InsertAtRandomPosition(pos int, val int) {// 如果位置小于0，或者链表为空，直接在头部插入if pos <= 0 || l.Head == nil {l.InsertAtHead(val)return}// 计算链表的长度length := 0current := l.Headfor current != nil {length++ // 遍历链表，计算长度current = current.Next}// 如果位置超出了链表的长度，就在尾部插入if pos >= length {l.InsertAtTail(val)return}// 遍历链表，找到指定位置的前一个节点current = l.Headfor i := 0; i < pos-1; i++ {current = current.Next}// 在指定位置插入节点newNode := &DoubleListNode{Val: val} // 创建新节点newNode.Next = current.Next          // 新节点的 Next 指向当前节点的 NextnewNode.Prev = current               // 新节点的 Prev 指向当前节点current.Next.Prev = newNode          // 当前节点的 Next 节点的Prev指向信介蒂纳current.Next = newNode               // 当前节点的 Next 指向新节点
}// DeleteAtPosition 删除指定位置的节点
// 如果链表为空或者位置无效（小于0），则不进行任何操作
func (l *DoubleLinkList) DeleteAtPosition(pos int) {// 如果链表为空或删除位置无效，直接返回if l.Head == nil || pos < 0 {return}// 如果删除的是头节点（位置为0）if pos == 0 {l.Head = l.Head.Next // 更新头节点为当前节点的下一个节点if l.Head != nil {   // 如果新的头节点不为空l.Head.Prev = nil // 清空新的头节点的前驱节点}return}// 初始化当前节点为头节点current := l.Head// 遍历链表，找到要删除节点的位置for i := 0; current != nil && i < pos; i++ {current = current.Next // 移动到下一个节点}// 如果当前节点为空，说明位置超出了链表的范围，直接驳回if current == nil {return}// 如果删除的是尾节点if current.Next == nil {// 将当前节点的前一个节点的 Next 指向nil，断开尾节点current.Prev.Next = nil} else {// 删除的是中间节点或非尾节点，调整前后节点的指针current.Prev.Next = current.Next // 当前节点的前一个节点指向当前节点的下一个节点current.Next.Prev = current.Prev // 当前节点的下一个节点的前驱指向当前节点的前一个节点}// 清理当前节点的指针（帮助垃圾回收）current.Next = nil // 当前节点的 Next 指针指向 nilcurrent.Prev = nil // 当前节点的 Prev 指针指向 nil
}// traverseList 遍历链表的函数
// 根据reverse的值决定遍历方向，并执行给定的操作action
// reverse为true时，从尾到头遍历；为false时，从头到尾遍历
func (l *DoubleLinkList) traverseList(reverse bool, action func(*DoubleListNode)) {// 如果链表为空，打印提示信息if l.Head == nil {fmt.Println("链表为空")return}// 定义当前节点，初始化为头部节点current := l.Head// 如果 reverse 为 true ,说明要尾部遍历if reverse {current = l.Tail // 从尾部遍历for {action(current)        // 执行传入的操作current = current.Prev // 移动到前一个节点if current == nil {    // 如果当前节点为nil，表示遍历结束break}}} else {// 从头部开始遍历for {action(current)        // 执行传入的操作current = current.Next // 移动到下一个节点if current == nil {    // 如果当前节点为nil,便是遍历结束break}}}
}// PrintListForward 打印双链表元素（从前向后）操作
// 调用traverseList遍历链表，并打印每个节点的值
func (l *DoubleLinkList) PrintListForward() {l.traverseList(false, func(node *DoubleListNode) {fmt.Println(node.Val) // 打印节点的值})
}// PrintListBackward 打印双链表元素（从后向前）操作
// 调用traverseList遍历链表，并打印每个节点的值
func (l *DoubleLinkList) PrintListBackward() {l.traverseList(true, func(node *DoubleListNode) {fmt.Println(node.Val) // 打印节点的值})
}func main() {doubleList := NewDoubleLinkList()doubleList.InsertAtHead(1)doubleList.InsertAtHead(2)doubleList.InsertAtTail(3)doubleList.InsertAtTail(4)doubleList.InsertAtRandomPosition(2, 5)doubleList.PrintListForward()fmt.Println("-------------")doubleList.PrintListBackward()doubleList.DeleteAtPosition(2)fmt.Println("----------------")doubleList.PrintListForward()}

关键点解析

• 节点结构体：DoubleListNode定义了每个节点的结构，包含一个值Val，一个指向前节点的指针Prev和一个指向后节点的指针Next。
• 链表结构体：DoubleLinkList使用Head和Tail指针来管理整个链表，这使得对头尾的操作变得简便。
• 初始化：NewDoubleLinkList函数返回一个空的双向链表。
• 插入操作：
  • InsertAtHead和InsertAtTail方法简化了在链表的头部或尾部插入新节点的操作。
  • InsertAtRandomPosition允许我们在链表的指定位置插入节点，提供了高度的灵活性。
• 删除操作：DeleteAtPosition展示了如何删除指定位置的节点，并处理了头节点、尾节点以及中间节点的删除逻辑。
• 遍历：
  • traverseList函数可以根据reverse参数决定遍历方向，并通过回调函数action执行指定操作。
  • PrintListForward和PrintListBackward方法分别用于打印链表的正向和反向节点值。

运行和测试

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

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

总结

通过这个实现，我们学习了如何在Go中构建和操作双向链表。双向链表在很多情况下优于单向链表，因为它提供了双向遍历的能力以及更灵活的插入和删除操作。Go语言的简单语法使得这些操作的实现变得直观和高效。

实际应用

• LRU缓存：双向链表可以有效地实现LRU（最近最少使用）缓存策略。
• 文件系统：操作系统中文件系统的目录结构可以使用双向链表来实现。
• 浏览器历史记录：浏览器的前进和后退功能可以用双向链表实现。

---