Go 结构体链表
链表结构
1. 定义
链表是一种线性数据结构，由一系列节点组成，每个节点包含两个部分：数据部分和指向下一个节点的指针（或引用）部分。链表的第一个节点称为头节点（head），最后一个节点的指针指向空（null）。
2. 类型
- 单链表：每个节点指向下一个节点。
- 双链表：每个节点有两个指针，分别指向前一个节点和后一个节点。
- 循环链表：最后一个节点指向头节点，形成一个环。
链表的优缺点
优点
- 动态内存分配：链表不需要预先分配固定大小的内存，节点可以在需要时动态创建，内存利用率更高。
- 插入和删除操作高效：在链表中插入和删除节点的操作只需要改变指针，时间复杂度为 O(1)。相比之下，数组需要移动元素，时间复杂度为 O(n)。
- 灵活性：链表的大小可以根据需要动态变化，非常适合需要频繁插入和删除操作的场景。
缺点
- 随机访问效率低：由于链表不支持下标访问，要访问某个节点只能从头节点开始逐个遍历，时间复杂度为 O(n)。
- 额外的内存开销：每个节点除了存储数据外，还需要存储指向下一个节点的指针，这会增加额外的内存消耗。
- 缓存性能差：链表节点在内存中通常是离散存储的，缺乏局部性，会导致缓存命中率较低，影响访问性能。
使用场景
- 需要频繁插入和删除的场景：例如实现队列、栈等数据结构。
- 不确定数据大小的场景：例如动态集合。
- 内存管理需要灵活的场景：例如实现链表分配器（linked list allocator）。
单项链表的基本操作
image-20240713181145134使用 struct 定义单链表
假设我们有一个结构体 Student：
type Student struct {
Name string
Age int
Score float64
}1.使用变量声明结构体
直接声明一个结构体变量：
代码语言：javascript复制 var stu Student这种方式 stu 是一个 Student 类型的变量，不是指针。
2. 使用 new 函数创建结构体指针
代码语言：javascript复制 var stu *Student = new(Student)这种方式 stu 是一个指向 Student 类型的指针，new 函数会分配内存并返回指向该类型的新零值指针。
3. 使用取地址符 & 创建结构体指针
代码语言：javascript复制 var stu *Student = &Student{}这种方式 stu 是一个指向 Student 类型的指针，通过 &Student{} 创建一个 Student 实例并返回其地址。
访问结构体字段
无论是通过结构体变量还是指针，我们都可以访问结构体的字段。
1. 直接通过结构体变量访问字段
代码语言：javascript复制 var stu Student
stu.Name = "John"
stu.Age = 20
stu.Score = 90.52. 通过结构体指针访问字段
使用指针访问字段有两种方式：
- 使用简便的点运算符：
var stu *Student = new(Student)
stu.Name = "John" // 等同于 (*stu).Name
stu.Age = 20 // 等同于 (*stu).Age
stu.Score = 90.5 // 等同于 (*stu).Score- 显式解引用：
(*stu).Name = "John"
(*stu).Age = 20
(*stu).Score = 90.5定义一个单项链表
next 是指针类型的属性，指向 Student struct 类型数据，也就是下一个节点的数据类型
type Student struct {
Name string
Age int
Score float32
next *Student
}完整代码
代码语言：javascript复制type Student struct {
Name string
Age int
Score float32
next *Student //存放下一个结构体的地址，用*直接指向下一个结构体
}
func main() {
//头部结构体
var head Student
head.Name = "王五"
head.Age = 20
head.Score = 78
//第二个结构体节点
var stu1 Student
stu1.Name = "小张"
stu1.Age = 2
stu1.Score = 1
head.next = &stu1
//第三个结构体节点
var stu2 Student
stu2.Name = "王五"
stu2.Age = 18
stu2.Score = 60
stu1.next = &stu2
Req(&head)
}
func Req(tmp *Student) { //tmp指针是指向下一个结构体的地址，加*就是下一个结构体
for tmp != nil { //遍历输出链表中每个结构体，判断是否为空
fmt.Println(*tmp)
tmp = tmp.next //tmp变更为下一个结构体地址
}
}尾部添加节点
代码语言：javascript复制package main
import (
"fmt"
"math/rand"
)
type Student struct {
Name string
Age int
Score float32
next *Student
}
// AppendNode adds a new student to the end of the linked list
func AppendNode(head *Student, newNode *Student) {
// Traverse to the end of the list
current := head
for current.next != nil {
current = current.next
}
// Add the new node at the end
current.next = newNode
}
func main() {
// Initialize head node
var head Student
head.Name = "head"
head.Age = 28
head.Score = 88
// Initialize subsequent nodes and append them to the list
nodes := []Student{
{Name: "stu1", Age: 25, Score: 100},
{Name: "stu2", Age: 18, Score: 60},
{Name: "stu3", Age: 18, Score: 80},
}
for _, node := range nodes {
AppendNode(&head, &node)
}
// Dynamically create and append more nodes
for i := 4; i < 10; i {
stu := &Student{
Name: fmt.Sprintf("stu%d", i),
Age: rand.Intn(100),
Score: rand.Float32() * 100,
}
AppendNode(&head, stu)
}
// Print the linked list
Req(&head)
}
// Req traverses and prints the linked list
func Req(tmp *Student) {
for tmp != nil {
fmt.Println(*tmp)
tmp = tmp.next
}
}头部插入节点
代码语言：javascript复制package main
import (
"fmt"
"math/rand"
)
type Student struct {
Name string
Age int
Score float32
next *Student
}
// PrependNode adds a new student to the beginning of the linked list
func PrependNode(head **Student, newNode *Student) {
newNode.next = *head
*head = newNode
}
func main() {
// Initialize head node
head := &Student{
Name: "head",
Age: 28,
Score: 88,
}
// Initialize subsequent nodes and prepend them to the list
nodes := []Student{
{Name: "stu1", Age: 25, Score: 100},
{Name: "stu2", Age: 18, Score: 60},
{Name: "stu3", Age: 18, Score: 80},
}
for _, node := range nodes {
newNode := node // Make a copy to avoid pointer issues
PrependNode(&head, &newNode)
}
// Dynamically create and prepend more nodes
for i := 4; i < 10; i {
stu := &Student{
Name: fmt.Sprintf("stu%d", i),
Age: rand.Intn(100),
Score: rand.Float32() * 100,
}
PrependNode(&head, stu)
}
// Print the linked list
Req(head)
}
// Req traverses and prints the linked list
func Req(tmp *Student) {
for tmp != nil {
fmt.Println(*tmp)
tmp = tmp.next
}
}指定节点后添加新节点
代码语言：javascript复制package main
import (
"fmt"
"math/rand"
)
type Student struct {
Name string
Age int
Score float32
next *Student
}
// InsertNode inserts a new student after the specified node in the linked list
func InsertNode(head *Student, targetName string, newNode *Student) {
current := head
for current != nil {
if current.Name == targetName {
newNode.next = current.next
current.next = newNode
return
}
current = current.next
}
fmt.Printf("Node with name %s not foundn", targetName)
}
func main() {
// Initialize head node
head := &Student{
Name: "head",
Age: 28,
Score: 88,
}
// Initialize subsequent nodes and append them to the list
nodes := []Student{
{Name: "stu1", Age: 25, Score: 100},
{Name: "stu2", Age: 18, Score: 60},
{Name: "stu3", Age: 18, Score: 80},
}
// Append nodes to the list
current := head
for i := range nodes {
current.next = &nodes[i]
current = &nodes[i]
}
// Dynamically create and append more nodes
for i := 4; i < 6; i {
stu := &Student{
Name: fmt.Sprintf("stu%d", i),
Age: rand.Intn(100),
Score: rand.Float32() * 100,
}
current.next = stu
current = stu
}
// Insert a new node after "stu2"
newNode := &Student{
Name: "newStu",
Age: 22,
Score: 75,
}
InsertNode(head, "stu2", newNode)
// Print the linked list
Req(head)
}
// Req traverses and prints the linked list
func Req(tmp *Student) {
for tmp != nil {
fmt.Println(*tmp)
tmp = tmp.next
}
}删除节点
代码语言：javascript复制package main
import (
"fmt"
"math/rand"
)
type Student struct {
Name string
Age int
Score float32
next *Student
}
// DeleteNode removes the student with the specified name from the linked list
func DeleteNode(head **Student, targetName string) {
current := *head
var prev *Student = nil
// If head needs to be removed
if current != nil && current.Name == targetName {
*head = current.next
return
}
// Search for the target node to delete
for current != nil && current.Name != targetName {
prev = current
current = current.next
}
// If the target node was not found
if current == nil {
fmt.Printf("Node with name %s not foundn", targetName)
return
}
// Remove the target node
prev.next = current.next
}
func main() {
// Initialize head node
head := &Student{
Name: "head",
Age: 28,
Score: 88,
}
// Initialize subsequent nodes and append them to the list
nodes := []Student{
{Name: "stu1", Age: 25, Score: 100},
{Name: "stu2", Age: 18, Score: 60},
{Name: "stu3", Age: 18, Score: 80},
}
// Append nodes to the list
current := head
for i := range nodes {
current.next = &nodes[i]
current = &nodes[i]
}
// Dynamically create and append more nodes
for i := 4; i < 6; i {
stu := &Student{
Name: fmt.Sprintf("stu%d", i),
Age: rand.Intn(100),
Score: rand.Float32() * 100,
}
current.next = stu
current = stu
}
// Delete a node with name "stu2"
DeleteNode(&head, "stu2")
// Print the linked list
Req(head)
}
// Req traverses and prints the linked list
func Req(tmp *Student) {
for tmp != nil {
fmt.Println(*tmp)
tmp = tmp.next
}
}
