当前位置: 首页 > news >正文

Go的数据结构与实现【LinkedList】

介绍

所谓链表(Linked List),就是按线性次序排列的一组数据节点。每个节点都是一个对象,它通过一个引用指向对应的数据元素,同时还通过一个引用next指向下一节点。

实现

逻辑方法

我们定义链表的结构体:

// LinkedList the linked list struct
type LinkedList struct {sync.RWMutexhead *Nodesize int
}// Node a single node that composes the list
type Node struct {content Tnext    *Node
}

其中包含头节点和链表长度,在这里我们主要实现以下方法:

  • Add:添加一个元素到链表末尾
  • Insert:向链表指定位置插入元素
  • RemoveAt:移除指定索引位置的元素
  • IndexOf:取指定索引位置的元素
  • IsEmpty:判断链表是否为空
  • Size:获取链表长度
  • Traverse:遍历链表并输出

首先是Add方法,判断链表头节点是否为空,若空则设置头节点为插入的元素,若非空,找到链表末尾节点,再插入元素。

// Add adds t to the end of the linked list
func (l *LinkedList) Add(t T) {l.Lock()defer l.Unlock()node := NewNode(t)if l.head == nil {l.head = node} else {last := l.headfor {if last.next == nil {break}last = last.next}last.next = node}l.size++
}

Insert方法,注意判断索引位置是否合法,再插入指定位置。

// Insert adds t at position pos
func (l *LinkedList) Insert(t T, pos int) error {l.Lock()defer l.Unlock()// validate positionif pos < 0 || pos > l.size {return fmt.Errorf("insert position must be larger than 0 and smaller than linked list size")}node := NewNode(t)if pos == 0 {node.next = l.headl.head = nodereturn nil}head := l.headidx := 0for idx < pos-2 {idx++head = head.next}node.next = head.nexthead.next = nodel.size++return nil
}

RemoveAt方法与之类似,判断索引位置是否合法再移除。

// RemoveAt removes a node at position pos
func (l *LinkedList) RemoveAt(pos int) (*T, error) {l.Lock()defer l.Unlock()// validate positionif pos < 0 || pos > l.size {return nil, fmt.Errorf("insert position must be larger than 0 and smaller than linked list size")}head := l.headidx := 0for idx < pos-1 {idx++head = head.next}next := head.nexthead.next = next.nextl.size--return &next.content, nil
}

剩下的方法直接取相应数据即可。

// IndexOf returns the position of the t
func (l *LinkedList) IndexOf(t T) int {l.RLock()defer l.RUnlock()head := l.headidx := 0for {if head.content == t {return idx}if head.next == nil {return -1}head = head.nextidx++}
}// IsEmpty returns true if the list is empty
func (l *LinkedList) IsEmpty() bool {l.RLock()defer l.RUnlock()return l.head == nil
}// Size returns the linked list size
func (l *LinkedList) Size() int {l.RLock()defer l.RUnlock()return l.size
}

遍历方法Traverse还会输出元素内容。

// Traverse traverses linked list
func (l *LinkedList) Traverse() {l.RLock()defer l.RUnlock()head := l.headfor {if head == nil {break}head.Print()head = head.next}fmt.Println()
}

单元测试

单元测试如下:

import "testing"var (t1 T = 1t2 T = 2t3 T = 3t4 T = 4
)func InitLinkedList() *LinkedList {list := NewLinkedList()list.head = NewNode(t1)list.head.next = NewNode(t2)list.head.next.next = NewNode(t3)list.size = 3return list
}func TestLinkedList_Add(t *testing.T) {linkedList := InitLinkedList()size := linkedList.Size()if size != 3 {t.Errorf("linked list size should be 3 but got %d", size)}linkedList.Add(4)size = linkedList.Size()if size != 4 {t.Errorf("linked list size should be 4 but got %d", size)}
}func TestLinkedList_Insert(t *testing.T) {linkedList := InitLinkedList()err := linkedList.Insert(t4, 1)if err != nil {t.Errorf("insert into linked list err %v", err)}idx1 := linkedList.IndexOf(t2)idx2 := linkedList.IndexOf(t4)if idx1 != 2 || idx2 != 1 {t.Errorf("linked list position is not expected.")}
}func TestLinkedList_RemoveAt(t *testing.T) {linkedList := InitLinkedList()ret, err := linkedList.RemoveAt(2)if err != nil {t.Errorf("linked list err %v", err)}if *ret != t3 {t.Errorf("removed item expect 3 but got %d", *ret)}size := linkedList.Size()if size != 2 {t.Errorf("linked list size should be 2 but got %d", size)}
}func TestLinkedList_IsEmpty(t *testing.T) {linkedList := InitLinkedList()empty := linkedList.IsEmpty()if empty {t.Errorf("linked list is not empty.")}linkedList = &LinkedList{}empty = linkedList.IsEmpty()if !empty {t.Errorf("linked list is empty.")}
}func TestLinkedList_Traverse(t *testing.T) {linkedList := InitLinkedList()linkedList.Traverse()
}

相关文章:

Go的数据结构与实现【LinkedList】

介绍 所谓链表&#xff08;Linked List&#xff09;&#xff0c;就是按线性次序排列的一组数据节点。每个节点都是一个对象&#xff0c;它通过一个引用指向对应的数据元素&#xff0c;同时还通过一个引用next指向下一节点。 实现 逻辑方法 我们定义链表的结构体&#xff1a…...

Ubuntu22.04安装CUDA+CUDNN+Conda+PyTorch

步骤&#xff1a; 1、安装显卡驱动&#xff1b; 2、安装CUDA&#xff1b; 3、安装CUDNN&#xff1b; 4、安装Conda&#xff1b; 5、安装Pytorch。 一、系统和硬件信息 1、Ubuntu 22.04 2、显卡&#xff1a;4060Ti 二、安装显卡驱动 &#xff08;已经安装的可以跳过&a…...

当“广撒网”遇上“精准定点”的鱼叉式网络钓鱼

批量网络钓鱼电子邮件活动倾向于针对大量受众&#xff0c;它们通常使用笼统的措辞和简单的格式&#xff0c;其中不乏各种拼写错误。而有针对性的攻击往往需要付出更大的努力&#xff0c;攻击者会伪装成雇主或客户向目标发送包含个人详细信息的个性化消息。在更大范围内采用这种…...

svn ldap认证临时切换到本地认证

当前的svn是在CentOS 7 下 SVN、 Apache 对接 LDAP 服务实现用户账号管理和权限认证&#xff0c;本文模拟ldap数据丢失如何恢复svn&#xff0c;方法是临时将认证切换到本地认证 编辑subversion.conf文件 vi /etc/httpd/conf.d/subversion.conf 注释ldap-status #<Locati…...

极狐GitLab如何配置使用独立数据库?

GitLab 是一个全球知名的一体化 DevOps 平台&#xff0c;很多人都通过私有化部署 GitLab 来进行源代码托管。极狐GitLab &#xff1a;https://gitlab.cn/install?channelcontent&utm_sourcecsdn 是 GitLab 在中国的发行版&#xff0c;专门为中国程序员服务。可以一键式部署…...

TCP状态转换详解

1.什么是TCP的状态转换 TCP&#xff08;Transmission Control Protocol&#xff0c;传输控制协议&#xff09;是一种面向连接的、可靠的、基于字节流的传输层协议。在 TCP 连接的生命周期中&#xff0c;连接的状态会随着不同阶段的通信而发生变化&#xff0c;这些变化被称为状…...

SimMIM:一个类BERT的计算机视觉的预训练框架

1、前言 呃…好久没有写博客了&#xff0c;主要是最近时间比较少。今天来做一期视频博客的内容。本文主要讲SimMIM&#xff0c;它是一个将计算机视觉&#xff08;图像&#xff09;进行自监督训练的框架。 原论文&#xff1a;SimMIM&#xff1a;用于掩码图像建模的简单框架 (a…...

数据精度丢失

js数据精度丢失 最近看面试题想到了之前在开发钟遇到过的问题&#xff0c;现总结一下 在开发过程中&#xff0c;发现从后台返回的数据结构中的id字段在前端显示为不正确的值。经过排查&#xff0c;怀疑是JavaScript中Number类型精度丢失的问题。通过将id字段的类型从Number改为…...

Element UI DatePicker选择日期范围区间默认显示前一个月和本月

要求&#xff1a;点击el-date-picker选择时间范围时&#xff0c;默认展开当月和上个月。 但是Element UI的组件默认展开的是本月和下一个月&#xff0c;如下图所示&#xff1a; 改为 <span click"changeInitCalendarRange"><el-date-picker v-model"r…...

C++:聚合类、嵌套类、局部类、union类详细介绍与分析

聚合类 (1)What&#xff08;什么是聚合类&#xff09; 本质是一个自定义类型的数据结构&#xff08;结构体或类&#xff09;&#xff0c;但聚合类有以下特性&#xff1a; 所有的成员都是public没有任何构造函数没有基类类内部没有初始值 (2)Why&#xff08;聚合类的作用&…...

MKS流量计软件MFC通讯驱动使用于C和P系列MFC控制USB接口W10系统

MKS流量计软件MFC通讯驱动使用于C和P系列MFC控制USB接口W10系统...

C++:左值/右值引用、移动语义/std::move、万能引用/完美转发std::forward 详解

你能学到 左值 与 右值左值引用 与 右值引用 基本用法与作用拷贝构造函数 与 移动构造函数移动语义 与 std::move万能引用 与 引用折叠完美转发&#xff1a;std::forward 前言 本文代码片段中变量命名规则如下&#xff1a; 小写字母&#xff1a;一般类型的变量&#xff08;非…...

蜂窝物联云平台:一站式服务,智能生活从此开始!

蜂窝云平台 一、PC端展示与管理 GIS地图整合 在GIS地图上精确展示地块&#xff0c;轻松点选查看详细设备信息、实时监控和控制功能&#xff0c;以及基地的全方位介绍。 个性化定制界面 界面布局与功能展示均可按需求定制&#xff0c;打造独一无二的用户体验。 数据集中看板 将…...

【中项】系统集成项目管理工程师-第3章 信息技术服务-3.3服务生命周期

前言&#xff1a;系统集成项目管理工程师专业&#xff0c;现分享一些教材知识点。觉得文章还不错的喜欢点赞收藏的同时帮忙点点关注。 软考同样是国家人社部和工信部组织的国家级考试&#xff0c;全称为“全国计算机与软件专业技术资格&#xff08;水平&#xff09;考试”&…...

【iOS】——消息传递底层实现

消息传递是什么 Objective-C是一种动态类型语言&#xff0c;这意味着在编译时并不确定对象的具体类型&#xff0c;而是在运行时决定。消息传递机制允许程序在运行时向对象发送消息&#xff0c;对象再决定如何响应这些消息。 当你通过对象调用方法时&#xff0c;例如像这样[ob…...

PostgreSQL数据库从入门到精通系列之十:表空间、索引表空间、创建表空间、创建索引空间、创建分区表、创建分区表的分区、创建指定表空间、索引表空间的分区表

PostgreSQL数据库从入门到精通系列之十:表空间、索引表空间、创建表空间、创建索引空间、创建分区表、创建分区表的分区、创建指定表空间、索引表空间的分区表 一、数据库表空间和数据库之间的关系二、索引表空间和数据库之间的关系三、创建角色四、创建表空间目录五、创建表空…...

恶补,先验分布,后验分布 ,似然估计

恶补&#xff0c;打一遍增加印象 先验分布后验分布&#xff0c;似然估计 声明&#xff1a;仅记录个人学习&#xff0c;并无其他用途。 先验分布 后验分布&#xff0c; 似然估计 隔壁小哥的故事&#xff1a; 隔壁小哥要去15公里外的一个公园里玩&#xff0c;小哥可以选择步行…...

JS之数组中的reduce方法

文章目录 基本语法&#xff1a;callbackFn 的参数:例子1. 数组求和2. 数组求积3. 扁平化数组4. 数组元素计数5. 使用对象解构和展开运算符合并数组中的对象6. 求最大值和最小值 函数组合异步操作中的 reduce总结 reduce 是 JavaScript 中 Array 对象的一个方法&#xff0c;非常…...

在win10上通过WSL和docker安装Ubuntu子系统,并配置Ubuntu可成功使用宿主机GPU

本文主要记录win10系统上,通过WSL的Ubuntu系统以及Docker使用GPU的全部过程。 文章目录 1、 启用hyper-v2、 安装docker3、 安装WSL3.1 安装WSL23.1.1 检查是否安装了WSL23.1.1 安装和配置 WSL 23.2 安装Ubuntu 子系统3.3 检查并修改WSL版本4、docker配置ubuntu20.04 LTS5、下…...

python需要掌握那些语法

1-list数据类型 内置方法查看长度len&#xff08;list&#xff09; 2.array数据类型 查看形状 3.tuple 取出元组 t (1, 2, 3, 4, 5) # 取出第一个元素 2first_element t[0] 3print(first_element) # 输出&#xff1a;1 4 5# 取出第三个元素 6third_element t[2] 7pr…...

基于Laravel的BeikeShop开源电商平台:从架构解析到生产部署实战

1. 项目概述&#xff1a;为什么选择BeikeShop作为你的开源电商起点&#xff1f;如果你正在寻找一个能让你完全掌控代码和数据&#xff0c;同时又不想从零开始造轮子的电商解决方案&#xff0c;那么BeikeShop绝对值得你花时间深入了解。作为一个基于Laravel 10构建的、100%开源的…...

计网实验一

课程实验报告专 业&#xff1a;物联网工程 班 级&#xff1a;2303学 号&#xff1a;231040700302 姓 名&#xff1a;杜子健实验名称&#xff1a;实验一实验类型&#xff1a;实验实验日期&#xff1a;2025年11月12日一 实…...

Unity 2D横版闯关游戏:从零到一构建像素风丛林冒险

1. 像素风游戏的前期准备 第一次打开Unity时&#xff0c;看着空荡荡的场景视图&#xff0c;我完全不知道从哪里开始。后来发现&#xff0c;制作2D横版游戏就像搭积木&#xff0c;需要先准备好所有零件。这里分享我制作《丛林法则》时的完整筹备过程。 像素风游戏最迷人的就是那…...

触发器如何在主从架构下进行同步_基于Row格式的Binlog规避触发器

不会。MySQL在ROW格式Binlog下&#xff0c;主库触发器产生的变更不生成独立Binlog事件&#xff0c;从库仅回放行记录快照&#xff0c;跳过触发器执行&#xff1b;若启用STATEMENT/MIXED模式或手动关闭从库只读&#xff0c;才可能意外触发。主库触发器写入会不会被同步到从库不会…...

ARM错误恢复中断机制与ERRERICR2寄存器详解

1. ARM错误恢复中断机制概述在ARM架构的可靠性、可用性和可维护性&#xff08;RAS&#xff09;系统中&#xff0c;错误恢复中断是实现硬件容错的关键机制。当处理器检测到可恢复的错误条件时&#xff0c;通过这套机制能够快速通知系统进行错误处理&#xff0c;而ERRERICR2寄存器…...

办公室翻新预算超支了怎么办

很多小微企业、创业团队翻修办公室。算来算去&#xff0c;最后发现预算超支了。这种情况真的太常见了。我们今天一步步理&#xff0c;给你实打实的解决办法。大家最关心的5个问题解答Q1&#xff1a;办公室翻新&#xff0c;哪块更容易超预算&#xff1f;A&#xff1a;大部分情况…...

非傍轴效应在量子比特操控中的影响与优化策略

1. 非傍轴效应与量子比特操控&#xff1a;从理论到实验的全景解析在量子计算与模拟领域&#xff0c;光学镊子技术正经历着革命性的发展。这项技术通过高度聚焦的激光束&#xff0c;实现了对单个原子或离子的精确操控&#xff0c;为构建大规模量子处理器提供了可能路径。然而&am…...

透明背景图片制作方法,一个小程序就能搞定!

最近&#xff0c;我被一个问题烦透了——每次需要制作透明背景图片时&#xff0c;总要在各种工具之间折腾半天。直到我发现了一个神器&#xff0c;才彻底改变了我的工作流程。今天&#xff0c;我就来分享一下我用过的所有透明背景图片制作方法&#xff0c;以及为什么我现在最常…...

基于Java的教学仪器设备销售网站(10017)

有需要的同学&#xff0c;源代码和配套文档领取&#xff0c;加文章最下方的名片哦 一、项目演示 项目演示视频 二、资料介绍 完整源代码&#xff08;前后端源代码SQL脚本&#xff09;配套文档&#xff08;LWPPT开题报告/任务书&#xff09;远程调试控屏包运行一键启动项目&…...

Loop:三步快速配置,让你的Mac窗口管理效率提升300%

Loop&#xff1a;三步快速配置&#xff0c;让你的Mac窗口管理效率提升300% 【免费下载链接】Loop Window management made elegant. 项目地址: https://gitcode.com/GitHub_Trending/lo/Loop 你是否经常在多个应用窗口间来回切换&#xff0c;感觉自己像个杂技演员&#…...