Go语言学习之链表的使用详解
目录
1. 什么是链表2. 单项链表的基本操作3. 使用 struct 定义单链表4. 尾部添加节点5. 头部插入节点6. 指定节点后添加新节点7. 删除节点1. 什么是链表
链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。
使用链表结构可以避免在使用数组时需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。
链表允许插入和移除表上任意位置上的结点,但是不允许随机存取。
链表有三种类型:单向链表、双向链表、循环链表。
2. 单项链表的基本操作
单向链表中每个结点包含两部分,分别是数据域和指针域,上一个结点的指针指向下一结点,依次相连,形成链表。
链表通过指针将一组零散的内存块串联在一起,这里的内存块称为链表的结点。为了将这些节点给串起来,每个链表的结点除了存储数据之外,还会记录下一个结点的指针(即下一个结点的地址),这个指针称为:后继指针
3. 使用 struct 定义单链表
利用 Struct 可以包容多种数据类型的特性
一个结构体内可以包含若干成员,这些成员可以是基本类型、自定义类型、数组类型,也可以是指针类型。
struct 定义的三种形式,其中2和3都是返回结构体的指针
//定义 var stu Student var stu *Student = new(Student) var stu *Student = &Student {} //调用 stu.Name stu.Age stu.Score 或 (*stu).Name (*stu).Age (*stu).Score
定义一个单项链表
next 是指针类型的属性,指向 Student struct 类型数据,也就是下一个节点的数据类型
type Student struct { Name string Age int Score float32 next *Student }
为链表赋值,并遍历链表中的每个节点
package main import "fmt" type Student struct { Name string Age int Score float32 next *Student //存放下一个结构体的地址,用*直接指向下一个结构体 } func main() { //头部结构体 var head Student head.Name = "张三" head.Age = 28 head.Score = 88 //第二个结构体节点 var stu1 Student stu1.Name = "李四" stu1.Age = 25 stu1.Score = 100 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变更为下一个结构体地址 } } //输出结果如下 {张三 28 88 0xc000114480} {李四 25 100 0xc0001144b0} {王五 18 60}
4. 尾部添加节点
方法一
package main import ( "fmt" "math/rand" ) type Student struct { Name string Age int Score float32 next *Student } func main() { //头部结构体 var head Student head.Name = "head" head.Age = 28 head.Score = 88 //第二个结构体节点 var stu1 Student stu1.Name = "stu1" stu1.Age = 25 stu1.Score = 100 head.next = &stu1 //头部指向第一个结构体 //第三个结构体节点 var stu2 Student stu2.Name = "stu2" stu2.Age = 18 stu2.Score = 60 stu1.next = &stu2 //第一个结构体指向第二个结构体 //第四个结构体节点 var stu3 Student stu3.Name = "stu3" stu3.Age = 18 stu3.Score = 80 stu2.next = &stu3 //第二个结构体指向第三个结构体 //声明变量 var tail = &stu3 for i := 4; i < 10; i++ { //定义节点 var stu Student = Student{ Name: fmt.Sprintf("stu%d", i), Age: rand.Intn(100), Score: rand.Float32() * 100, } //生产结构体串联 tail.next = &stu tail = &stu } Req(&head) } func Req(tmp *Student) { for tmp != nil { fmt.Println(*tmp) tmp = tmp.next } } //输出结果如下 {head 28 88 0xc0001144b0} {stu1 25 100 0xc0001144e0} {stu2 18 60 0xc000114510} {stu3 18 80 0xc000114540} {stu4 81 94.05091 0xc000114570} {stu5 47 43.77142 0xc0001145a0} {stu6 81 68.682304 0xc0001145d0} {stu7 25 15.651925 0xc000114600} {stu8 56 30.091187 0xc000114630} {stu9 94 81.36399}
方法二,使用函数进行优化
package main import ( "fmt" "math/rand" ) type Student struct { Name string Age int Score float32 next *Student } func main() { //头部结构体 var head Student head.Name = "head" head.Age = 28 head.Score = 88 TailInsert(&head) Req(&head) } //循环遍历 func Req(tmp *Student) { for tmp != nil { fmt.Println(*tmp) tmp = tmp.next } } //添加结构体节点 func TailInsert(tail *Student) { for i := 0; i < 10; i++ { //定义节点 var stu Student = Student{ Name: fmt.Sprintf("stu%d", i), Age: rand.Intn(100), Score: rand.Float32() * 100, } //生产结构体串联 tail.next = &stu //指向下一个结构体 tail = &stu //把当前的结构体给tail,让其继续循环 } } //输出结果如下 {head 28 88 0xc0001144b0} {stu0 81 94.05091 0xc0001144e0} {stu1 47 43.77142 0xc000114510} {stu2 81 68.682304 0xc000114540} {stu3 25 15.651925 0xc000114570} {stu4 56 30.091187 0xc0001145a0} {stu5 94 81.36399 0xc0001145d0} {stu6 62 38.06572 0xc000114600} {stu7 28 46.888985 0xc000114630} {stu8 11 29.310184 0xc000114660} {stu9 37 21.855305}
5. 头部插入节点
方法一
package main import ( "fmt" "math/rand" ) type Student struct { Name string Age int Score float32 next *Student } func main() { //头部结构体 var head Student head.Name = "head" head.Age = 28 head.Score = 88 //调用头部插入函数 HeadInsert(&head) Req(HeadInsert(&head)) } func Req(tmp *Student) { for tmp != nil { fmt.Println(*tmp) tmp = tmp.next } } func HeadInsert(p *Student) *Student { for i := 0; i < 10; i++ { var stu = Student{ Name: fmt.Sprintf("stu%d", i), Age: rand.Intn(100), Score: rand.Float32() * 100, } //当前新节点指向head,因为head是下一个节点 stu.next = p //指向下一个节点 p = &stu //把当前的结构体给tail,让其继续循环 } return p } //输出结果如下 {stu9 85 30.152267 0xc000094840} {stu8 37 5.912065 0xc000094810} {stu7 29 7.9453626 0xc0000947e0} {stu6 87 60.72534 0xc0000947b0} {stu5 41 2.8303082 0xc000094780} {stu4 90 69.67192 0xc000094750} {stu3 87 20.658266 0xc000094720} {stu2 47 29.708258 0xc0000946f0} {stu1 28 86.249146 0xc0000946c0} {stu0 95 36.08714 0xc0000944b0} {head 28 88}
方法二
使用指针的指针
package main import ( "fmt" "math/rand" ) type Student struct { Name string Age int Score float32 next *Student } func main() { //头部结构体 var head *Student = &Student{} head.Name = "head" head.Age = 28 head.Score = 88 //调用头部插入函数 HeadInsert(&head) Req(head) } func Req(tmp *Student) { for tmp != nil { fmt.Println(*tmp) tmp = tmp.next } } func HeadInsert(p **Student) { for i := 0; i < 10; i++ { var stu = Student{ Name: fmt.Sprintf("stu%d", i), Age: rand.Intn(100), Score: rand.Float32() * 100, } //当前新节点指向head,因为head是下一个节点 stu.next = *p //指向下一个节点 *p = &stu //把当前的结构体给tail,让其继续循环 } } //输出结果如下 {stu9 37 21.855305 0xc000114660} {stu8 11 29.310184 0xc000114630} {stu7 28 46.888985 0xc000114600} {stu6 62 38.06572 0xc0001145d0} {stu5 94 81.36399 0xc0001145a0} {stu4 56 30.091187 0xc000114570} {stu3 25 15.651925 0xc000114540} {stu2 81 68.682304 0xc000114510} {stu1 47 43.77142 0xc0001144e0} {stu0 81 94.05091 0xc0001144b0} {head 28 88}
总结
如果想要外部的数据和函数处理结果进行同步,两种方法:
① 传参,传递指针
② return 进行值的返回
6. 指定节点后添加新节点
package main import ( "fmt" "math/rand" ) type Student struct { Name string Age int Score float32 next *Student } func main() { //头部结构体 var head *Student = &Student{} //定义指针类型 head.Name = "head" head.Age = 28 head.Score = 88 //定义新的节点 var newNode *Student = &Student{} //定义指针类型 newNode.Name = "newNode" newNode.Age = 19 newNode.Score = 78 HeadInsert(&head) //指定位置插入函数 Add(head, newNode) Req(head) } func Req(tmp *Student) { for tmp != nil { fmt.Println(*tmp) tmp = tmp.next } } func HeadInsert(p **Student) { //传入指针的指针 for i := 0; i < 10; i++ { var stu = Student{ Name: fmt.Sprintf("stu%d", i), Age: rand.Intn(100), Score: rand.Float32() * 100, } //当前新节点指向head,因为head是下一个节点 stu.next = *p //指向下一个节点 *p = &stu //把当前的结构体给tail,让其继续循环 } } //p为当前节点,newnode为插入的节点 func Add(p *Student, newNode *Student) { for p != nil { if p.Name == "stu6" { //对接下一个节点 newNode.next = p.next p.next = newNode } //插入节点指向下一个节点 p = p.next //p.next赋予给p,继续进行循环遍历 } } //输出结果如下 {stu9 37 21.855305 0xc0000c0660} {stu8 11 29.310184 0xc0000c0630} {stu7 28 46.888985 0xc0000c0600} {stu6 62 38.06572 0xc0000c04b0} {newNode 19 78 0xc0000c05d0} {stu5 94 81.36399 0xc0000c05a0} {stu4 56 30.091187 0xc0000c0570} {stu3 25 15.651925 0xc0000c0540} {stu2 81 68.682304 0xc0000c0510} {stu1 47 43.77142 0xc0000c04e0} {stu0 81 94.05091 0xc0000c0480} {head 28 88}
7. 删除节点
package main import ( "fmt" "math/rand" ) type Student struct { Name string Age int Score float32 next *Student } func main() { //头部结构体 var head *Student = &Student{} //定义指针类型 head.Name = "head" head.Age = 28 head.Score = 88 //定义新的节点 var newNode *Student = &Student{} //定义指针类型 newNode.Name = "newNode" newNode.Age = 19 newNode.Score = 78 HeadInsert(&head) //指定位置插入函数 Add(head, newNode) //删除节点 del(head) Req(head) } func Req(tmp *Student) { for tmp != nil { fmt.Println(*tmp) tmp = tmp.next } } func HeadInsert(p **Student) { //传入指针的指针 for i := 0; i < 10; i++ { var stu = Student{ Name: fmt.Sprintf("stu%d", i), Age: rand.Intn(100), Score: rand.Float32() * 100, } //当前新节点指向head,因为head是下一个节点 stu.next = *p //指向下一个节点 *p = &stu //把当前的结构体给tail,让其继续循环 } } //p为当前节点,newnode为插入的节点 func Add(p *Student, newNode *Student) { for p != nil { if p.Name == "stu6" { //对接下一个节点 newNode.next = p.next p.next = newNode } //插入节点指向下一个节点 p = p.next //p.next赋予给p,继续进行循环遍历 } } //删除节点 func del(p *Student) { var prev *Student = p //p=head prev=head ——》prev=p for p != nil { if p.Name == "newNode" { prev.next = p.next break } prev = p //进行平移,前节点赋值 p = p.next //后节点赋值 } } //输出结果如下 {stu9 37 21.855305 0xc0000c0660} {stu8 11 29.310184 0xc0000c0630} {stu7 28 46.888985 0xc0000c0600} {stu6 62 38.06572 0xc0000c05d0} {stu5 94 81.36399 0xc0000c05a0} {stu4 56 30.091187 0xc0000c0570} {stu3 25 15.651925 0xc0000c0540} {stu2 81 68.682304 0xc0000c0510} {stu1 47 43.77142 0xc0000c04e0} {stu0 81 94.05091 0xc0000c0480} {head 28 88}
以上就是Go语言学习之链表的使用详解的详细内容,更多关于Go语言链表的资料请关注脚本之家其它相关文章!
X 关闭
X 关闭
- 15G资费不大降!三大运营商谁提供的5G网速最快?中国信通院给出答案
- 2联想拯救者Y70发布最新预告:售价2970元起 迄今最便宜的骁龙8+旗舰
- 3亚马逊开始大规模推广掌纹支付技术 顾客可使用“挥手付”结账
- 4现代和起亚上半年出口20万辆新能源汽车同比增长30.6%
- 5如何让居民5分钟使用到各种设施?沙特“线性城市”来了
- 6AMD实现连续8个季度的增长 季度营收首次突破60亿美元利润更是翻倍
- 7转转集团发布2022年二季度手机行情报告:二手市场“飘香”
- 8充电宝100Wh等于多少毫安?铁路旅客禁止、限制携带和托运物品目录
- 9好消息!京东与腾讯续签三年战略合作协议 加强技术创新与供应链服务
- 10名创优品拟通过香港IPO全球发售4100万股 全球发售所得款项有什么用处?