常用的数据结构有：数组，栈，链表，队列，树，图，堆，散列表等。
每一种数据结构都有着独特的数据存储方式，下面为大家介绍它们的结构和优缺点。
1、数组
数组是可以再内存中连续存储多个元素的结构，在内存中的分配也是连续的，数组中的元素通过数组下标进行访问，数组下标从0开始。例如下面这段代码就是将数组的第一个元素赋值为1。
arr是数组的名字,后面的” [] “表示哪一个数据,这里面的数字叫做数组下标,或者叫索引,下标是从0开始计数,比如想要查询小红的话则是” arr[1]
数组的数据是按照顺序存储在内存中连续的空间,所以内存中的每个数据都可以通过下标来取得,这样就可以直接进行访问数据,如果我们使用链表的话,那么就需要指针一个个去查询数据,数组可以直接访问,这样查询效率就会大大提升,但是想要在任意未知去添加数据和删除数据的话,那么数组的操作就比链表难多了,如果我们想把” 小王 “加入到小明的后面,也就是 arr[1] 的位置,首先数组的末尾需要有足够的空间,(java中数组的长度一但初始化就不可改变,所以要保证有足够的空间来存放想要添加的数据),如果已经有空间,那么我们需要将小黑向后移动一位,然后小红向后移动一位,当arr[1] 的空间空出来的时候,才能把小王添加进去,这样的话数组的添加操作才能完成,相反如果想要删除掉小王的话,那么就需要删除目标的数据,也就是arr[1]的位置,然后把后面的数据往前移动,最后删除掉多余的空间即可
数组的查询数据的时间复杂度为O(1),删除和添加则为O(n),正好和链表相反
优点：
1、 按照索引查询元素快
2、 按照索引遍历数组方便
缺点：
1、 数组的大小固定后就无法扩容了
2、 数组只能存储一种类型的数据
3、 添加，删除的操作慢，因为要移动其他的元素。
适用场景：
频繁查询，对存储空间要求不大，很少增加和删除的情况。
2、栈
栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。 栈的特点是：先进后出，或者说是后进先出，从栈顶放入元素的操作叫入栈，取出元素叫出栈。
栈的结构就像一个集装箱，越先放进去的东西越晚才能拿出来，所以，栈常应用于实现递归功能方面的场景，例如斐波那契数列。
3、队列
队列与栈一样，也是一种线性表，不同的是，队列可以在一端添加元素，在另一端取出元素，也就是：先进先出。从一端放入元素的操作称为入队，取出元素为出队，示例图如下：
适用场景：因为队列先进先出的特点，在多线程阻塞队列管理中非常适用。
4、链表
链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域。根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。
优点：
1、 链表是很常用的一种数据结构，不需要初始化容量，可以任意加减元素；
2、 添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可，所以添加，删除很快；
缺点：
1、 因为含有大量的指针域，占用空间较大；
2、 查找元素需要遍历链表来查找，非常耗时。
适用场景：
数据量较小，需要频繁增加，删除操作的场景
5、树
树是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
1、每个节点有零个或多个子节点；
2、没有父节点的节点称为根节点；
3、每一个非根节点有且只有一个父节点；
4、除了根节点外，每个子节点可以分为多个不相交的子树；
在日常的应用中，我们讨论和用的更多的是树的其中一种结构，就是二叉树。
二叉树是树的特殊一种，具有如下特点：
1、每个结点最多有两颗子树，结点的度最大为2。
2、左子树和右子树是有顺序的，次序不能颠倒。
3、即使某结点只有一个子树，也要区分左右子树。
二叉树是一种比较有用的折中方案，它添加，删除元素都很快，并且在查找方面也有很多的算法优化，所以，二叉树既有链表的好处，也有数组的好处，是两者的优化方案，在处理大批量的动态数据方面非常有用。
扩展：
二叉树有很多扩展的数据结构，包括平衡二叉树、红黑树、B+树等，这些数据结构二叉树的基础上衍生了很多的功能，在实际应用中广泛用到，例如mysql的数据库索引结构用的就是B+树，还有HashMap的底层源码中用到了红黑树。这些二叉树的功能强大，但算法上比较复杂，想学习的话还是需要花时间去深入的。
6、散列表
散列表，也叫哈希表，是根据关键码和值 (key和value) 直接进行访问的数据结构，通过key和value来映射到集合中的一个位置，这样就可以很快找到集合中的对应元素。
记录的存储位置=f(key)
这里的对应关系 f 成为散列函数，又称为哈希 (hash函数)，而散列表就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里，这种存储空间可以充分利用数组的查找优势来查找元素，所以查找的速度很快。
哈希表在应用中也是比较常见的，就如Java中有些集合类就是借鉴了哈希原理构造的，例如HashMap，HashTable等，利用hash表的优势，对于集合的查找元素时非常方便的，然而，因为哈希表是基于数组衍生的数据结构，在添加删除元素方面是比较慢的，所以很多时候需要用到一种数组链表来做，也就是拉链法。拉链法是数组结合链表的一种结构，较早前的hashMap底层的存储就是采用这种结构，直到jdk1.8之后才换成了数组加红黑树的结构，其示例图如下：
从图中可以看出，左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。
哈希表的应用场景很多，当然也有很多问题要考虑，比如哈希冲突的问题，如果处理的不好会浪费大量的时间，导致应用崩溃。
7、堆
堆是一种比较特殊的数据结构，可以被看做一棵树的数组对象，具有以下的性质：
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。
(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2)，满足前者的表达式的成为小顶堆，满足后者表达式的为大顶堆，这两者的结构图可以用完全二叉树排列出来，示例图如下：
因为堆有序的特点，一般用来做数组中的排序，称为堆排序。
8、图
图的定义：
一个图G = (V,E)由顶点(vertex)集 V 合边(edge)集 E 组成。每条边(v,w)就是一个点对,其中v,w ∈ V。有时也把边称作弧。如果点对是有序的，那么图就叫做有向图。顶点 v 和 w 领接边 (v,w) ∈ E。在一个具有边(v,w)从而具有边(w,v)的无向图，w和v邻接那v和w也邻接。
图的基本术语：
1、 阶（Order）：图G中顶集V的大小称作图G的阶。
2、 子图（Sub-Graph）：G’称作图G=(V,E)的子图，当图G’=(V’,E’)，且V‘包含于V，E’包含于E。每个图都是本身的子图。
3、 生成子图（Spanning Sub-Graph）：指满足条件V(G’) = V(G)的G的子图G。
4、 度（Degree）：一个顶点的度是指与该边相关联的边的条数，顶点v的度记作d(v)。
5、 入度（In-degree）和出度（Out-degree）：对于有向图来说，一个顶点的度可细分为入度和出度。一个顶点的入度是指与其关联的各边之中，以其为终点的边数；出度则是相对的概念，指以该顶点为起点的边数。
6、 自环（Loop）：若一条边的两个顶点为同一顶点，则此边称作自环。
7、 路径（Path）：从u到v的一条路径是指一个序列v0,e1,v1,e2,v2,…ek,vk，其中ei的顶点为vi及vi - 1，k称作路径的长度。如果它的起止顶点相同，该路径是“闭”的，反之，则称为“开”的。一条路径称为一简单路径(simple path)，如果路径中除起始与终止顶点可以重合外，所有顶点两两不等。
8、 连通图：如果在一个无向图中从每一个顶点到每个其他顶点都存在一条路径，则称该无向图是联通的，具有这样的有向图成为强连通图。
图的基本操作：
（1）创建一个图结构 CreateGraph(G)
（2）检索给定顶点 LocateVex(G,elem)
（3）获取图中某个顶点 GetVex(G,v)
（4）为图中顶点赋值 PutVex(G,v,value)
（5）返回第一个邻接点 FirstAdjVex(G,v)
（6）返回下一个邻接点 NextAdjVex(G,v,w)
（7）插入一个顶点 InsertVex(G,v)
（8）删除一个顶点 DeleteVex(G,v)
（9）插入一条边 InsertEdge(G,v,w)
（10）删除一条边 DeleteEdge(G,v,w)
（11）遍历图 Traverse(G,v)
图的高级算法：
1、 最小生成树（Prim和kruskal算法）
2、 单元路径最短（Dijkstra算法）
3、所有点对的最短路径（Floyd-Warshall算法）
