耗时两周，我整理了一套数据结构与算法的学习路线，大厂面试必备

对于我们程序员来说，数据结构和算法是必须要掌握的内功。网络上有很多人整理过编程学习的路线图，但是有关数据结构和算法的却并不多。

为了能够帮助到更多的程序员小伙伴，小灰花了整整两周时间，整理了一份数据结构和算法的学习路线图。

这份路线图包含了115项重要的知识点，可以说是非常的全面，而且大部分知识点都附上了详细的讲解，这些讲解都是我最近五年以来陆陆续续写的原创内容。

这份路线图包含了四大部分，分别是数据结构基础、算法基础、常见面试题，以及各种学习工具。由于这张路线图比较复杂，乍一看可能会感到懵逼，因此小灰特意带着大家来导读一下：

1.数据结构基础

数据结构当中最基本也是最常用的一类，是线性数据结构，其中包括大家最熟悉的数组和链表。通过这两种基础数据结构，又可以实现出栈和队列。这几种数据结构的特性和原理，大家一定要掌握，最好是能自己用代码实现出它们的基本功能，面试常考。

除了线性数据结构以外，树也是比较常用的数据结构，其中最核心的是二叉树。手写二叉树的遍历，常常在面试中被考察，其中深度遍历比较简单，写个递归就行，层序遍历稍微复杂一些，实现的时候需要懂一些脑筋。

二叉树根据不同功能，又分成了很多具体的数据结构，最基础的是二叉查找树，可以方便元素的查找和排序。AVL树和红黑树，是二叉查找树的特殊形式，可以在多次插入删除节点之后，仍然保持树的平衡。

二叉堆也是一种特殊的二叉树，分为大顶堆和小顶堆，可以始终保证堆顶的元素是最大或者最小的一个，堆排序算法和优先级队列都用到了这个数据结构。

还有一种很有趣的二叉树，叫做哈夫曼树。它的功能是把通信报文的字符转化成哈夫曼编码，从而压缩通信报文的总长度。

除了二叉树之外，我们工作中也会用到一些非二叉树，最常用的就是B-树和B+树。我们电脑上文件系统的索引，很多就是用B-树实现的，而我们常用的关系型数据库，默认索引就是用B+树实现。

此外，还有一种叫做前缀树的结构，可以通过单词的前缀来快速匹配到我们想要查找的单词。

说完了树结构，我们再来说一说图。图这种数据结构，相对来说不算是很常用，我们对它有一个基本的了解就可以。

首先我们要知道，图可以按照两个维度来划分，有向图和无向图，带权图和无权图。

其次，图的遍历有两种方式，广度优先遍历和深度优先遍历。

图结构会使用到一类重要的算法：最短路径算法。其中Dijkstra算法可以求出某顶点到另一个顶点的最短路径，也就是单源最短路径；Floyd算法可以求出所有顶点到某一顶点的最短路径，也就是多源最短路径。

另外，最小生成树大家也可以了解一下，它是图的一部分，保证所有顶点都连通的情况下，总成本最小。

除了上面讲的这些数据结构以外，还有一些复合数据结构也很重要。

比如大家最熟悉的哈希表，是数组与链表的结合，大家需要了解哈希表的基本原理，以及如何解决哈希冲突。这个大厂面试必考。

除了哈希表以外，哈希链表也很常用。我们Redis数据库当中用到的LRU算法，背后就用到了哈希链表。

还有两种复合数据结构可能知道的人不多，一个是跳表，它在链表的基础上增加了很多层级，主要为了提升链表的查询效率。另一个是线段树，他是数组和二叉树的结合，方便在局部范围内对数组进行操作。

2.算法基础

数据结构基础就说到这里，接下来我们说一说算法基础。要学习算法，首先要弄懂算法到底是什么，同时也要理解衡量算法好坏的重要指标：时间复杂度和空间复杂度。

排序算法，可以说是程序员最常用的一类算法。

排序算法同样可以按照不同的维度进行分类，以相等元素的位置是否改变作为条件，可以分成稳定排序和不稳定排序；以排序过程是否在内存中完成为条件，可以分成内部排序和外部排序。

以时间复杂度为条件，又可以划分为更多的类型，时间复杂度O（n^2）的排序，包括冒泡排序、选择排序、插入排序；O（nlogn）的排序，包括快速排序、归并排序、堆排序、锦标赛排序；线性时间复杂度的排序，包括计数排序，桶排序，基数排序。至于希尔排序的时间复杂度比较特殊，取决于每一轮分组的方式。最后，还有一些排序算法没有什么实用性，纯粹是用来搞笑的，比如猴子排序、睡眠排序，以及珠排序。