简介
单链表是一种基本的线性数据结构，由节点组成，每个节点存储数据和指向下一个节点的指针。今天，我们将深入探讨如何在Go语言中实现和操作单链表。
单链表的优缺点
优点：
- 动态内存分配，灵活性高。
- 插入和删除节点操作在时间复杂度上比数组更优。
缺点：
- 访问元素需要顺序遍历，时间复杂度为O(n)。
- 占用额外的内存来存储指针。
代码实现
下面是我们在Go中实现单链表的完整代码：
// -------------------------------------------
// @file : SingleLinkedList.go
// @author : Serein
// @contact : xming9523@gmail.com
// @blog : https://blog.childish.vip
// @time : 2024/12/3 20:33:32 星期二
// -------------------------------------------
package main
import "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 = newNode
l.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 := 0
current := l.Head
for current != nil {
length++
current = current.Next
}
// 如果位置超出链表的长度，就在尾部插入
if pos >= length {
l.InsertAtTail(val) // 在尾部插入
return
}
// 遍历链表，找到指定位置的前一个位置
current = l.Head
for 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.Head
for 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.Head
for 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（最近最少使用）缓存。
- 任务队列：在事件驱动的系统中，任务可以按顺序存储在单链表中。
- 符号表：在编译器设计中，单链表用于实现符号表。