Go 结构体链表

原创

f1sh

发布于 2024-07-17 16:25:01

870

发布于 2024-07-17 16:25:01

Go 结构体链表

链表结构

1. 定义

链表是一种线性数据结构，由一系列节点组成，每个节点包含两个部分：数据部分和指向下一个节点的指针（或引用）部分。链表的第一个节点称为头节点（head），最后一个节点的指针指向空（null）。

2. 类型

单链表：每个节点指向下一个节点。
双链表：每个节点有两个指针，分别指向前一个节点和后一个节点。
循环链表：最后一个节点指向头节点，形成一个环。

链表的优缺点

优点

动态内存分配：链表不需要预先分配固定大小的内存，节点可以在需要时动态创建，内存利用率更高。
插入和删除操作高效：在链表中插入和删除节点的操作只需要改变指针，时间复杂度为 O(1)。相比之下，数组需要移动元素，时间复杂度为 O(n)。
灵活性：链表的大小可以根据需要动态变化，非常适合需要频繁插入和删除操作的场景。

缺点

随机访问效率低：由于链表不支持下标访问，要访问某个节点只能从头节点开始逐个遍历，时间复杂度为 O(n)。
额外的内存开销：每个节点除了存储数据外，还需要存储指向下一个节点的指针，这会增加额外的内存消耗。
缓存性能差：链表节点在内存中通常是离散存储的，缺乏局部性，会导致缓存命中率较低，影响访问性能。

使用场景

需要频繁插入和删除的场景：例如实现队列、栈等数据结构。
不确定数据大小的场景：例如动态集合。
内存管理需要灵活的场景：例如实现链表分配器（linked list allocator）。

单项链表的基本操作

使用 struct 定义单链表

假设我们有一个结构体 Student：

 type Student struct {
     Name  string
     Age   int
     Score float64
 }

1.使用变量声明结构体

直接声明一个结构体变量：

 var stu Student

这种方式 stu 是一个 Student 类型的变量，不是指针。

2. 使用 `new` 函数创建结构体指针

 var stu *Student = new(Student)

这种方式 stu 是一个指向 Student 类型的指针，new 函数会分配内存并返回指向该类型的新零值指针。

3. 使用取地址符 `&` 创建结构体指针

 var stu *Student = &Student{}

这种方式 stu 是一个指向 Student 类型的指针，通过 &Student{} 创建一个 Student 实例并返回其地址。

访问结构体字段

无论是通过结构体变量还是指针，我们都可以访问结构体的字段。

1. 直接通过结构体变量访问字段

 var stu Student
 stu.Name = "John"
 stu.Age = 20
 stu.Score = 90.5

2. 通过结构体指针访问字段

使用指针访问字段有两种方式：

使用简便的点运算符：

 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
 }

完整代码

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变更为下一个结构体地址
	}
}

尾部添加节点

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
	}
}

头部插入节点

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
	}
}

指定节点后添加新节点

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 found\n", 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
	}
}

删除节点

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 found\n", 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
	}
}

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

登录后参与评论

0 条评论

热度

Go 结构体链表

Go 结构体链表

Go 结构体链表

链表结构

1. 定义

2. 类型

链表的优缺点

优点

缺点

使用场景

单项链表的基本操作

使用 struct 定义单链表

1.使用变量声明结构体

2. 使用 `new` 函数创建结构体指针

3. 使用取地址符 `&` 创建结构体指针

访问结构体字段

1. 直接通过结构体变量访问字段

2. 通过结构体指针访问字段

定义一个单项链表

完整代码

尾部添加节点

头部插入节点

指定节点后添加新节点

删除节点

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

Go 结构体链表

Go 结构体链表

Go 结构体链表

链表结构

1. 定义

2. 类型

链表的优缺点

优点

缺点

使用场景

单项链表的基本操作

使用 struct 定义单链表

1.使用变量声明结构体

2. 使用 new 函数创建结构体指针

3. 使用取地址符 & 创建结构体指针

访问结构体字段

1. 直接通过结构体变量访问字段

2. 通过结构体指针访问字段

定义一个单项链表

完整代码

尾部添加节点

头部插入节点

指定节点后添加新节点

删除节点

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

2. 使用 `new` 函数创建结构体指针

3. 使用取地址符 `&` 创建结构体指针