一、数组

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

1）线性表（Linear List）

　　顾名思义，线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。

2）非线性表

　　比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。

3）连续的内存空间和相同类型的数据

　　正是因为这两个限制，它才有了一个堪称“杀手锏”的特性：“随机访问”。

　　这两个限制也让数组的很多操作变得非常低效，比如要想在数组中删除、插入一个数据，为了保证连续性，就需要做大量的数据搬移工作。

4）误区

　　在面试的时候，常常会问数组和链表的区别，很多人都回答说，“链表适合插入、删除，时间复杂度 O(1)；数组适合查找，查找时间复杂度为 O(1)”。

　　实际上，这种表述是不准确的。数组是适合查找操作，但是查找的时间复杂度并不为 O(1)。即便是排好序的数组，你用二分查找，时间复杂度也是 O(logn)。

　　所以，正确的表述应该是，数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。

二、链表

　　数组和链表的区别如下：

　　（1）数组需要一块连续的内存空间来存储，对内存的要求比较高。

　　（2）链表恰恰相反，它并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用。

　　三种最常见的链表结构，它们分别是：单链表、双向链表和循环链表。

1）单链表

　　链表通过指针将一组零散的内存块串联在一起。其中，把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。把这个记录下个结点地址的指针叫作后继指针 next。

　　与数组一样，链表也支持数据的查找、插入和删除操作。

　　（1）删除一个数据是非常快速的，只需考虑相邻结点的指针改变，所以对应的时间复杂度是 O(1)。

　　（2）链表随机访问的性能没有数组好，需要 O(n) 的时间复杂度。

2）循环链表

　　循环链表是一种特殊的单链表。实际上，循环链表也很简单。

　　它跟单链表唯一的区别就在尾结点。循环链表的优点是从链尾到链头比较方便。

　　当要处理的数据具有环型结构特点时，就特别适合采用循环链表。比如著名的约瑟夫问题。

3）双向链表

　　顾名思义，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。

　　双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点，正是这样的特点，也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。

　　双向链表尽管比较费内存，但还是比单链表的应用更加广泛。实际上，这里有一个更加重要的知识点需要你掌握，那就是用空间换时间的设计思想：

　　对于执行较慢的程序，可以通过消耗更多的内存（空间换时间）来进行优化；而消耗过多内存的程序，可以通过消耗更多的时间（时间换空间）来降低内存的消耗。

4）应用场景

　　一个经典的链表应用场景，那就是 LRU 缓存淘汰算法。

　　常见的缓存清理策略有三种：先进先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used）。

　　用链表实现的思路是这样的：维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，从链表头开始顺序遍历链表。

　　（1）如果此数据之前已经被缓存在链表中了，遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。

　　（2）如果此数据没有在缓存链表中，又可以分为两种情况：

　　　　如果此时缓存未满，则将此结点直接插入到链表的头部；

　　　　如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。

　　这种基于链表的实现思路，缓存访问的时间复杂度为 O(n)。

5）边界条件

　　检查链表代码是否正确的边界条件有这样几个：

　　（1）如果链表为空时，代码是否能正常工作？

　　（2）如果链表只包含一个结点时，代码是否能正常工作？

　　（3）如果链表只包含两个结点时，代码是否能正常工作？

　　（4）代码逻辑在处理头结点和尾结点的时候，是否能正常工作？

6）链表题目

　　精选了 5 个常见的链表操作。只要把这几个操作都能写熟练，不熟就多写几遍，保证你之后再也不会害怕写链表代码。

　　（1）单链表反转

　　（2）链表中环的检测

　　（3）两个有序的链表合并

　　（4）删除链表倒数第 n 个结点

　　（5）求链表的中间结点

三、栈

　　后进者先出，先进者后出，这就是典型的“栈”结构。

　　从栈的操作特性上来看，栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。

　　但你要知道，特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。

1）实现

　　实际上，栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。注意：

　　（1）在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是 O(1)。

　　（2）不管是顺序栈还是链式栈，入栈、出栈只涉及栈顶个别数据的操作，所以时间复杂度都是 O(1)。

2）应用场景

　　比较经典的一个应用场景就是函数调用栈。

　　（1）操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构, 用来存储函数调用时的临时变量。

　　（2）每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。

　　另一个常见的应用场景，编译器如何利用栈来实现表达式求值。

　　比如：34+13*9+44-12/3。对于这个四则运算，人脑可以很快求解出答案，但是对于计算机来说，理解这个表达式本身就是个挺难的事儿。

　　（1）实际上，编译器就是通过两个栈来实现的。其中一个保存操作数的栈，另一个是保存运算符的栈。

　　（2）从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较。

　　（3）如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。

　　除了用栈来实现表达式求值，还可以借助栈来检查表达式中的括号是否匹配。

　　比如，{[] ()[{}]}或[{()}([])]等都为合法格式，而{[}()]或[({)]为不合法的格式。

　　（1）用栈来保存未匹配的左括号，从左到右依次扫描字符串。当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号。

　　（2）如果能够匹配，比如“(”跟“)”匹配，“[”跟“]”匹配，“{”跟“}”匹配，则继续扫描剩下的字符串。

　　（3）如果扫描的过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。

四、队列

　　先进者先出，这就是典型的“队列”。

　　队列跟栈非常相似，支持的操作也很有限，最基本的操作也是两个：

　　（1）入队 enqueue()，放一个数据到队列尾部；

　　（2）出队 dequeue()，从队列头部取一个元素。

　　作为一种非常基础的数据结构，队列的应用也非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。

1）实现

　　用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。

　　对于栈来说，只需要一个栈顶指针就可以了。但是队列需要两个指针：一个是 head 指针，指向队头；一个是 tail 指针，指向队尾。

2）循环队列

　　顾名思义，它长得像一个环。原本数组是有头有尾的，是一条直线。现在我们把首尾相连，扳成了一个环。

3）阻塞队列

　　简单来说，就是在队列为空的时候，从队头取数据会被阻塞。如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据。

　　上述的定义就是一个“生产者 - 消费者模型”！可以有效地协调生产和消费的速度。

　　基于阻塞队列，还可以通过协调“生产者”和“消费者”的个数，来提高数据的处理效率。

4）并发队列

　　最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。

　　实际上，对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。

五、跳表

　　跳表（Skip List）是一种各方面性能都比较优秀的动态数据结构，可以支持快速地插入、删除、查找操作，写起来也不复杂，甚至可以替代红黑树（Red-black Tree）。

1）实现

　　对于一个单链表来讲，即便链表中存储的数据是有序的，如果我们要想在其中查找某个数据，也只能从头到尾遍历链表。这样查找效率就会很低，时间复杂度会很高，是 O(n)。

　　如果在链表上加一层索引之后，查找一个结点需要遍历的结点个数减少了，也就是说查找效率提高了。

　　这种链表加多级索引的结构，就是跳表。

　　在一个单链表中查询某个数据的时间复杂度是 O(n)，在跳表中查询任意数据的时间复杂度就是 O(logn)，空间复杂度是 O(n)。

2）索引的空间复杂度

　　假设第一级索引需要大约 n/3 个结点，第二级索引需要大约 n/9 个结点。每往上一级，索引结点个数都除以 3。

　　为了方便计算，假设最高一级的索引结点个数是 1。把每级索引的结点个数都写下来，就是一个等比数列。

　　通过等比数列求和公式，总的索引结点大约就是 n/3+n/9+n/27+…+9+3+1=(n-1)/2，空间复杂度就是 O(n)。

六、散列表

　　散列表（Hash Table）平时也叫“哈希表”或者“Hash 表”。散列表用的是数组支持的按照下标随机访问数据的特性，时间复杂度是 O(1) ，所以散列表其实就是数组的一种扩展，由数组演化而来。

　　例如参赛选手的编号我们叫做键（key）或者关键字。用它来标识一个选手。

　　把参赛编号转化为数组下标的映射方法就叫作散列函数（或“Hash 函数”“哈希函数”），而散列函数计算得到的值就叫作散列值（或“Hash 值”“哈希值”）。

1）散列函数

　　顾名思义，它是一个函数。可以把它定义成 hash(key)，其中 key 表示元素的键值，hash(key) 的值表示经过散列函数计算得到的散列值。

　　散列函数设计的基本要求：

　　（1）散列函数计算得到的散列值是一个非负整数；

　　（2）如果 key1 = key2，那 hash(key1) == hash(key2)；

　　（3）如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。

2）散列冲突

　　再好的散列函数也无法避免散列冲突，常用的散列冲突解决方法有两类，开放寻址法（open addressing）和链表法（chaining）。

　　（1）开放寻址法的核心思想是，如果出现了散列冲突，就重新探测一个空闲位置，将其插入。

　　对于开放寻址冲突解决方法，除了线性探测方法之外，还有另外两种比较经典的探测方法，二次探测（Quadratic probing）和双重散列（Double hashing）。

　　不管采用哪种探测方法，当散列表中空闲位置不多的时候，散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率，会尽可能保证散列表中有一定比例的空闲槽位。

　　用装载因子（load factor）来表示空位的多少。装载因子的计算公式是：

散列表的装载因子 = 填入表中的元素个数 / 散列表的长度

　　装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。

　　（2）在散列表中，每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。

七、二叉树

　　树（Tree）有三个比较相似的概念：高度（Height）、深度（Depth）、层（Level）。

　　除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫做满二叉树（编号2）。

　　叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做完全二叉树（编号3）。

　　如果某棵二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式。讲到堆和堆排序的时候，你会发现，堆其实就是一种完全二叉树，最常用的存储方式就是数组。

1）遍历

　　二叉树的遍历有三种，前序遍历、中序遍历和后序遍历。遍历的时间复杂度是 O(n)。

　　（1）前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。

　　（2）中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。

　　（3）后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。

2）二叉查找树

　　二叉查找树（Binary Search Tree，BST）最大的特点就是，支持动态数据集合的快速插入、删除、查找操作。

　　二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

　　除了插入、删除、查找操作之外，二叉查找树中还可以支持快速地查找最大节点和最小节点、前驱节点和后继节点。

　　还有一个重要的特性，就是中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是 O(n)，非常高效。因此，二叉查找树也叫作二叉排序树。

　　不管操作是插入、删除还是查找，时间复杂度其实都跟树的高度成正比，也就是 O(height)。

八、红黑树

　　平衡二叉树的严格定义是这样的：二叉树中任意一个节点的左右子树的高度相差不能大于 1。最先被发明的平衡二叉查找树是AVL 树。

　　红黑树的英文是“Red-Black Tree”，简称 R-B Tree。它是一种不严格的平衡二叉查找树。

　　顾名思义，红黑树中的节点，一类被标记为黑色，一类被标记为红色。除此之外，一棵红黑树还需要满足这样几个要求：

　　（1）根节点是黑色的；

　　（2）每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；

　　（3）任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；

　　（4）每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；

　　红黑树中包含最多黑色节点的路径不会超过 log2^n，所以加入红色节点之后，最长路径不会超过 2log2^n，也就是说，红黑树的高度近似 2log2^n。

　　红黑树是一种平衡二叉查找树。它是为了解决普通二叉查找树在数据更新的过程中，复杂度退化的问题而产生的。

　　红黑树的高度近似 log2^n，所以它是近似平衡，插入、删除、查找操作的时间复杂度都是 O(logn)。

九、堆

　　堆（Heap）是一种特殊的树。

　　（1）堆是一个完全二叉树；

　　（2）堆中每一个节点的值都必须大于等于或小于等于其子树中每个节点的值，前者叫大顶堆，后者叫小顶堆。

　　完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。因为我们不需要存储左右子节点的指针，单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点。

　　数组中下标为 i 的节点的左子节点，就是下标为 i*2 的节点，右子节点就是下标为 i*2+1 的节点，父节点就是下标为 2/i 的节点。

1）堆化

　　将堆进行调整，让其重新满足堆的特性，这个过程叫做堆化（heapify）。

　　堆化非常简单，就是顺着节点所在的路径，向上或者向下，对比，然后交换。

　　让新插入的节点与父节点对比大小。如果不满足子节点小于等于父节点的大小关系，就互换两个节点。

2）应用场景

　　堆这种数据结构几个非常重要的应用：优先级队列、求 Top K 和求中位数。

　　（1）优先级队列中数据的出队顺序不是先进先出，而是按照优先级来，用堆来实现是最直接、最高效的。往优先级队列中插入一个元素，就相当于往堆中插入一个元素；从优先级队列中取出优先级最高的元素，就相当于取出堆顶元素。应用场景包括赫夫曼编码、图的最短路径、最小生成树算法等。

　　（2）维护一个大小为 K 的小顶堆，顺序遍历数组，从数组中取出数据与堆顶元素比较。如果比堆顶元素大，就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理，继续遍历数组。这样等数组中的数据都遍历完之后，堆中的数据就是前 K 大数据了。

　　（3）维护两个堆，一个大顶堆，一个小顶堆。大顶堆中存储前半部分数据，小顶堆中存储后半部分数据，且小顶堆中的数据都大于大顶堆中的数据。

十、图

　　图（Graph）和树比起来，这是一种更加复杂的非线性表结构。

　　树中的元素我们称为节点，图中的元素我们就叫做顶点（vertex）。图中的一个顶点可以与任意其他顶点建立连接关系。我们把这种建立的关系叫做边（edge）。度（degree）就是跟顶点相连接的边的条数。

　　把这种边有方向的图叫做“有向图”。以此类推，我们把边没有方向的图就叫做“无向图”。在有向图中，我们把度分为入度（In-degree）和出度（Out-degree）。

　　在带权图（weighted graph）中，每条边都有一个权重（weight），我们可以通过这个权重来表示 QQ 好友间的亲密度。

　　图最直观的一种存储方法就是，邻接矩阵（Adjacency Matrix）。

十一、Trie树

　　Trie 树，也叫“字典树”。顾名思义，它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。

　　Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。

　　当在 Trie 树中查找一个字符串的时候，比如查找字符串“her”，那将要查找的字符串分割成单个的字符 h，e，r，然后从 Trie 树的根节点开始匹配。

　　每次查询时，如果要查询的字符串长度是 k，那只需要比对大约 k 个节点，就能完成查询操作。

　　跟原本那组字符串的长度和个数没有任何关系。所以说，构建好 Trie 树后，在其中查找字符串的时间复杂度是 O(k)，k 表示要查找的字符串的长度。

　　实际上，Trie 树只是不适合精确匹配查找，这种问题更适合用散列表或者红黑树来解决。Trie 树比较适合的是查找前缀匹配的字符串。