【Go 数据结构】列表与字典

列表

对于列表的表示我们有如下两种实现形式：

  • 顺序表示：指的是使用一组地址连续的存储单元依次存储线性表的数据，成为此线性表为顺序存储结构， 它以物理位置相邻来表示线性表中的数据间的逻辑位置，可随机存取表中的任何一个数据元素，顺序表示的也叫做顺序表，也就是用数组来实现的列表。
  • 链式表示：指的是用一组任意的非连续的存储单元存储线性表中的数据元素，成为线性表的链式存储结构。它的存储单元可以是连续的，也可以是不连续的。在表示数据元素之间的逻辑关系时，除了存储本身信息之外，还需要存储一个指向直接后继节点的信息，也就是用链表来实现的列表。

双端列表

定义数据类型

// 定义双端链表的数据类型
type ListNode struct {
	prev  *ListNode
	next  *ListNode
	value string
}
type DoubleList struct {
	head *ListNode  // 头节点
	tail *ListNode  // 尾节点
	len  int        // 长度
	lock sync.Mutex // 为了并发安全，引入锁
}

常见操作

/*
	一些常见的基本操作
*/

// GetValue 获取节点值
func (node *ListNode) GetValue() string {
	return node.value
}

// GetPre 获取前一个节点
func (node *ListNode) GetPre() *ListNode {
	return node.prev
}

// GetNext 获取后一个节点
func (node *ListNode) GetNext() *ListNode {
	return node.next
}

// HasNext 是否有后一个节点
func (node *ListNode) HasNext() bool {
	return node.next != nil
}

// HasPre 是否有前一个节点
func (node *ListNode) HasPre() bool {
	return node.prev != nil
}

// IsNil 是否为空
func (node *ListNode) IsNil() bool {
	return node == nil
}

// Len 获取长度
func (list *DoubleList) Len() int {
	return list.len
}

// First 头部节点
func (list *DoubleList) First() *ListNode {
	return list.head
}

// Last 尾部节点
func (list *DoubleList) Last() *ListNode {
	return list.tail
}

插入操作

实现从头部开始，在某个节点之前插入一个节点。

// AddNodeFormHead 从头部开始，在某个节点之前插入一个节点
// 0 表示第一个元素之前，1 表示第二个元素之前...
func (list *DoubleList) AddNodeFormHead(value string, pre int) {
	list.lock.Lock()
	defer list.lock.Unlock()

	if pre <= 0 || pre > list.len {
		panic("pre is out of range")
	}

	// 找到头部节点
	node := list.head

	// 向后进行遍历，找到pre-1个节点
	for i := 0; i <= pre; i++ {
		node = node.next
	}

	newNode := new(ListNode)
	node.value = value

	// 如果定位到的节点为空，则直接插入到头部
	if node.IsNil() {
		list.head = newNode
		list.tail = newNode
	} else {
		// 找到前一个节点
		pre := node.prev

		// 如果定位到的节点为头部，则直接插入到头部
		if pre.IsNil() {
			newNode.next = node
			node.prev = newNode
			list.head = newNode
		} else {
			// 将新节点插入到定位节点之前
			// 新节点的后一个节点为定位节点
			pre.next = newNode
			newNode.prev = pre

			// 新节点的前一个节点为定位节点的前一个节点
			node.next.prev = newNode
			newNode.next = node.next
		}
	}
	list.len++
}

实现从尾部开始，在某个节点之后插入一个节点。

// AddNodeFormTail 从尾部开始，在某个节点之后插入一个节点
// 0 表示第一个元素之后，1 表示第二个元素之后...
func (list *DoubleList) AddNodeFormTail(value string, next int) {
	list.lock.Lock()
	defer list.lock.Unlock()

	// 找到尾部节点
	node := list.tail

	if next <= 0 || next > list.len {
		panic("next is out of range")
	}

	// 向前进行遍历，找到next-1个节点
	for i := 0; i <= next; i++ {
		node = node.prev
	}

	newNode := new(ListNode)
	newNode.value = value

	// 如果定位到的节点为空，则直接插入到尾部
	if node.IsNil() {
		list.head = newNode
		list.tail = newNode
	} else {
		// 找到定位节点的后一个节点
		next := node.next

		// 如果定位到的节点为尾部，则直接插入到尾部,需要更新尾部节点
		if next.IsNil() {
			// 新节点的前一个节点为尾部节点
			// 新节点的后一个节点为空
			newNode.prev = node
			node.next = newNode

			list.tail = newNode
		} else {
			// 将新节点插入到定位节点之后
			// 新节点的前一个节点为定位节点
			newNode.prev = node
			node.next = newNode

			// 新节点的后一个节点为定位节点的后一个节点
			newNode.next = next
			next.prev = newNode
		}
	}
	list.len++
}

获取节点

实现从头部开始，获取第 n + 1 个位置上的节点。

// IndexFormHead 从头部开始获取第 n + 1 个位置上的节点，索引从零开始
func (list *DoubleList) IndexFormHead(n int) *ListNode {
	if n > list.len || n < 0 {
		panic("index is out of range")
	}
	// 找到头部节点
	node := list.head
	// 向后进行遍历，找到第 n 个节点
	for i := 0; i < n; i++ {
		node = node.next
	}
	return node
}

实现从尾部开始，获取第 n + 1 个位置上的节点。

// IndexFormTail 从尾部开始获取第 n + 1 个位置上的节点，索引从零开始
func (list *DoubleList) IndexFormTail(n int) *ListNode {
	if n > list.len || n < 0 {
		panic("index is out of range")
	}

	// 找到尾部节点
	node := list.tail

	// 向前进行遍历，找到第 n 个节点
	for i := 0; i < n; i++ {
		node = node.prev
	}
	return node
}

删除节点

实现从头部开始，删除第 n + 1 个位置上的节点。

// RemoveNodeFormHead 从头部开始，删除第 n + 1 个位置上的节点，索引从零开始
func (list *DoubleList) RemoveNodeFormHead(n int) *ListNode {
	list.lock.Lock()
	defer list.lock.Unlock()

	if n >= list.len || n < 0 {
		return nil
		panic("index is out of range")
	}

	// 找到头部节点
	node := list.head

	// 向后进行遍历，找到第 n 个节点
	for i := 0; i < n; i++ {
		node = node.next
	}

	// 移除节点
	pre := node.prev
	next := node.next

	// 如果前继和后继都为空，则直接删除头部节点
	if pre.IsNil() && next.IsNil() {
		list.head = nil
		list.tail = nil
	} else if pre.IsNil() {
		// 表示移除的是头部节点，让下一个节点变成头部节点
		list.head = next
		next.prev = nil
	} else if next.IsNil() {
		// 表示移除的是尾部节点，让前一个节点变成尾部节点
		list.tail = pre
		pre.next = nil
	} else {
		// 前继和后继都不为空，则将后继节点的前继节点变成前继节点
		pre.next = next
		next.prev = pre
	}
	list.len--
	return node
}

实现从尾部开始，删除第 n + 1 个位置上的节点。

// PopTailFromHead 从尾部开始往前找，获取第 n 个位置上的节点，并将移除返回
func (list *DoubleList) PopTailFromHead(n int) *ListNode {
	list.lock.Lock()
	defer list.lock.Unlock()

	if n >= list.len || n < 0 {
		return nil
		panic("index is out of range")
	}

	// 获取尾部元素
	node := list.tail

	// 向前进行遍历，找到第 n 个节点
	for i := 0; i < n; i++ {
		node = node.prev
	}

	// 移除的节点的前驱和后继
	pre := node.prev
	next := node.next

	// 如果前驱和后继都为空，则直接删除尾部节点
	if pre.IsNil() && next.IsNil() {
		list.head = nil
		list.tail = nil
	} else if pre.IsNil() {
		// 直接将后继节点变成尾部节点
		list.head = next
		next.prev = nil
	} else if next.IsNil() {
		list.tail = pre
		pre.next = nil
	} else if next.IsNil() {
		pre.next = next
		pre.next = nil
	} else {
		pre.next = next
		next.prev = pre
	}
	list.len--
	return node
}

字典

字典是存储键值对的数据结构，把一个键和一个值映射起来，一一映射。并且键不能重复。

func DicExample() {
	m := make(map[string]int64, 4)

	m["dog"] = 1
	m["hen"] = 2
	m["cat"] = 3

	fmt.Println(m)

	which := "hen"

	v, ok := m[which]
	if ok {
		// find
		fmt.Println("finn", which, "value:", v)
	} else {
		// not find
		fmt.Println("not find", which)
	}
}

不可重复集合

在 Golang 中，实现集合是一件很有意思的事情。

我们通常借助空结构体为值来实现 Set， 因为我们知道字典的键是不重复的，所以只要我们不考虑字典的值，就可以来实现集合了。

注意：空结构体并不占用内存在大小。

定义数据类型

// 思想：不考虑字典的值，我们可以实现一个set

type Set struct {
	m   map[int]struct{} // 为什么我们要使用空结构体，因为空结构体不占用内存
	len int
	sync.RWMutex
}

新建一个Set操作

// NewSet 新建一个set
func NewSet(cap int64) *Set {
	temp := make(map[int]struct{}, cap)
	return &Set{
		m: temp,
	}
}

增加一个元素

// Add 增加一个元素
func (s *Set) Add(item int) {
	s.Lock()
	defer s.Unlock()

	s.m[item] = struct{}{}
	s.len = len(s.m)
}

删除一个元素

//Remove 移除一个元素
func (s *Set) Remove(item int) {
	s.Lock()
	defer s.Unlock()

	if s.len == 0 {
		return
	}
	// 从字典中删除
	delete(s.m, item)
	// 计算长度
	s.len = len(s.m)
}

判断元素是否存在

// Has 判断一个元素是否在set中
func (s *Set) Has(item int) bool {
	s.RLock()
	defer s.RUnlock()

	_, ok := s.m[item]
	return ok
}

获取长度

// Len 获取set的长度
func (s *Set) Len() int {
	return s.len
}

判断是否为空

//IsEmpty 判断set是否为空
func (s *Set) IsEmpty() bool {
	if s.len == 0 {
		return true
	}
	return false
}

清空

// Clear 清空set
func (s *Set) Clear() {
	s.Lock()
	defer s.Unlock()

	s.m = make(map[int]struct{})
	s.len = 0
}

转化为Slice

// List 将 Set 转化为 Slice
func (s *Set) List() []int {
	s.RLock()
	defer s.RUnlock()

	list := make([]int, 0, s.len)
	for item := range s.m {
		list = append(list, item)
	}
	return list
}

总结

本次我们介绍使用Go语言实现数据结构中的列表和字典，并且介绍了一些常见的操作。数据结构这一系列我们没有涉及到具体的细节的讲解，适合有一定数据结构基础的童鞋，本系列代码已经上传至Github，欢迎大家 Star。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/595493.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

[leetcode] 62. 不同路径

[leetcode] 62. 不同路径

文章目录 题目描述解题方法方法一&#xff1a;动态规划java代码复杂度分析 方法二&#xff1a;排列组合java代码复杂度分析 相似题目 题目描述 一个机器人位于一个 m x n 网格的左上角 &#xff08;起始点在下图中标记为 “Start” &#xff09;。 机器人每次只能向下或者向右…
阅读更多...
毕业设计：《基于 Prometheus 和 ELK 的基础平台监控系统设计与实现》

毕业设计：《基于 Prometheus 和 ELK 的基础平台监控系统设计与实现》

前言 《基于 Prometheus 和 ELK 的基础平台监控系统设计与实现》&#xff0c;这是我在本科阶段的毕业设计&#xff0c;通过引入 Prometheus 和 ELK 架构实现企业对指标与日志的全方位监控。并且基于云原生&#xff0c;使用容器化持续集成部署的开发方式&#xff0c;通过 Sprin…
阅读更多...
开源模型应用落地-CodeQwen模型小试-SQL专家测试（二）

开源模型应用落地-CodeQwen模型小试-SQL专家测试（二）

一、前言 代码专家模型是基于人工智能的先进技术&#xff0c;它能够自动分析和理解大量的代码库&#xff0c;并从中学习常见的编码模式和最佳实践。这种模型可以提供准确而高效的代码建议&#xff0c;帮助开发人员在编写代码时避免常见的错误和陷阱。 通过学习代码专家模型&…
阅读更多...
使用Bandzip分卷压缩文件

使用Bandzip分卷压缩文件

需求 部分文件太大&#xff0c;例如超过10G&#xff0c;就不能使用企业微信等传输&#xff0c;如果可以把一个10G的文件分割成为10个1G的文件就可以方便传输了。 实现方式 使用bandzip&#xff0c;把超过10G的文件分卷压缩成为多个小的zip文件。 把生成的多个文件放在同一目…
阅读更多...
网红隋总揭秘：高效实施人力RPO项目的秘诀

网红隋总揭秘：高效实施人力RPO项目的秘诀

随着企业对于招聘流程效率和专业性的追求日益提升&#xff0c;RPO(招聘流程外包)项目逐渐成为人力资源领域的热门话题。隋总凭借丰富的行业经验和独特的视角&#xff0c;分享了关于如何高效实施人力RPO项目的秘诀。 一、明确目标&#xff0c;找准定位 在启动RPO项目之前&#x…
阅读更多...
零基础入门篇④ 初识Python(注释、编码规范、关键字...)

零基础入门篇④ 初识Python(注释、编码规范、关键字...)

Python从入门到精通系列专栏面向零基础以及需要进阶的读者倾心打造，9.9元订阅即可享受付费专栏权益，一个专栏带你吃透Python，专栏分为零基础入门篇、模块篇、网络爬虫篇、Web开发篇、办公自动化篇、数据分析篇…学习不断，持续更新，火热订阅中🔥专栏订阅地址 👉Python从…
阅读更多...
【挑战30天首通《谷粒商城》】-【第一天】01、简介-项目介绍

【挑战30天首通《谷粒商城》】-【第一天】01、简介-项目介绍

文章目录 课程介绍一、 项目介绍1、项目背景A、电商模式1、B2B 模式2、B2C 模式3、C2B 模式4、C2C 模式5、O2O 模式 1.2、项目架构图1.3、项目技术 & 特色1.4、项目前置要求二、分布式基础概念(略)三、环境撘建(略) one more thing 课程介绍 1.分布式基础(全栈开发篇)2.分…
阅读更多...
UE5 audio capture 回声问题 ||在安卓上有爆鸣声

UE5 audio capture 回声问题 ||在安卓上有爆鸣声

参考视频 0.基本步骤 【UE4_蓝图】录制麦克风声音/系统声音并输出保存WAV文件_ue4录音-CSDN博客 1.步骤 1.创建Sound Submix A 2. 右键新建Sound Submix B 3.把B的两个参数调为-96 4.audio capture的Base Submix&#xff0c;把前面提到的A赋值进去 5.开始录制输出和完成录制…
阅读更多...
【Unity 协程】

【Unity 协程】

Unity中的协程&#xff08;Coroutine&#xff09;是一种编程结构&#xff0c;它允许你以一种看似同步的方式编写可能需要异步执行的代码。协程特别适用于需要在一定时间后执行操作&#xff0c;或者在循环执行某段代码直到某个条件满足时的场景。 协程使用IEnumerator委托来实现…
阅读更多...
30天精通 Δ-Σ ADC 设计

30天精通 Δ-Σ ADC 设计

在现代电子工程和信号处理领域&#xff0c;模拟-数字转换器&#xff08;ADC&#xff09;是实现信号精确转换的核心组件。ADC技术正经历革新&#xff0c;拓展了其在多个前沿技术领域的应用范围。 **首先&#xff0c;**ADC的采样率和分辨率是衡量其性能的关键指标。随着技术工艺…
阅读更多...
海外网安同行们面对当下的就业环境，也破防了。。。

海外网安同行们面对当下的就业环境，也破防了。。。

问&#xff1a;漂亮国的安全行业就业市场怎么样&#xff1f; 答&#xff1a;初级岗位挺好找的&#xff0c;如果你有一个硕士学位并且还有10年工作经验的话。 0x00 我之前在分析海外的就业环境的时候[海外安全行业工资水平怎么样&#xff1f;]&#xff0c;一度以为外国的月亮就…
阅读更多...
分布式光伏管理系统和一般的光伏管理系统相比有什么区别？

分布式光伏管理系统和一般的光伏管理系统相比有什么区别？

随着全球对可再生能源的关注度日益提高&#xff0c;光伏技术作为其中的佼佼者&#xff0c;已经得到了广泛的应用。在光伏技术中&#xff0c;管理系统扮演着至关重要的角色&#xff0c;它关乎着光伏电站的运行效率、能源产出以及运维成本等多个方面。其中&#xff0c;分布式光伏…
阅读更多...
N9048B PXE EMI 测试接收机，1 Hz 至 44 GHz

N9048B PXE EMI 测试接收机，1 Hz 至 44 GHz

​ _EMI_ N9048B EMI 测试接收机 1 Hz 至 44 GHz Keysight N9048B PXE 是一款符合标准的 EMI 测试接收机&#xff0c;配有射频预选器和 LNA 设计。其实时扫描&#xff08;RTS&#xff09;功能有助于您缩短总体测试时间&#xff0c;轻松执行无间隙的信号捕获和分析。 特点 …
阅读更多...
前后端功能实现——添加品牌

前后端功能实现——添加品牌

需求 点击新增&#xff0c;跳转到添加品牌的页面&#xff0c;从后一个页面提交品牌数据&#xff1a; 1、BrandMapper接口添加add()方法 /** * 添加品牌 */ void add(Brand brand); 2、BrandMapper.xml中添加sql方法 <insert id"add">insert into brand val…
阅读更多...
【字符串】Leetcode 最长回文子串

【字符串】Leetcode 最长回文子串

题目讲解 5. 最长回文子串 算法讲解 dp[i][j]表示i~j这一段区间的子串是否是回文 当s[i] s[j]的时候&#xff0c;此时是有三种情况的&#xff1a; ij说明一个字符肯定是回文 i1 j也说明一个字符是回文 i1 < j说明需要判断[i1, j-1]这一段区间是否是回文 此时我们就可以…
阅读更多...
代码随想录算法训练营第十三天：树的认知（补五一）

代码随想录算法训练营第十三天：树的认知（补五一）

代码随想录算法训练营第十三天&#xff1a;树的认知&#xff08;补五一&#xff09; ‍ 二叉树的递归遍历 #算法公开课 《代码随想录》算法视频公开课 ****(opens new window)****​ &#xff1a;​每次写递归都要靠直觉&#xff1f; 这次带你学透二叉树的递归遍历&#xf…
阅读更多...
[UDS][OTA] 自定义 IntelHEX (IHEX) format read/write library in C

[UDS][OTA] 自定义 IntelHEX (IHEX) format read/write library in C

参考修改 参考github的MIT协议开源项目 ihex 改写的代码 https://gitee.com/liudegui/intelhex-c 修改点&#xff1a; 修改Makefile脚本&#xff0c;支持x86_X64平台和aarch64平台将默认读取行长度设置为16位删除与ihex和bin之间的转换无关的示例代码 十六进制描述 HEX格式…
阅读更多...
c#绘制渐变色的Led

c#绘制渐变色的Led

项目场景&#xff1a; c#绘制渐变色的button using System; using System.ComponentModel; using System.Drawing; using System.Drawing.Drawing2D; using System.Windows.Forms; using static System.Windows.Forms.AxHost;namespace WindowsFormsApp2 {public class Gradie…
阅读更多...
接口测试及常用的接口测试工具（Postman/Jmeter）

接口测试及常用的接口测试工具（Postman/Jmeter）

&#x1f345; 视频学习&#xff1a;文末有免费的配套视频可观看 &#x1f345; 点击文末小卡片 &#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 首先&#xff0c;什么是接口呢&#xff1f; 接口一般来说有两种&#xff0c;一种是程序内部的接…
阅读更多...
包管理工具npm、cnpm、yarn、NVM

包管理工具npm、cnpm、yarn、NVM

[包]英文单词是package,代表了一组特定功能的源码集合 包管理工具&#xff1a; 管理[包]的应用软件,可以对[包]进行下载安装,更新,删除,上传等操作借助包管理工具,可以快速开发项目,提升开发效率 包管理工具是一个通用的概念,很多编程语言都有包管理工具,所以掌握好包管理工具非…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站