数据结构-线性表
线性表结构：线性表：数组、链表、栈、队列
1.数组：连续的内存空间。
1.1 查找：随机查找的时间复杂度为O(1)，注意，只是随机查找（用下标的方式）。排序后的二分查找时间复杂度O(logn)
中间插入和删除：需要搬移元素位置，时间复杂度为O(n)
开头和结尾插入和删除：O(1)
插入优化技巧：如果条件允许，插入到第K个位置时，可以把第K个位置的元素移动到最后，减少数据搬运
删除优化技巧：如果条件允许，可以几个删除一起后，再搬移元素。（类似JVM的垃圾回收，标记清除法）
1.2 JAVA中的ArrayList封装了数组，相比数组优势：动态扩容。
（1）扩容时，新建一个大的数组，然后数据拷贝到这个新的数组。
（2）扩容大小：原来容量的1.5倍
（3）数组和ArrayList的选择：一般使用ArrayList，但是对于底层框架的开发，需要把性能做到极致，可以选择数组。
1.3 二维数组可以表示矩阵
针对稀疏矩阵的表示：如果直接表示会浪费存储空间。可以采用三项式来表示。
A(0,1)表示矩阵的行数
A(0,2)表示矩阵的列数
A(0,3)表示矩阵的非零项的总数
A(i,j,value) 表示非零的项。i从1开始，第i行第j列的值为value
1.4 数组和多项式
P(x) = a0 + a1x + a2*x^2 + a3*x^3 + ... + + an*x^n
比如 2x^5 + 3x^4 + 5x^2 + 4x + 1
方法一：使用n+2长度的一维数组存储，第一个元素是最大的指数n，其余元素按n递减存储多项式的系数。如果没有的存储0
A = {5,2,3,0,5,4,1} ，其中这里没有x^3的系数，所以第四项为0
缺点：如果有x^100,那么素组的长度为100+1
方法二：只存储多项式非零项。第一个元素为多项式非零项的个数。
A = {5,2,5,3,4,5,2,4,1,1,0}
缺点：计算时可能会更复杂些
2.链表：不要求内存空间连续
2.1 插入和删除：适合大量的操作 O(1)；查询： O(n)
2.2 JAVA中的LinkedList为双向链表，有next也有previous
LinkedList可以实现栈、队列以及双端队列等数据结构
LinkedList可以实现LRU缓存机制
2.3 单向链表：指针和数据（第一个接节点是链表头指针，最后一个指针设置为null）
循环链表：最后一个指针指向链表头部，从任何一个节点入手，可以遍历所有其他节点
环形链表：通常应用于内存工作区与输入/处处缓冲区
双向链表：优势是可以轻松找到前后节点
双向循环链表
2.4 链表和多项式：和数组的方法一样，只是链表实现的好处是适合多项式内容变动
2.5 环形链表可以实现稀疏矩阵：优点是矩阵变更时不需要大量移动数据
3.跳表（跳跃表）：通过多级索引使得链表能够实现二分查找，加速链表的随机查询效率，似于二分查找。
查询（不支持随机查询）：O(logn)
空间复杂度：O(n)
场景： Redis使用了跳表。
HBase MemStore的也使用的跳表。为什么呢？
HBase 属于 LSM Tree 结构的数据库，LSM Tree 结构的数据库有个特点，实时写入的数据先写入到内存
内存达到阈值往磁盘 flush 的时候，会生成类似于 StoreFile 的有序文件，而跳表恰好就是天然有序的
所以在 flush 的时候效率很高，而且跳表查找、插入、删除性能都很高，这应该是 HBase MemStore 内部存储数据使用跳表的原因之一。
HBase 使用的是 java.util.concurrent 下的 ConcurrentSkipListMap()。
4.栈：先入后出，看成桶。（操作受限的数组或链表结构）
4.1 添加、删除复杂度都是O(1)；查询： O(n)
4.2 可以数组实现（顺序栈）和链表实现（链式栈）（数组不利于大小动态变化，但是优点是编程简单）只需要一个top指针指向栈顶元素。
4.3 应用：浏览器前进后退
函数调用
表达式取值
5.队列Queue：先入先出，通俗理解：排队。（操作受限的数组或链表结构）
5.1 添加、删除复杂度都是O(1)；查询： O(n)
在高级语言中，一般不用纯粹的栈和队列，java可以用双端队列替代。
5.2 可以数组（顺序队列）和链表（链式队列）实现。
线程池中的各种策略：
链表实现：无界队列，不合适响应时间敏感的。
数组实现：有界队列，适合响应时间敏感的。
环形队列与链式队列的选择：如果可以确定最大的大小，那么选择环形队列。如果不能确定，那么选择链式队列。
5.3 需要两个指针front和rear分别指向前端和后端。
5.4 应用：作业调度、磁盘的缓冲区。
5.5 双端队列Deque：两边都可以进出。两边都需要front和rear指针。
5.6 循环队列 ： MapReduce中Shuffle时使用了。
注意：环形队列是使用数组实现的，解决顺序队列的数据搬运问题。
5.7 优先队列Priority Queue
插入和删除：O(1)
取出操作：O(logn)，按照优先级
底层实现可以多样：heap、bst、treap
java中实现：PriorityQueue
5.8 阻塞队列和并发队列（CAS）
6.哈希表Hash table（散列表）：通过哈希函数（散列函数）映射值。
6.1 模型：Hash函数得到数组下标 -> 数组（链表作为数组的元素）
插入和删除：O(1)
查询：O（1）
说明：可能后面链表查询的复杂度不为1，但是一般hashCode一致的比较少，
所以链表的元素个数其实很有限，可以认为就是O(1)。
6.2 哈希函数
（1）除后取余数法
（2）平方取中
6.3 java 7中的HashMap是数组和链表的结合体。JAVA 8中是数组 + 红黑树实现（size达到8个的适合，就会由链表转换成红黑树）。
（1）对象的HashCode是用来在散列存储结构中确定对象的存储地址的。
（2）如果两个对象的HashCode相同，即在数组中的地址相同。而数组的元素是链表。这两个对象会放在同一链表上。
（3）如何确定是同一个对象？ 通过equals方法。
（4）HashMap默认的加载因子是0.75，默认最大容量是16。
因此可以得出HashMap的默认实际容量是：0.75*16=12，到了12就会扩容。
扩容大小：扩容原来的一倍。
还有常用的 HashMap HashSet。
7. 应用：算术表达式的表示方法
中序法（操作数1-运算符-操作数2）： 2*3 + 4*5
中序表达法符合人的习惯，不过计算机处理不方便
前序法（运算符-操作数1-操作数2）： +*23*45
常用的计算机处理方式
后序法（操作数1-操作数2-运算符）： 23*45*+
常用的计算机处理方式（比前序常用）
7.1 利用堆栈实现表达式运算：最简单的是后续表达式求值-只需要一个栈。
7.2 可以使用二叉树的方法
7.3 中序转前序/后序
2*3 + 4*5
（1）括号法: 先括号括起来((2*3) + (4*5))
中序转前序
用括号内的运算符替代左括号，近者优先：+*23)*45))
去掉所有右括号：+*23*45
中序转后序
用括号内的运算符替代右括号，近者优先：((23* (45*+
去掉所有左括号：23*45*+
（2）堆栈法
7.4 前序或后序转中序
（1）括号法
（2）堆栈法