Go语言中的链表与双向链表实现
链表基础
链表是一种由有限元素组成的数据结构,其中每个元素至少使用两个内存空间:一个存储实际数据,另一个存储指向下一个元素的指针,从而形成一个元素序列构成链表。链表的第一个元素称为头结点,而最后一个元素通常被称为尾结点。为了操作链表,保持对头结点的引用非常重要,因为头结点是我们访问整个链表的唯一入口。如果丢失了指向头结点的指针,将无法再次找到链表的其他元素。
链表的操作
在链表中,移除节点时,主要操作是调整要删除节点的前一个节点的指针,使其指向要删除节点的下一个节点。
Go中的链表实现
我们通过Go语言的链表实现来更好地理解链表的操作过程。
package mainimport ("fmt"
)// 定义链表节点结构
type Node struct {Value intNext *Node
}// 全局变量root,保存链表的头结点
var root = new(Node)
在以上代码中,定义了链表节点的结构,包含一个Value用于存储节点的值,一个Next指针指向链表的下一个节点。此外,还定义了一个全局变量root,用于保存链表的头结点。
添加节点
链表通常不允许重复元素,并且当链表未排序时,新节点通常添加到链表末尾。以下是添加节点的代码实现:
func addNode(t *Node, v int) int {if root == nil {t = &Node{v, nil}root = treturn 0}if v == t.Value {fmt.Println("节点已存在:", v)return -1}if t.Next == nil {t.Next = &Node{v, nil}return -2}return addNode(t.Next, v)
}
在addNode函数中,首先检查链表是否为空,如果为空,则将新节点作为头结点插入。接着,检查链表中是否已有待插入的值,避免重复元素。如果当前节点的Next指针为空,说明已到达链表末尾,便将新节点添加到链表的末尾。若以上情况均不满足,则递归地继续检查下一个节点。
遍历链表
遍历链表的代码如下:
func traverse(t *Node) {if t == nil {fmt.Println("-> 空链表!")return}for t != nil {fmt.Printf("%d -> ", t.Value)t = t.Next}fmt.Println()
}
traverse函数通过循环遍历链表,并输出每个节点的值,直到遍历到最后一个节点。
查找节点与计算链表长度
func lookupNode(t *Node, v int) bool {if root == nil {t = &Node{v, nil}root = treturn false}if v == t.Value {return true}if t.Next == nil {return false}return lookupNode(t.Next, v)
}func size(t *Node) int {if t == nil {fmt.Println("-> 空链表!")return 0}i := 0for t != nil {i++t = t.Next}return i
}
lookupNode用于检查链表中是否存在某个值,而size函数用于计算链表的长度,即节点的数量。通过递归或循环,分别遍历链表的每个节点,返回结果。
主函数测试
func main() {fmt.Println(root)root = niltraverse(root)addNode(root, 1)addNode(root, -1)traverse(root)addNode(root, 10)addNode(root, 5)addNode(root, 45)traverse(root)if lookupNode(root, 100) {fmt.Println("节点存在!")} else {fmt.Println("节点不存在!")}fmt.Println("链表长度:", size(root))
}
输出结果:
&{0 <nil>}
-> 空链表!
1 -> -1 ->
1 -> -1 -> 10 -> 5 -> 45 ->
节点不存在!
链表长度: 5
链表的优势
链表的优势在于其灵活性和实现的简单性,适合处理各种数据类型。链表在进行顺序查找时效率较高,特别是在动态数据管理(如插入和删除)时优于数组等静态数据结构。此外,链表可以动态增长,且删除节点的操作较为简单,尤其是有序链表。
双向链表
双向链表是一种特殊的链表结构,每个节点不仅有一个指向下一个节点的指针,还有一个指向前一个节点的指针。这样可以实现双向遍历。双向链表的头节点的前一个节点为nil,尾节点的下一个节点也为nil。
Go中的双向链表实现
双向链表的节点定义如下:
type Node struct {Value intPrevious *NodeNext *Node
}
该结构体中有两个指针字段:一个指向前一个节点,一个指向下一个节点。
添加节点
func addNode(t *Node, v int) int {if root == nil {t = &Node{v, nil, nil}root = treturn 0}if v == t.Value {fmt.Println("节点已存在:", v)return -1}if t.Next == nil {temp := tt.Next = &Node{v, temp, nil}return -2}return addNode(t.Next, v)
}
与单链表类似,双向链表的节点通常添加到链表末尾。
遍历与反向遍历
func traverse(t *Node) {if t == nil {fmt.Println("-> 空链表!")return}for t != nil {fmt.Printf("%d -> ", t.Value)t = t.Next}fmt.Println()
}func reverse(t *Node) {if t == nil {fmt.Println("-> 空链表!")return}temp := tfor t != nil {temp = tt = t.Next}for temp.Previous != nil {fmt.Printf("%d -> ", temp.Value)temp = temp.Previous}fmt.Printf("%d -> ", temp.Value)fmt.Println()
}
reverse函数实现了反向遍历,先遍历到链表末尾,再通过Previous指针反向输出节点值。
双向链表的优势
双向链表相比单链表,优势在于可以进行双向遍历,删除和插入操作更加灵活。如果丢失了头结点的指针,仍可以通过尾节点找到链表的其他节点。但双向链表需要维护两个指针,增加了存储空间的消耗和代码的复杂性。
结语
链表和双向链表作为基础的数据结构,在处理动态数据和顺序查找中具有显著优势。通过对Go语言中链表的实现,读者可以更深入理解如何在实际开发中使用这些数据结构来提高程序的性能和可维护性。
相关文章:
Go语言中的链表与双向链表实现
链表基础 链表是一种由有限元素组成的数据结构,其中每个元素至少使用两个内存空间:一个存储实际数据,另一个存储指向下一个元素的指针,从而形成一个元素序列构成链表。链表的第一个元素称为头结点,而最后一个元素通常…...
开始一个WPF项目时的记忆重载入
目前在工业软件的UI开发方案选择中,WPF仍然是一个重要的选项。 但是其固有的复杂性,对于像我这样,并不是一直在从事界面开发的人来说,每次重启,都需要一两天的适应的时间。所以这里稍微写一个笔记。 还是老办法&…...
用go语言实现树和哈希表算法
算法复杂度 判断一个算法的效率通常基于其计算复杂度,这主要与算法访问输入数据的次数有关。计算机科学中常用大O表示法来描述算法的复杂度。例如,O(n)的算法只需访问一次输入数据,因此优于O(n)的算法,后者则优于O(n)的算法&…...
基于SpringBoot+Vue+MySQL的校园健康驿站管理系统
系统展示 用户前台界面 管理员后台界面 系统背景 本文设计并实现了一个基于SpringBoot后端、Vue前端与MySQL数据库的校园健康驿站管理系统。该系统旨在通过数字化手段,全面管理学生的健康信息,包括体温监测、疫苗接种记录、健康状况申报等,为…...
深入理解MATLAB中的事件处理机制
在MATLAB中,事件处理机制是一种强大的工具,它允许对象之间的交互和通信。这种机制基于观察者设计模式,其中一个对象(观察者)监听另一个对象(发布者)的状态变化。当发布者的状态发生变化时&#…...
线程--线程同步
这里写目录标题 同步概念线程同步概念数据混乱原因 互斥量原理锁的注意事项1、cpu时间轮片2、建议锁总结 使用锁来管理线程同步问题产生主要函数init、destorylock、unlock代码注意事项(锁的粒度) try锁死锁出现原因图解 读写锁特性图解函数总览init、de…...
【QT】Qt窗口
欢迎来到Cefler的博客😁 🕌博客主页:折纸花满衣 🏠个人专栏:QT 目录 👉🏻菜单栏设置👉🏻QToolBar练习 👉🏻QStausBar👉🏻Q…...
场外个股期权怎么给股票加杠杆?
今天期权懂带你了解场外个股期权怎么给股票加杠杆?场外期权交易通过向证券公司支付一定额度的股票期权费,然后买入大额的股票持仓,从而实现的杠杆交易。 买入看涨期权 操作:支付权利金购买看涨期权。 杠杆作用: 期…...
【Docker部署ELK】(7.15)
1、拉取镜像 docker pull docker.elastic.co/elasticsearch/elasticsearch:7.15.0 docker pull docker.elastic.co/kibana/kibana:7.15.0 docker pull docker.elastic.co/logstash/logstash:7.15.02、配置文件(解压资源到D盘DOCKER目录下) 2.1 配置文件…...
UE4_后期处理_后期处理材质及后期处理体积一
后期处理效果 在渲染之前应用于整个渲染场景的效果。 后期处理效果(Post-processing effect)使美术师和设计师能够对影响颜色、色调映射、光照的属性和功能进行组合选择,从而定义场景的整体外观。要访问这些功能,可以将一种称为…...
【PyQt6 应用程序】基于QtDesigner做一个用户登录页面
在当今的软件开发领域,用户界面(UI)设计和后端编程是创建现代、互动应用程序的两大重要组成部分。尤其是在开发具有用户登录功能的应用程序时,不仅要注重外观和用户体验的设计,还要确保后端逻辑的安全性和可靠性。 本文将介绍如何使用PyQt6框架结合UI设计,实现一个简单而…...
Ollama—87.4k star 的开源大模型服务框架!!
这一年来,AI 发展的越来越快,大模型使用的门槛也越来越低,每个人都可以在自己的本地运行大模型。今天再给大家介绍一个最厉害的开源大模型服务框架——ollama。 项目介绍 Ollama 是一个开源的大语言模型(LLM)服务工具…...
MySQL表的操作与数据类型
目录 前言 一、表的操作 1.创建一个表 2.查看表的结构 3.修改表 4.删除一个表 二、 MySQL的数据类型 0.数据类型一览: 1.整数类型 2.位类型 3.小数类型 4.字符类型 前言 在MySQL库的操作一文中介绍了有关MySQL库的操作,本节要讲解的是由库管理的结构——…...
mysql把某一个字段的值中的aa,替换成bb
UPDATE my_table SET my_column REPLACE(my_column, aa, bb); 例 假设my_table表在替换前的数据如下: idmy_column1hello aa2world aa aa3no aa here 执行上述UPDATE语句后,my_table表的数据将变为: idmy_column1hello bb2world bb b…...
【系统架构设计师】原型模式详解
原型模式详解 1. 什么是原型模式? 原型模式(Prototype Pattern)是一种创建型设计模式,它允许通过复制已有的对象来创建新的对象,而不是通过类实例化来创建新对象。通过这种方式,原型模式能够减少创建对象的开销,尤其是当对象的创建过程非常复杂或者耗费资源时。原型模…...
Spring @Async 深度解读:默认线程池执行器的配置与优化
在Spring中,Async注解用于异步执行方法。默认情况下,Async注解的任务是由一个线程池执行的。然而,这个默认的线程池是如何初始化的呢?本文将深入探讨这一过程,帮助你理解Spring异步任务背后的线程池执行器的初始化原理…...
手把手教你用护核纪元地心护核者用服务器开服联机
1、购买后登录服务器面板(百度莱卡云面板) 登录面板的信息在绿色的登陆面板按键下方,不是你的莱卡云账号 进入控制面板后会出现正在安装的界面,安装大约3分钟(如长时间处于安装中请联系我们的客服人员) 2、…...
Log4j 1.x如何升级到Log4j 2.x
Log4j 1.x升级到Log4j 2.x是一个涉及多个步骤的过程,主要包括删除旧版本、添加新版本依赖、配置新版本的配置文件等。以下是一个详细的升级步骤指南: 一、准备阶段 了解当前项目依赖: 检查项目中所有使用Log4j 1.x的地方,包括ja…...
CloudFlare问题与CDN问题
昨天将腾讯云的解析转移到Cloudflare中了,结果今天发现网站崩了,显示重定向次数过多,昨天估计是因为浏览器缓存,所以没有发现问题 问题一:强制HTTPS 当时看到CloudFlare的强制https时就想到了我的宝塔面板也开着强制h…...
[Linux]:文件(上)
✨✨ 欢迎大家来到贝蒂大讲堂✨✨ 🎈🎈养成好习惯,先赞后看哦~🎈🎈 所属专栏:Linux学习 贝蒂的主页:Betty’s blog 1. C语言文件操作 C语言文件操作接口如下,详情可参照——C语言文…...
装饰模式(Decorator Pattern)重构java邮件发奖系统实战
前言 现在我们有个如下的需求,设计一个邮件发奖的小系统, 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其…...
Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
基于TurtleBot3在Gazebo地图实现机器人远程控制
1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...
现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?
现有的 Redis 分布式锁库(如 Redisson)相比于开发者自己基于 Redis 命令(如 SETNX, EXPIRE, DEL)手动实现分布式锁,提供了巨大的便利性和健壮性。主要体现在以下几个方面: 原子性保证 (Atomicity)ÿ…...
JavaScript 数据类型详解
JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型(Primitive) 和 对象类型(Object) 两大类,共 8 种(ES11): 一、原始类型(7种) 1. undefined 定…...
搭建DNS域名解析服务器(正向解析资源文件)
正向解析资源文件 1)准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2)服务端安装软件:bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...
es6+和css3新增的特性有哪些
一:ECMAScript 新特性(ES6) ES6 (2015) - 革命性更新 1,记住的方法,从一个方法里面用到了哪些技术 1,let /const块级作用域声明2,**默认参数**:函数参数可以设置默认值。3&#x…...
TCP/IP 网络编程 | 服务端 客户端的封装
设计模式 文章目录 设计模式一、socket.h 接口(interface)二、socket.cpp 实现(implementation)三、server.cpp 使用封装(main 函数)四、client.cpp 使用封装(main 函数)五、退出方法…...
字符串哈希+KMP
P10468 兔子与兔子 #include<bits/stdc.h> using namespace std; typedef unsigned long long ull; const int N 1000010; ull a[N], pw[N]; int n; ull gethash(int l, int r){return a[r] - a[l - 1] * pw[r - l 1]; } signed main(){ios::sync_with_stdio(false), …...
