使用go实现常见的数据结构
1 golang常见数据结构实现
1.1 链表
举单链表的例子,双向链表同理只是多了pre指针。
定义单链表结构:
构造链表及打印链表:
1.2 可变数组
可变数组在各种语言中都非常常用,在golang中,可变数组语言本身已经实现,就是我们的切片slice。
1.3 栈和队列
1.3.1 原生切片实现栈和队列
栈:先进后出,后进先出,类似弹夹
队列:先进先出
golang中,实现并发不安全的栈和队列,非常简单,我们直接使用原生切片即可。
1.3.1.1 切片原生栈实现
1.3.1.2 切片原生队列实现
1.3.2 *并发安全的栈和队列
1.3.2.1 切片实现并发安全的栈并发安全的栈
入栈
出栈
1、如果切片偏移量向前移动 stack.array[0 : stack.size-1],表明最后的元素已经不属于该数组了,数组变相的缩容了。此时,切片被缩容的部分并不会被回收,仍然占用着空间,所以空间复杂度较高,但操作的时间复杂度为:o(1)。
2、如果我们创建新的数组 newarray,然后把老数组的元素复制到新数组,就不会占用多余的空间,但移动次数过多,时间复杂度为:o(n)。
获取栈顶元素
获取栈大小和判定是否为空
1.3.2.2 切片实现并发安全的队列队列结构
入队
出队
1、原地挪位,依次补位 queue.array[i-1] = queue.array[i],然后数组缩容:queue.array = queue.array[0 : queue.size-1],但是这样切片缩容的那部分内存空间不会释放。
2、创建新的数组,将老数组中除第一个元素以外的元素移动到新数组。
1.4 字典map和集合set
1.4.1 map
字典也是程序语言经常使用的结构,golang中的字典是其自身实现的map结构。具体操作可以查看语言api
并发安全的map,可以定义结构,结构中有一个map成员和一个锁变量成员,参考并发安全的栈和队列的实现。go语言也实现了一个并发安全的map,具体参考sync.map的api
1.4.2 set
我们可以借助map的特性,实现一个set结构。
set结构
map的值我们不适用,定义为空的结构体struct{}
初始化set
往set中添加一个元素
删除一个元素
查看元素是否在集合set中
查看集合大小
查看集合是否为空
清除集合所有元素
将集合转化为切片
1.5 二叉树
二叉树:每个节点最多只有两个儿子节点的树。
满二叉树:叶子节点与叶子节点之间的高度差为 0 的二叉树,即整棵树是满的,树呈满三角形结构。在国外的定义,非叶子节点儿子都是满的树就是满二叉树。我们以国内为准。
完全二叉树:完全二叉树是由满二叉树而引出来的,设二叉树的深度为 k,除第 k 层外,其他各层的节点数都达到最大值,且第 k 层所有的节点都连续集中在最左边。
二叉树结构定义
树的遍历
1、先序遍历:先访问根节点,再访问左子树,最后访问右子树。
2、后序遍历:先访问左子树,再访问右子树,最后访问根节点。
3、中序遍历:先访问左子树,再访问根节点,最后访问右子树。
4、层次遍历:每一层从左到右访问每一个节点。
按层遍历:
到此这篇关于用go实现常见的数据结构的文章就介绍到这了,更多相关go实现数据结构内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持!
推荐阅读
-
android使用Messenger绑定Service的多种实现方法
-
使用Python实现将list中的每一项的首字母大写
-
使用Flask-Cache缓存实现给Flask提速的方法详解
-
C#使用委托实现的快速排序算法实例
-
C#中通过使用Connection类来实现打开/关闭数据库的代码实例
-
Android中使用Handler及Countdowntimer实现包含倒计时的闪屏页面
-
vue cli使用融云实现聊天功能的实例代码
-
Python单元测试_使用装饰器实现测试跳过和预期故障的方法
-
premiere cc怎么实现多机位监视器? premiere监视器的使用方法
-
Spring Cache的基本使用与实现原理详解