[toc]
https://zhuanlan.zhihu.com/p/138523723
数组是最简单、使用最频繁的一种数据结构。 它一种线性表数据结构，用一组连续的内存空间来存储一组相同类型的数据。
由于数据是存储在连续空间内的，所以每个数据的内存地址(在内存上的位置)都可以通过数组下标计算出来， 从而可以直接访问目标数据，达到随机访问的目的。
其特点是先入先出，也就是我们常听到的FIFO（First in First Out），即操作数据是从两端进行的
链表是一种物理存储单元上非连续，非顺序的存储结构。 链表有一系列节点组成，所谓节点就是指链表中的每一个元素， 每个节点包含两个数据，一个是存储元素的数据域（值），另一个是存储下一个节点地址的指针域。
栈也是一种数据呈线性排列的数据结构，和上面的队列相反，栈的特点先进后出、后进先出， 就是常说的LIFO（Last in First Out）
树形结构是一种层级式的数据结构，由顶点（节点）和连接它们的边组成。 数的结构特点是:
- 每个节点有零个或多个子节点；
- 没有父节点的节点称为根节点；
- 每一个非根节点有且只有一个父节点；
- 除了根节点外，每个子节点可以分为多个不相交的子树。
我们平时用到最多的就是二叉树，我也以二叉树来为例，先看一下树结构：
二叉树有几下特点：
- 每个结点最多有两颗子树，结点的度最大为2。
- 左子树和右子树是有顺序的，次序不能颠倒。
- 即使某结点只有一个子树，也要区分左右子树。
- 每个结点的值均大于其左子树上任意一个结点的值。比如 点的值。结点100大于其左子树上的30，18和16。
- 每个结点的值均小于其右子树上任意 一个结点的值。比如结点 100 小于其右子树上的 120、130 和 135。
散列表又叫哈希表，存储的是由键(key)和值(value)组 成的数据，根据键直接访问存储在内存存储位置的数据结构
从图中可以看出，左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空， 也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表， 再从链表中找出这个元素。哈希表查找数据的公式为：记录的存储位置=f(key)这里的对应关系 f 成为散列函数， 又称为哈希 (hash函数)，而散列表就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字， 然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里， 这种存储空间可以充分利用数组的查找优势来查找元素，所以查找的速度很快
堆比较特殊，是一种图的树形结构。 被用于实现“优先队列”(priority queues)，优先队列是一种数据结构，可以自由添加数据， 但取出数据时要从最小值开始按顺 序取出。
在堆的树形结构中，各个顶点被称为“结点”(node)，数据就存储在这些结点中。
只要满足下面两个特点的树形结构就是堆：
- 堆是一个完全二叉树（所谓完全二叉树就是除了最后一层其他层的节点个数都是满的）。
- 堆中每一个节点的值都必须大于等于或者小于其子树中每一个节点的值。
上图中其实叫大顶堆，如果每一个节点小于子树中每个节点的值，那就叫小顶堆。
图是相对复杂的一种数据结构，由顶点和连接每对顶点的边所构成的图形就是图。 上图中的圆圈叫作“顶点”(Vertex，也叫“结点”)，连接顶点的线叫作“边”（Edge）。也就是说，由顶点和连接每对顶点的边所构成的图形就是图。 图按照顶点指向的方向可分为无向图和有向图，像我上面的就叫无向图。 图在存储数据上有着比较复杂和高效的算法，分别有邻接矩阵 、邻接表、十字链表、邻接多重表、边集数组等存储结构。 常见的图遍历算法就是广度优先算法和深度优先算法