数组
数组（Array） 是一种线性表（Linear List）数据结构。它用一组连续的内存空间(对内存要求比较高)，来存储一组具有相同类型的数据。
因如上特点，通过寻址公式，可随机访问数组中元素，时间复杂度为O（1）。但为保证连续性，在数组中删除插入数据时，需要做大量数据搬移工作，时间复杂度是O（n）
小技巧：插入操作做成两个元素互换；删除操作先记录下已删除的数据再统一删除。（JVM标记清除垃圾回收算法）
数组从0开始编号：考虑寻址公式a[k]_address = base_address + k * type_size，便于计算。另历史原因，java沿用C习惯
ArrayList（容器类）：将很多数组操作的细节封装起来，如插入删除搬移数据。支持动态扩容（扩为1.5倍）。但扩容耗时，最好事先指定数据大小。
Array优势：省去自动装箱拆箱的性能消耗，多维数组更直观，操作简单用不到ArrayList大部分方法时可直接用数组。
链表
链表（Linked List）通过指针将一组零散的内存块串联起来使用。
结点：即内存块，存储数据并记录链上下一个结点的地址，记录下一个结点地址的指针叫后继指针next。头结点记录链表基地址，尾结点指向空地址NULL。
单链表的插入删除操作只需要考虑相邻结点的指针改变，时间复杂度O(1)
单链表随机访问需根据指针一个结点一个结点依次遍历，时间复杂度O(n)
循环链表尾结点指针指向链表头结点，处理环形结构的数据方便。
双向链表每个结点有后继指针next和前驱指针prev，需额外两个控件存储后继和前驱指针地址，占内存。但支持双向遍历，操作灵活，查找遍历高效。
LinkedHashMap实现用到双向链表结构。
空间换时间设计思想：内存充足时可选择空间复杂度较高时间复杂度较低的算法或数据结构，否则相反。
数组与链表：数组连续存储对CPU缓存友好，链表不友好，链表需存储指向下一个结点的指针地址更耗内存，且对链表频繁插入删除容易造成内存碎片（Java频繁GC）；数组大小固定，链表没有大小限制天然支持扩容；
指针：将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。
带头链表不管链表是否为空，head指针一直指向不存储数据的哨兵结点。
因为哨兵结点一直存在，所以插入/删除第一个结点或其他结点都可以统一为相同的代码实现，这种利用哨兵简化编程难度的技巧很常用，如插排，归并，动态规划等。
常见的缓存淘汰策略：先进先出（ FIFO）,最少使用（LFU），最近最少使用（LRU，可考虑有序单链表实现，新入列存表头）
栈
栈结构 操作受限的线性表数据结构，只允许在一端插删数据(入栈出栈)，先进后出，后进先出。
顺序栈 用数组实现，操作栈顶指针，入栈出栈空间复杂度O(1)；可改造以支持动态扩容，则入栈需重新申请内存和数据搬移时，时间复杂度O(n)，按摊还分析法，入栈均摊时间复杂度为O(1)。
链式栈 用链表实现，入栈出栈空间复杂度O(1)。
应用：函数调用栈；编译器实现表达式求值；括号匹配；使用两个栈实现浏览器前进后退
队列
队列 同为操作受限的线性表数据结构，支持入队出队，先进先出。
顺序队列 用数组实现有界队列，操作队头(head)指针，队尾(tail)指针,判断队空(head == tail)队满(tail == n)需考虑数据搬移的成本，入队队满时统一处理搬移。
大部分资源有限的场景如线程池请求排队，数据库连接池等，没有空闲资源时基本上都可以通过“队列”实现请求排队。
链式队列 用链表实现，可实现一个支持无限排队的无界队列（过多等待响应时间过长）
循环队列 避免数据搬移，关键要确定好队空(head == tail)和队满((tail + 1)%n==head)的判定条件
阻塞队列队列为空阻塞队头读取操作，队列已满阻塞插入操作，可用于实现生产者-消费者模型。
并发队列线程安全的队列
应用：具有额外特性的队列如循环队列，阻塞队列，并发队列，在很多偏底层系统框架中间件的开发中起关键作用。如高性能队列Disruptor，Linux环形存储（循环并发队列）；Java concurrent 并发包用ArrayBlockingQueue实现公平锁。
要点补充：递归
递归需满足的三个条件
- 一个问题的解可分解为几个子问题的解 （思考时假设子问题已解决，屏蔽递归细节）
- 这个问题与分解之后的子问题，除数据规模不同，求解思路完全一样
- 存在递归终止条件
编写递归代码的关键点
- 写出递推公式
- 找到终止条件
n级台阶的走法：f(n) = f(n - 1) + f(n - 2)，终止条件为f(1) = 1, f(2) = 2
int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return f(n - 1) + f(n - 2);
}
递归代码需警惕的点
- 堆栈溢出 ：递归求解数据规模较大，调用层次深一直压入栈，有堆栈溢出的风险。可在代码中限制递归调用
最大深度解决该问题(实际跟当前线程剩余栈空间大小有关，深度较小适用)。 - 重复计算 ： 可通过一个数据结构（如散列表）保存已求解过的f(k)，调用时先检查。
- 时间效率
- 空间开销
- 脏数据造成的
无限递归和递归环
参考：《数据结构与算法之美》王争
网友评论