使用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实现数据结构内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！