当前位置: 首页 > 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…...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...

MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)

macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 &#x1f37a; 最新版brew安装慢到怀疑人生&#xff1f;别怕&#xff0c;教你轻松起飞&#xff01; 最近Homebrew更新至最新版&#xff0c;每次执行 brew 命令时都会自动从官方地址 https://formulae.…...

Rust 开发环境搭建

环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行&#xff1a; rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu ​ 2、Hello World fn main() { println…...

算法打卡第18天

从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder &#xff0c;其中 inorder 是二叉树的中序遍历&#xff0c; postorder 是同一棵树的后序遍历&#xff0c;请你构造并返回这颗 二叉树 。 示例 1: 输入&#xff1a;inorder [9,3,15,20,7…...

OCR MLLM Evaluation

为什么需要评测体系&#xff1f;——背景与矛盾 ​​ 能干的事&#xff1a;​​ 看清楚发票、身份证上的字&#xff08;准确率>90%&#xff09;&#xff0c;速度飞快&#xff08;眨眼间完成&#xff09;。​​干不了的事&#xff1a;​​ 碰到复杂表格&#xff08;合并单元…...