单链表在Go语言中的实现与操作

简介

单链表是一种基本的线性数据结构，由节点组成，每个节点存储数据和指向下一个节点的指针。今天，我们将深入探讨如何在Go语言中实现和操作单链表。

单链表的优缺点

• 优点：

  • 动态内存分配，灵活性高。
  • 插入和删除节点操作在时间复杂度上比数组更优。

• 缺点：

  • 访问元素需要顺序遍历，时间复杂度为O(n)。
  • 占用额外的内存来存储指针。

代码实现

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

// -------------------------------------------
// @file      : SingleLinkedList.go
// @author    : Serein
// @contact   : [e-mail]
// @blog      : https://blog.childish.vip
// @time      : 2024/12/3 20:33:32 星期二
// -------------------------------------------package mainimport "fmt"// 单链表// ListNode 节点结构体定义
type ListNode struct {Val  int       // 节点的值Next *ListNode // 指向下一个节点的指针
}// SingleLinkedList 单链表结构体定义
type SingleLinkedList struct {Head *ListNode // 链表的头节点Tail *ListNode // 链表的尾节点
}// NewSingleLinkedList 初始化单链表函数
func NewSingleLinkedList() *SingleLinkedList {// 初始化时，链表为空return &SingleLinkedList{Head: nil, Tail: nil}
}// insertNode 插入节点的通用方法
func (l *SingleLinkedList) insertNode(val int, atHead bool) {newNode := &ListNode{Val: val} // 创建一个新节点// 如果链表为空if l.Head == nil {l.Head = newNodel.Tail = newNode // 头部和尾部都指向新节点return}// 如果要在头部插入if atHead {newNode.Next = l.Head // 新节点的 Next 指向源头部节点l.Head = newNode      // 跟新头部节点} else {// 如果要在尾部插入l.Tail.Next = newNode // 当前尾节点的 Next 指向新节点l.Tail = newNode      // 更新尾节点}
}// InsertAtHead 在头部插入节点操作
func (l *SingleLinkedList) InsertAtHead(val int) {l.insertNode(val, true) // 调用insertNode,在头部插入
}// 在尾部插入节点操作
func (l *SingleLinkedList) InsertAtTail(val int) {l.insertNode(val, false) // 调用insertNode，在尾部插入
}// InsertAtRandomPosition 在指定位置插入节点
func (l *SingleLinkedList) 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 := &ListNode{Val: val}newNode.Next = current.Next // 新节点的 Next 指向原来的节点current.Next = newNode      // 将原位置的节点的 Next 指向新节点}func (l *SingleLinkedList) DeleteAtPosition(pos int) {// 如果链表为空或删除位置无效，直接返回if l.Head == nil || pos < 0 {return}// 如果删除的是头节点if pos == 0 {l.Head = l.Head.Next // 新节点更新为原头节点的下一个位置if l.Head == nil {l.Tail = nil // 如果删除后链表为空，则尾节点也置空}return}// 初始化当前节点为头节点current := l.Headfor i := 0; current != nil && i < pos-1; i++ {current = current.Next // 移动到要删除节点的前一个节点去}// 如果当前节点为空，说明位置超出了链表的范围，直接返回if current == nil || current.Next == nil {return}// 如果删除的是尾节点if current.Next == l.Tail {l.Tail = current // 更新尾节点}// 删除当前节点的下一个节点current.Next = current.Next.Next}// 打印单链表操作
func (l *SingleLinkedList) PrintList() {current := l.Headfor current != nil {fmt.Println(current.Val)current = current.Next}}func main() {singList := NewSingleLinkedList()singList.InsertAtHead(2)singList.InsertAtTail(3)singList.InsertAtHead(1)singList.InsertAtRandomPosition(2, 4)singList.PrintList()singList.DeleteAtPosition(2)fmt.Println("删除2节点后")singList.PrintList()}

关键点解析

• 节点结构体：ListNode定义了节点的结构，包含数据Val和指向下一个节点的指针Next。
• 链表结构体：SingleLinkedList用Head和Tail指针来管理链表，这简化了对头部和尾部的操作。
• 初始化：NewSingleLinkedList函数返回一个空的单链表。
• 插入操作：
  • InsertAtHead和InsertAtTail方法简化了在头部或尾部插入新节点的操作。
  • InsertAtRandomPosition允许我们在链表的指定位置插入节点。
• 删除操作：DeleteAtPosition展示了如何删除指定位置的节点，并处理了特殊情况，如删除头节点或尾节点。
• 打印链表：PrintList方法遍历并打印链表中的每个节点值。

运行和测试

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

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

总结

通过这个实现，我们学习了如何在Go中构建和操作一个单链表。尽管单链表在某些方面比数组或双向链表更受限制，但在内存效率和操作简便性上，它仍然是一个有价值的数据结构。Go语言的简单语法使得这些操作变得直观而高效。

实际应用

• 缓存机制：单链表可以实现LRU（最近最少使用）缓存。
• 任务队列：在事件驱动的系统中，任务可以按顺序存储在单链表中。
• 符号表：在编译器设计中，单链表用于实现符号表。

---