【数据结构系列】聊聊数据结构的那些事儿~

在程序的世界里，有一个东西虽然看不见，摸不着，却时时刻刻影响着程序的运行，这个东西就是 数据结构

合适的场景选择合适的数据结构非常重要，它可以左右我们程序的性能，因此一定要掌握它，废话不多说，开搞！

什么是数据结构

即数据元素相互之间存在的 一种和多种特定关系的集合

数据结构的分类

数据结构可以从两个维度去分类

1. 逻辑结构: 简单来说就是数据之间的关系
2. 存储结构: 就是逻辑结构用 计算机语言 的实现

逻辑结构的维度下，通常分为8大类：

1. 数组
2. 栈
3. 队列
4. 链表
5. 树
6. 散列表
7. 堆
8. 图

存储结构的维度下，通常分为4大类：

1. 顺序存储: 数组在内存中的位置是连续的，它就属于顺序存储
2. 链式存储: 链表是主动建立数据间的关联关系，在内存中却 不一定是连续的，它属于链式存储
3. 索引存储
4. 散列存储: 顺序和逻辑上都不存在顺序关系，但是你可以通过一定的方式去访问，如哈希表

接下来详细聊聊在逻辑结构的维度下，每一个类别的详细内容

数组

数组是可以 在内存中连续存储多个元素 的结构，在内存中的分配也是 连续的，数组中的元素通过 数组下标 进行访问，数组下标从0开始

优点如下:

1. 按照索引查询元素 速度快
2. 按照索引遍历数组 方便

缺点:

1. 数组的大小固定后就 无法扩容了
2. 数组只能存储 一种类型 的数据
3. 添加，删除的操作 慢，因为要移动其他的元素

适用场景:

1. 频繁查询
2. 对存储空间要求不大
3. 很少增加和删除的情况

栈

栈是一种 特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作

栈的特点是 先进后出，从栈顶放入元素的操作叫 入栈，取出元素叫 出栈

常应用于 实现递归 功能方面的场景

队列

队列与栈一样，也是一种线性表，不同的是，队列可以在一端添加元素，在另一端取出元素

队列的特点就是 先进先出，从一端放入元素的操作称为 入队，另一端取出元素称为 出队

在 多线程阻塞队列管理 中非常适用

链表

链表是物理存储单元上 非连续的、非顺序的 存储结构，数据元素的逻辑顺序是通过 链表的指针地址 实现

每个元素包含两个东西，一个是存储元素的 数据域，另一个是指向下一个结点地址的 指针域

根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等

优点：

1. 不需要初始化容量
2. 可以任意加减元素
3. 添加或者删除元素时只需要改变前后两个元素结点的指针域即可，所以添加，删除很快

缺点：

1. 因为含有大量的指针域，占用空间较大
2. 查找元素需要遍历链表来查找，非常耗时

适用场景：

1. 数据量较小
2. 需要频繁增加，删除操作的场景

树

是由n（n>=1）个有限节点组成一个具有 层次关系 的集合

把它叫做 “树” 是因为它看起来像一棵倒挂的树，也就是说它是 根朝上，而 叶朝下的

这个部分我准备单独写文章，因此不过多介绍

散列表

散列表，也叫哈希表，是根据 关键码 和 值 (key和value) 直接进行访问的数据结构，通过key和value来映射到集合中的一个位置，这样就可以很快找到集合中的对应元素

堆

堆有如下两个特点

1. 由 完全二叉树 实现

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树

2. 堆中每一个节点的值都必须大于等于（或小于等于）其后代节点的值。堆中每一个节点若大于等于后代节点就是大根堆，根是最大值，若小于等于后代节点就是小根堆，根是最小值

堆由于其 有序性，所以可以用 数组 实现

图

图是由 结点的有穷集合V和边的集合E 组成

其中，为了与树形结构加以区别，在图结构中常常将结点称为 顶点，边是顶点的 有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有 相邻关系

按照顶点指向的方向可分为 无向图 和 有向图

结语

数据结构对于我们程序员来说非常重要，它是所有程序的基石，只有在合适的场景选择合适的数据结构，才能写出优秀的程序，因此一起加油吧，骚年！