定义
数据结构是指相互之间存在着一种或多种关系的数据元素的集合 。
常见的数据结构
数据存储的常用结构有数组，栈，队列，链表，树，图，堆，散列表等，如下图所示。
数组（Array）
数组是连续存储多个元素的序列，在内存中的分配也是连续的，数组中的元素通过下标进行访问。
String【】 data = new String【】{"Tom","Jack","Jessica","Katherine","Layman"};
System.out.println(data【3】);
优点：
1、查找元素快：通过索引，可以快速访问指定位置的元素
2、遍历数组快：通过索引，能够快速遍历数组
缺点：
1、数组的大小一旦确定就无法再扩容
2、数组只能存储单一类型的数据
3、添加，删除的操作慢，因为要移动其他的元素。
增加元素：需要创建一个新数组，将指定新元素存储在指定索引位置，再把原数组元素根据索引，复制到新数组对应索引的位置。
删除元素：需要创建一个新数组，把原数组元素根据索引，复制到新数组对应索引的位置，原数组中指定索引位置元素舍弃，不复制。
适用场景：
频繁查询，对存储空间要求不大，很少增加和删除的情况。
栈（Stack）
栈，又称堆栈，是一种特殊的（运算受限）线性表，其限制是仅允许在栈顶允许进行操作（类似弹匣）。
从栈顶放入元素的操作叫入栈，也叫压栈，取出元素叫出栈，也叫弹栈。
特点
先进后出，后进先出（类比弹匣上子弹）
适用场景：
递归，例如斐波那契数列。
队列（Queue）
队列和堆栈一样，也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。
可以把队列想象成两端开口的栈
特点
先进先出。
试用场景
因为队列具有先进先出的特点，因此非常适用于多线程阻塞队列管理。
链表（Linked List）
链表是由一系列结点node（链表中每一个元素称为结点）组成，每个结点至少有两个域，一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
链表的第一个节点和最后一个节点，分别称为头节点和尾节点。
尾节点的特征是其 next 引用为空（null）。
单向链表
单向链表中，每个节点的数据域都是通过一个 Object 类的对象引用来指向数据元素。
与数组类似，单向链表中的节点也具有线性次序，即如果节点 a1 的 next 引用指向节点 a2，则 a1 是 a2 的直接前驱节点，a2 是 a1 的直接后续节点。
只能通过前驱节点找到后续节点，而无法从后续节点找到前驱节点。
特点
查询慢： 存储地址不连续，每次查询元素都需要从头开始增删快：不必移动节点，只要改变节点中的指针，但是需要先定位到元素上。不保证元素的顺序：存储元素和取出元素的顺序有可能不一致。只能通过前驱节点找到后续节点，而无法从后续节点找到前驱节点。
双向链表
单向链表中找到某个节点的前驱节点，必须从链表的头节点出发依次向后寻找，需要Ο(n)时间。
因此我们可以扩展单向链表的节点结构，使得通过一个节点的引用，不但能够访问其后续节点，也可以访问其前驱节点。这就是双向链表。
双向链表，就是在单链表节点结构中新增一个域，该域存储指向该节点的前驱节点。
单向链表只能从一个方向遍历，双向链表可以从两个方向遍历。
双向链表头节点的前驱节点（pre）为空，而尾节点的后续节点（Next）为空
在双向链表中插入和删除节点，无//代码效果参考：http://www.jhylw.com.cn/184920699.html
论插入和删除的节点位置在何处。因为首尾节点的存在，插入、删除操作都可以被归结为某个中间节点的插入和删除。因为首尾节点的存在，双向链表永不为空。
简单用双向列表模拟LinkedList，代码如下：
import lombok.Data;
/
简单用双向列表模拟LinkedList
@author layman
@date 2021/2/24
/
public class MyLinkedList {
//首节点
private Node first;
//尾节点
private Node last;
public void add(Object obj){
if(first==null){
//说明该元素存于首节点上
Node firstNode = new Node();
firstNode.setPrevious(null);
firstNode.setObj(obj);
firstNode.setNext(null);
//此时该LinkedList只存了一个元素，所以首尾节点都设置为首节点
first //代码效果参考：http://www.jhylw.com.cn/023035215.html
= firstNode;last = firstNode;
}else{
//存入的不是首节点，则该元素存于首节点之后，指向前一个节点的last
Node node=new Node();
node.setPrevious(last);
node.setObj(obj);
node.setNext(null);
//将链表的last指针指向node
last.setNext(node);
//将链表的last改为node
last = node;
}
}
}
// 节点类
@Data
class Node {
//前驱节点
private Object previous;
//存储的数据
private Object obj;
//后续节点
private Object next;
}
循环链表
头节点和尾节点被连接在一起的链表称为循环链表，这种方式在单向和双向链表中皆可实现。
循环链表中第一个节点之前就是最后一个节点，反之亦然。
总结
链表的优点：
链表不需要初始化容量，可以任意加减元素；查询慢： 存储地址不连续，每次查询元素都需要从头开始，非常耗时增删快：不必移动节点，只要改变节点中的指针，但是需要先定位到元素上。因为含有大量的指针域，所以占用空间较大
适用场景：
数据量较小，需要频繁增加，删除操作的场景
树（Tree）
树是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。
之所以把它叫做 “树”， 是因为它看起来像一棵倒挂的树（根朝上，叶朝下）。
特点
每个节点有零个或多个子节点。没有父节点的节点称为根节点。每一个非根节点有且仅有一个父节点。除了根节点外，每个子节点可以分为多个不相交的子树。
树分为二叉树，平衡树，红黑树等。
在Java语言中，讨论和使用最多的是二叉树。
二叉树（binary tree）是每个结点不超过2的有序树（tree），具有如下特点：
每个结点最多有两颗子树，结点的度最大为2。左子树和右子树是有顺序的，次序不能颠倒。即使某结点只有一个子树，也要区分左右子树。
适用场景：
二叉树添加，删除元素都很快，并且在查找方面也有很多的算法优化，所以，二叉树既有链表的好处，也有数组的好处，是两者的优化方案，在处理大批量的动态数据方面具有得天独厚的优势。
扩展：
二叉树有很多扩展的数据结构，比如平衡二叉树、红黑树、B+树等。
这些数据结构在二叉树的基础上衍生了很多的功能，在实际应用中被广泛使用。
比如MySQL数据库索引结构用的是B+树，HashMap的底层源码中用到了红黑树。这些二叉树的功能强大，但算法比较复杂，想学习的话需要花时间深入，本文限于篇幅不再一一展开。
图（Graph）
（了解即可）
图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。
按照顶点指向的方向可分为无向图和有向图。
图是一种比较复杂的数据结构，有着非常复杂和高效的算法，这里不做展开，读者有兴趣可以自己学习深入
堆（Heap）
堆是一种比较特殊的数据结构，可以被看做一棵树的数组对象，具有以下的性质：
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
常见的堆有二叉堆、斐波那契堆等。
堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。
(ki <= k2i,ki = k2i,ki >= k2i+1), (i = 1,2,3,4…n/2)，满足前者的表达式的成为小顶堆，满足后者表达式的为大顶堆，这两者的结构图可以用完全二叉树排列出来，示例图如下：
因为堆有序的特点，一般用来做数组中的排序，称为堆排序。
散列表（Hash）
散列表，也叫哈希表，是根据关键码和值 (Key和Value) 直接进行访问的数据结构。
哈希值（hashCode）：是一个十进制整数，由系统随机给出（就是对象的地址值，是一个逻辑地址， 不是数据的实际存储地址。）
public class Demo02 {
public static void main(String【】 args) {
Layman layman = new Layman("layman",18);
/
public native int hashCode() : Object类中的方法，可以返回对象的哈希值(一个十进制整数)。
/
System.out.println(layman.hashCode()); //-1109720331
}
//Object类中toString()的源码
public String toString() {
return getClass().getName() + "@" + Integer.toHexString(hashCode());
}
}
@Data
@AllArgsConstructor
class Layman{
private String name;
private Integer age;
}
记录的存储位置=F(key)
散列表就是把Key通过算法函数F（哈希函数）转换成一个十进制整数，然后将该整数对数组长度进行取余，取余的结果当作数组下标，将value存储在以该数字为下标的数组空间中。
这种存储空间充分利用数组的查找优势来查找元素，所以查找速度快。
哈希表应用广泛，比如Java中有些集合类（HashMap，HashTable）就是借鉴了哈希原理构造的，查找元素时非常方便。
然而，因为哈希表是基于数组衍生的数据结构，所以增删元素慢。出于解决增删元素慢的问题，哈希表的底层采用数组+链表（数组查询快，链表增删快）。
JDK1.8之前，哈希表底层采用数组+链表实现，即使用链表处理冲突，同一hash值的数据都存储在一个链表里。但是当hash值相等的元素较多时，通过key值依次查找的效率较低。JDK1.8中，哈希表存储采用数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。
