前言
最近人有些低潮，干什么都不得劲。工作也逐渐进入安逸区，没什么有挑战性的工作，都是对之前的重复。想着把计算机基础都好好补一下，系统性的梳理一下，中国大学慕课网上面的国家精品课程看一看，极客时间上面的一些课程也好好学习一下。
以下的一些总结可能过于简陋，更多的是总纲性质的总结，更多的细枝末节，不懂为什么的，自己去找那些基础来看。简而言之，就是下面的总结很多只说了是什么，没有说为什么。
数据结构与算法总览
核心
10 个数据结构：
- 数组
- 链表
- 栈
- 队列
- 散列表
- 二叉树
- 堆
- 跳表
- 图
- Trie 树
10 个算法
- 递归
- 排序
- 二分查找
- 搜索
- 哈希算法
- 贪心算法
- 分治算法
- 回溯算法
- 动态规划
- 字符串匹配算法
算法复杂度
对于刚罗列的复杂度量级，我们可以粗略地分为两类，多项式量级和非多项式量级。其中，非多项式量级只有两个：O($n^2$) 和 O($n!$)
复杂度包括时间复杂度和空间复杂度。
虽然复杂度看似很多，但实际上常用的就下面三种：
关于复杂度本身，还可以分为：
- 最好情况时间复杂度（best case time complexity）：在最理想的情况下，执行这段代码的时间复杂度
- 最坏情况时间复杂度（worst case time complexity）：在最糟糕的情况下，执行这段代码的时间复杂度
- 平均情况时间复杂度（average case time complexity）：又可以叫做
加权平均时间复杂度或者期望时间复杂度 - 均摊时间复杂度（amortized time complexity）：均摊时间复杂度就是一种特殊的平均时间复杂度（比如对数组进行扩容操作的复杂度）
学习算法推荐书单
其实除了上述的书单，对于 Java 工程师，我尤其要推荐一本《算法》第四版。
数据结构
线性表数据结构
非线性表数据结构
数组（Array）
关于数组和链表的区别，很多人都回答说，“链表适合插入、删除，时间复杂度 O(1)；数组适合查找，查找时间复杂度为 O(1)”。
实际上，这种表述是不准确的。数组是适合查找操作，但是查找的时间复杂度并不为 O(1)。即便是排好序的数组，你用二分查找，时间复杂度也是 O($\log n$)。所以，正确的表述应该是，数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。
数组由于自身特点，插入、删除等操作比较低效，对于他们的改进可以如下：
关于插入操作：如果数组中的数据是有序的，我们在某个位置插入一个新的元素时，就必须按照刚才的方法搬移 k 之后的数据。但是，如果数组中存储的数据并没有任何规律，数组只是被当作一个存储数据的集合。在这种情况下，如果要将某个数组插入到第 k 个位置，为了避免大规模的数据搬移，我们还有一个简单的办法就是，直接将第 k 位的数据搬移到数组元素的最后，把新的元素直接放入第 k 个位置。
关于删除操作：我们可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，我们再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。
思考：容器能否完全替代数组？
Java ArrayList 无法存储基本类型，比如 int、long，需要封装为 Integer、Long 类，而 Autoboxing、Unboxing 以及动态扩容则有一定的性能消耗，所以如果特别关注性能，或者希望使用基本类型，就可以选用数组。
如果数据大小事先已知，并且对数据的操作非常简单，用不到 ArrayList 提供的大部分方法，也可以直接使用数组。
当要表示多维数组时，用数组往往会更加直观。比如 Object[][] array；而用容器的话则需要这样定义：
ArrayList<ArrayList> array。
链表（Linked list）
数组与链表内存分布区别
单链表
在链表里面，有两个结点是比较特殊的，它们分别是第一个结点和最后一个结点。我们习惯性地把第一个结点叫作头结点，把最后一个结点叫作尾结点。其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。
与数组一样，链表也支持数据的查找、插入和删除操作。
循环链表和双向链表
循环链表
和单链表相比，循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时，就特别适合采用循环链表。比如著名的约瑟夫问题。尽管用单链表也可以实现，但是用循环链表实现的话，代码就会简洁很多。
约瑟夫问题（有时也称为约瑟夫斯置换），是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。
人们站在一个等待被处决的圈子里。 计数从圆圈中的指定点开始，并沿指定方向围绕圆圈进行。 在跳过指定数量的人之后，执行下一个人。 对剩下的人重复该过程，从下一个人开始，朝同一方向跳过相同数量的人，直到只剩下一个人，并被释放。
问题即，给定人数、起点、方向和要跳过的数字，选择初始圆圈中的位置以避免被处决。
双向链表
从图中可以看出来，双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。从结构上来看，双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点，正是这样的特点，也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。
思考：如何基于链表实现 LRU 缓存淘汰算法？
缓存淘汰策略来决定。常见的策略有三种：先进先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used）。
思路如下：
我们维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。
如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
如果此数据没有在缓存链表中，又可以分为两种情况：
如果此时缓存未满，则将此结点直接插入到链表的头部；
如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。
对于指针的理解
对于指针的理解，只需要记住下面这句话就可以了：
将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针；或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。