常用的数据结构有：数组、栈、链表、队列、树、图、堆、散列表
数组：按照索引查询元素速度快，按照索引便利方便 ；数组的大小固定后无法扩容了；数组只能存储一种类型的数据；添加、删除操作效率低，要移动其他元素 使用场景 ：频繁查询，对存储空间要求不大，很少增加和删除的情况

栈：一种特殊的线性表，特点是先进后出， 使用场景：常用于实现递归功能方面的场景

队列：也是一种线性表，特点是先进先出，使用场景：所以在多线程队列阻塞，队列管理较适用。

链表：链表在屋里存储单元上是非连续的，非顺序的存储结构，数据元素的逻辑是通过连表的指针地址实现，每个元素包含两个节点，一个是存储元素的数据域，另一个是指向下一个节点地址的指针域。 可以形成不同结构：单链表，双链表，循环链表等
不需要初始化容量，可以任意加减元素，删除很快，添加或删除元素只需要修改前后两个元素节点的指针域指向。
适用场景： 数据量较小，需要频繁增加、删除的场景

树：是由n个有限节点组成一个具有层次关系的集合， 使用的最多的结构是二叉树 使用场景：添加、删除元素都很快，在查找方面也有很多算法优化，既有链表的好处、也有数组的好处，是两者的优化方案，在处理大批量动态数据时有用

二叉树也有很多扩展：如平衡二叉树、红黑树、B+树等
mysql索引用的B+树，HashMap底层源码用到红黑树，

◎ 散列表：也叫哈希表，用的是数组支持按照下标随机访问数据的特性，所以散列表是数组的一种扩展，根据key和value直接访问的数据结构，通过key和value映射到集合中的一个位置，很快就能找到集合中对应的元素 使用场景 java中的有些集合类就是借鉴哈希原理构造，比如HashMap、HashTable等，利用hash表优势，对集合的元素查找方便。 但是添加元素比较慢，所以很多时候用到数组链表来做，也即是拉链法，早期HashMap底层就是用拉链法，jdk1.8后换成了数组+红黑树的结构，

◎ 散列冲突
1，开放寻址法
思想是如果出现了散列冲突，就重新探测一个空闲位置
2，链表法 将所有关键字为同义词的记录存储在一个单链表中，称这种表为同义词子表

堆；可以被看成一棵树的数组对象，堆总是一颗完全二叉树、堆的某个节点的值总是不大于或不小于其父节点的值
使用场景：由于堆有序的特点，一般用来做数组中的排序，称为堆排序

图：由节点的有穷集合V和边的集合E组成， 图是一种较为复杂的数据结构，在存储上有着比较复杂和高效的算法， 分别有。邻接矩阵，邻接表，十字链表，邻接多重表等结构。

内部排序： 1、选择排序： #直接选择排序。#堆排序
2、插入排序： #直接插入排序。#希尔排序
3、比较排序； #冒泡排序。 #快速排序
4、归并排序
5、基数排序

◎ 栈、堆：
栈与堆实际上是操作系统对进程占用的内存空间的两种管理方式
区别：1、管理方式不同，栈由系统自动分配释放，无需手动控制（数组）；而堆的申请和释放工作由程序员控制，容易产生内存漏洞（链表）
2、空间大小不同，每个进程拥有的栈的大小远远小于堆的大小
3、生长方向不同，堆的生长方向向上，内存地址由低到高，但是后申请的内存空间并不一定在先申请内存空间的后面，因为先申请的堆空间一旦被释放，后申请的内存空间则会利用被释放的内存，导致先后分配的内存空间在地址上不存在先后关系；栈的生长方向向下，内存地址由高到低

4、分配方式不同，堆是动态分配；而栈分配有静态分配和动态分配，静态分配是由操作系统完成的，比如局部变量分配，动态分配用alloca函数进行分配

5、生存周期，如果堆中的数据未释放，则其生命周期等同与程序的生命周期