数据结构
数据结构是计算机存储、组织数据的方式。
数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
逻辑结构
逻辑结构就是数据之间的关系。
集合结构
处于同一数据集合中的元素之间除同属该集合这一联系外没有其他的关系。
线性结构
线性结构是一个有序数据元素的集合。
树形结构
树形结构指的是数据元素之间，存在着“一对多”的树形关系的数据结构，可表示从属关系、并列关系。
图形结构
任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的，也就是可以多对多。
存储结构
存储结构是逻辑结构的存储映像，存储结构为逻辑结构用计算机语言的实现。
线性结构
线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系。
a1是a2的前驱，ai+1 是ai的后继，a1没有前驱，an没有后继
n为线性表的长度 ，若n==0时，线性表为空表
顺序表(顺序存储结构)
寻址容易
顺序表可以存储重复的元素，而且可以指定元素存储的位置并根据下表访问元素。使用连续的存储空间。尾插效率高，支持随机访问，在非尾部的位置插入或者删除会导致整个存储空间的偏移，效率低。
数组 ArrayList(动态创建的数组) 都是顺序表
链表(链式存储结构)
插入与删除容易
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的，需要在线性表的任意位置插入或者删除元素，可以选择链表。
单链表
单链表，拥有指向下一节点的指针。查找元素需要从头结点遍历
MessageQueue 就是单链表的实现
单循环链表
在单链表中，将终端结点的指针域NULL改为指向表头结点即可
双链表
双链表拥有指向上一节点和下一节点的指针。相对于单链表，在找当前节点的前一节点时比较方便。
LinkedList 就是双向链表的实现
双循环链表
双循环链表可以从任何结点开始任意向前向后双向访问。
堆栈
先进后出，限定仅在表尾进行插入和删除操作的线性表。
队列
先进先出，它只允许在表的前端（front）进行删除操作，而在表的后端进行插入操作。
非线性结构
非线性结构，其逻辑特征是一个结点元素可能有多个直接前驱和多个直接后继。
哈希表(散列表)
寻址容易，插入删除也容易的数据结构，扩容需要消费大量的空间和性能。
是根据关键码值(Key value)而直接进行访问的数据结构，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。
存放记录的数组叫做散列表
映射存放位置函数叫做散列函数
装填因子：数据总数 / 哈希表长，装填因子越大哈希冲突机会越大
哈希冲突的意思是不同的key用散列函数算出来的值相同
例如
Key : {14, 19, 5, 7, 21, 1, 13, 0, 18}
散列表: 大小为13 的数组 a[13];
散列函数: f(x) = x mod 13;
解决哈希碰撞方案
拉链法
用拉链法处理冲突的办法是：把具有相同散列地址的关键字的值放在同一个单链表中，这也是jdk1.8之前的做法。
缺点是当数据量大有可能某一个单链表长度特别长。
所以在jdk1.8后当链表长度超过阈值，就转换成红黑树。
树
它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树。
二叉树
二叉树（binary tree）是指树中节点的度不大于2的有序树
图
其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。结点也可以称为顶点
算法
算法是指解题方案的准确而完整的描述，一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
空间复杂度
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。
语句总占用存储空间大小记为S(n)
当所处理的数据有N个元素时，该算法还需额外消耗多少元素大小的内存空间，记为f(N)。常用大O表示法，大O表示法就是将算法的所有步骤转换为代数项，然后排除不会对问题的整体复杂度产生较大影响的较低阶常数和系数。
公式表达：
S(n)=O(f(n))称作算法的渐进空间复杂度，简称空间复杂度。（就是当n趋于无穷大的时候，f(n) 得到的极限值）
时间复杂度
算法的时间复杂度是一个函数，它描述该算法的运行时间。
语句总的执行次数记为T(N)
一个算法语句总的执行次数是关于问题规模N的某个函数，记为f(N)。
N称为问题的规模，当N不断变化时，T(N)也在变化，算法执行次数的增长速率和f(N)的增长速率相同。
时间复杂度常用大O表示法，大O表示法就是将算法的所有步骤转换为代数项，然后排除不会对问题的整体复杂度产生较大影响的较低阶常数和系数。
公式表达：
T(N) = O(f(N)) 称作算法的渐进时间复杂度，简称时间复杂度。（就是当n趋于无穷大的时候，f(n) 得到的极限值）
穷举法
也叫作暴力法，枚举法或者蛮力法