详解Go语言中单链表的使用
作者:Hann?Yang 发布时间:2024-02-01 11:55:03
标签:Go,单链表
链表
一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。使用链表结构可以避免在使用数组时需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。
单链表结构
利用 struct 可以包容多种数据类型,结构体内也可以包含多个成员,这些成员可以是基本类型、自定义类型、数组类型,也可以是指针类型。这里可以使用指针类型成员来存放下一个结点的地址。如以下定义,成员 data 用来存放结点中的数据(整数类型),next 是指针类型的成员,它指向 ListNode struct 类型数据,也就是下一个结点的数据类型。
type ListNode struct {
data int
next *ListNode
}
创建节点
节点声明和赋值有以下几种格式:
package main
import "fmt"
type ListNode struct {
data int
next *ListNode
}
func main() {
var head *ListNode
head = new(ListNode)
head.data = 1
var node1 = new(ListNode)
node1.data = 2
var node2 = &ListNode{3, nil}
var node3 = &ListNode{data: 4}
fmt.Println(*head)
fmt.Println(*node1)
fmt.Println(*node2)
fmt.Println(*node3)
}
/* 输出:
{1 <nil>}
{2 <nil>}
{3 <nil>}
{4 <nil>}
*/
遍历链表
一个for循环即可,结构描述的链表没有空链表的,不论data是何种类型,一旦声明即使不马上赋值也会有类型默认值,比如new(ListNode)即赋值了ListNode{0, nil}。
func showNode(p *ListNode) {
fmt.Print(*p)
for p.next != nil {
p = p.next
fmt.Print("->", *p)
}
fmt.Println()
}
头插法
新结点放在链表的最前面
package main
import "fmt"
type ListNode struct {
data int
next *ListNode
}
func showNode(p *ListNode) {
fmt.Print(*p)
for p.next != nil {
p = p.next
fmt.Print("->", *p)
}
fmt.Println()
}
func main() {
var head = &ListNode{0, nil}
for i := 1; i < 5; i++ {
var node = ListNode{data: i}
node.next = head
head = &node
}
showNode(head)
}
/* 输出:
{4 0xc000084250}->{3 0xc000084240}->{2 0xc000084230}->{1 0xc000084220}->{0 <nil>}
*/
尾插法
新结点追加到链表的最后面
package main
import "fmt"
type ListNode struct {
data int
next *ListNode
}
func showNode(p *ListNode) {
fmt.Print(*p)
for p.next != nil {
p = p.next
fmt.Print("->", *p)
}
fmt.Println()
}
func main() {
var head, tail *ListNode
head = &ListNode{0, nil}
tail = head
for i := 1; i < 5; i++ {
var node = ListNode{data: i}
(*tail).next = &node
tail = &node
}
showNode(head)
}
/* 输出:
{0 0xc000084220}->{1 0xc000084230}->{2 0xc000084240}->{3 0xc000084250}->{4 <nil>}
*/
遍历方法
方法的定义:参数表放在函数名前
package main
import "fmt"
type ListNode struct {
data int
next *ListNode
}
func (p *ListNode) travel() {
fmt.Print(p.data)
for p.next != nil {
p = p.next
fmt.Print("->", p.data)
}
fmt.Println("<nil>")
}
func main() {
var head = &ListNode{0, nil}
head.travel()
for i := 1; i < 10; i++ {
var node = ListNode{data: i}
node.next = head
head = &node
}
head.travel()
var root *ListNode
root = new(ListNode)
root.travel()
}
/* 输出:
0<nil>
9->8->7->6->5->4->3->2->1->0<nil>
0<nil>
*/
链表长度
注意:函数与方法的区别
package main
import "fmt"
type ListNode struct {
data int
next *ListNode
}
func (head *ListNode) size() int {
size := 1
for head = head.next; head != nil; size++ {
head = head.next
}
return size
}
func Len(head *ListNode) int {
size := 1
for head = head.next; head != nil; size++ {
head = head.next
}
return size
}
func main() {
var head = &ListNode{0, nil}
fmt.Println(Len(head))
fmt.Println(head.size())
for i := 1; i < 10; i++ {
var node = ListNode{data: i}
node.next = head
head = &node
}
fmt.Println(Len(head))
fmt.Println(head.size())
}
/* 输出:
1
1
10
10
*/
链表转数组
package main
import (
"fmt"
)
type ListNode struct {
data int
next *ListNode
}
func (head *ListNode) size() int {
size := 1
for head = head.next; head != nil; size++ {
head = head.next
}
return size
}
func (head *ListNode) tolist() []int {
var res []int
res = make([]int, 0, head.size())
for head.next != nil {
res = append(res, head.data)
head = head.next
}
res = append(res, head.data)
return res
}
func (head *ListNode) tolist2() []int {
var res []int
res = make([]int, 0, head.size())
res = append(res, head.data)
head = head.next
for head != nil {
res = append(res, head.data)
head = head.next
}
return res
}
func main() {
var head = &ListNode{0, nil}
for i := 1; i < 10; i++ {
var node = ListNode{data: i}
node.next = head
head = &node
}
fmt.Println(head.tolist())
var root, tail *ListNode
root = &ListNode{0, nil}
tail = root
for i := 1; i < 10; i++ {
var node = ListNode{data: i}
(*tail).next = &node
tail = &node
}
fmt.Println(root.tolist2())
}
/* 输出:
[9 8 7 6 5 4 3 2 1 0]
[0 1 2 3 4 5 6 7 8 9]
*/
数组转链表
package main
import "fmt"
type ListNode struct {
data int
next *ListNode
}
func (p *ListNode) travel() {
fmt.Print(p.data)
for p.next != nil {
p = p.next
fmt.Print("->", p.data)
}
fmt.Println("<nil>")
}
func toNode(list []int) *ListNode {
var head, tail *ListNode
head = &ListNode{list[0], nil}
tail = head
for i := 1; i < len(list); i++ {
var node = ListNode{data: list[i]}
(*tail).next = &node
tail = &node
}
return head
}
func main() {
var lst = []int{1, 3, 2, 3, 5, 6, 6, 8, 9}
toNode(lst).travel()
}
/* 输出:
1->3->2->3->5->6->6->8->9<nil>
*/
来源:https://blog.csdn.net/boysoft2002/article/details/126442832
0
投稿
猜你喜欢
- 本文实例讲述了python实现堆栈与队列的方法。分享给大家供大家参考。具体分析如下:1、python实现堆栈,可先将Stack类写入文件st
- Python遍历numpy数组下面是示例代码:import numpy as npnum = np.zeros([2, 3])[rows,
- 前言初学者看到 Python 中的下划线 _ 时可能会有些懵圈,不知道这个到底是干什么用的,今天就来盘点一下 Python 中间的下划线有哪
- 有的小伙伴对于枚举的理解很模糊,其实我们可以把它看成一个数量的大管家,对其中的每一个数进行检查,保证里面的数字都没有重复的,这就是枚举的用法
- 逆向最大匹配方法有正即有负,正向最大匹配算法大家可以参阅https://www.jb51.net/article/127404.htm逆向最
- 现像如下:站点无法打开,或者打开很慢.HTML可以打开.重新启动或者回收应用程序池可恢复.但过一段时间又会出现日志里会有:ISAPI
- pycharm出现no module named xlwt问题首先声明,我是初学者,今天按照书上步骤,创建Excel文件,当我的xlwt安装
- 一、Django中路由的作用URL配置(URLconf)就像Django 所支撑网站的目录。它的本质是URL与要为该URL调用的视图函数之间
- 一、安装plotly库因为这部分内容主要是用plotly库进行数据动态展示,所以要先安装plotly库pip install plotly除
- 本文实例为大家分享了js浏览器倒计时跳转页面效果,供大家参考,具体内容如下效果图:<!DOCTYPE html><html
- 1.必需的参数:必须参数须以正确的顺序传入函数,调用的数量必须和声明时的一样def f(name,age):print('I am
- 目录1 摘要2 概述2.1 什么是并行计算?2.2 为什么要并行计算?2.3 谁都在使用并行计算?科学界和工程界:工业界和商业界:全球应用:
- 前言数据分析时候,需要将数据进行加载和存储,本文主要介绍和excel的交互。read_excel()加载函数为read_excel(),其具
- 做服务器端开发的同学应该都对进程监控不会陌生,最近恰好要更换 uwsgi 为 gunicorn,而gunicorn又恰好有这么一章讲进程监控
- 相对于numpy、TensorFlow、pandas这些已经经过多年维护、迭代,对于大多数Python开发者耳熟能详的库不同。今天要给大家介
- python开发中经常遇到报错的情况,但是warning通常并不影响程序的运行,而且有时特别讨厌,下面我们来说下如何忽略warning错误。
- Summary主要包括以下三种途径:使用独立的函数;使用torch.type()函数;使用type_as(tesnor)将张量转换为给定类型
- 这些对文本的操作经常用到, 那我就总结一下。 陆续补充。。。操作:strip_html(cls, text) 去除html标签separat
- DQL(Data Query Language),数据查询语言,主要是用来查询数据的,这也是SQL中最重要的部分!简单查询#DQL操作之基本
- 这篇文章主要介绍了Python如何把多个PDF文件合并,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋