本文我们来介绍一下编程中常见的一些数据结构。

为什么要学习数据结构？

随着业务场景越来越复杂，系统并发量越来也高，要处理的数据越来越多，特别是大型互联网的高并发、高性能、高可用系统，对技术要求越来越高，我们引入各种中间件，这些中间件底层涉及到的各种数据结构和算法，是其核心技术之一。如：

ElasticSearch中用于压缩倒排索引内存存储空间的FST，用于查询条件合并的SkipList，用于提高范围查找效率的BKDTree；
各种分库分表技术的核心：hash算法；
Dubbo或者Nginx等的负载均衡算法；
MySQL索引中的B树、B+树等；
Redis使用跳跃表作为有序集合键的底层实现之一；
Zookeeper的节点树；
J.U.C并发包的各种实现的阻塞队列，AQS底层实现涉及到的链式等待队列；
JDK对HashMap的Hash冲突引入的优化数据结构红黑树...

可以发现，数据结构和算法真的是无处不在，作为一个热爱技术，拒绝粘贴复制的互联网工程师，怎么能不掌握这些核心技术呢？

与此同时，如果你有耐心听8个小时通俗易懂的数据结构入门课，我强烈建议你看一下以下这个视频，来自Google一位工程师：Data Structures Easy to Advanced Course - Full Tutorial from a Google Engineer

阅读完本文，你将了解到一些常见的数据结构(或者温习，因为大部分朋友大学里面其实都是学过的)。在每个数据结构最后一小节都会列出代码实现，以及相关热门的算法题，该部分需要大家自己去探索与书写。只有自己能熟练的编写各种数据结构的代码才是真正的掌握了，大家别光看，动手写起来。阅读完本文，您将了解到：

抽象数据类型与数据结构的关系；
如何评估算法的复杂度；
了解以下数据结构，并且掌握其实现思路：数组，链表，栈，队列，优先级队列，索引式优先队列，二叉树，二叉搜索树BST，平衡二叉搜搜书BBST，AVL树，HashTable，并查集，树状数组，后缀数组。
文章里面不会贴这些数据结构的完整实现，但是会附带实现的链接，同时每种数据类型最后一节的相关实现以及练习题，建议大家多动手尝试编写这些练习题，以及尝试自己动手实现这些数据结构。

1、抽象数据类型

抽象数据类型(ADT abstract data type)：是数据结构的抽象，它仅提供数据结构必须遵循的接口。接口并未提供有关应如何实现某种内容或以哪种编程语言的任何特定详细信息。

下标列举了抽象数据类型和数据结构之间的构成关系：

ADT	DS
List	Dynamic Array Linked List
Queue	Linked List based Queue Array based Queue Stack based Queue
Map	Tree Map Hash Map HashTable
Vehicle	自行车电动车摩托车塞车

2、时间与空间复杂度

我们一般会关注程序的两个问题：

时间复杂度：这段程序需要花费多少时间才可以执行完成？
空间复杂度：执行这段代码需要消耗多大的内存？

有时候时间复杂度和空间复杂度二者不能兼得，我们只能从中取一个平衡点。

下面我们通过Big O表示法来描述算法的复杂度。

2.1、时间复杂度

2.1.1、Big-O

Big-O表示法给出了算法计算复杂性的上限。

T(n) = O(f(n))，该公式又称为算法的渐进时间复杂度，其中f(n)函数表示每行代码执行次数之和，O表示执行时间与之形成正比例关系。

常见的时间复杂度量级，从上到下时间复杂度越来越大，执行效率越来越低：

常数阶 Constant Time: O(1)
对数阶 Logarithmic Time: O(log(n))
线性阶 Linear Time: O(n)
线性对数阶 Linearithmic Time: O(nlog(n))
平方阶 Quadratic Time: O(n^2)
立方阶 Cubic Time: O(n^3)
n次方阶 Exponential Time: O(b^n), b > 1
指数阶 Factorial Time: O(n!)

下面是我从 Big O Cheat Sheet^[1]引用过来的一张表示各种度量级的时间复杂度图表：

2.1.2、如何得出Big-O

所谓Big-O表示法，就是要得出对程序影响最大的那个因素，用于衡量复杂度，举例说明：

O(n + c) => O(n)，常量可以忽略；

O(cn) => O(n), c > 0，常量可以忽略；

2log(n)3 + 3n2 + 4n3 + 5 => O(n3)，取对程序影响最大的因素。

练习：请看看下面代码的时间复杂度：

答案依次为：O(1), O(n), O(log(n)), O(nlog(n)), O(n^2)

第三个如何得出对数？假设循环x次之后退出循环，也就是说 2^x = n，那么 x = log2(n)，得出O(log(n))

2.2、空间复杂度

空间复杂度是对一个算法在运行过程中占用存储空间的大小的衡量。

O(1)：存储空间不随变量n的大小而变化；
O(n)：如：new int[n]；

2.3、常用数据结构复杂度

一些常用的数据结构的复杂度(注：以下表格图片来源于 Big O Cheat Sheet^[1:1])：

2.4、常用排序算法复杂度

(注：以下表格图片来源于 Big O Cheat Sheet^[1:2])

关于复杂度符号

O：表示渐近上限，即最差时间复杂度；

Θ：表示渐近紧边界，即平均时间复杂度；

Ω：表示渐近下界，即最好时间复杂度；

3、静态数组和动态数组

3.1、静态数组

静态数组是固定长度的容器，其中包含n个可从[0，n-1]范围索引的元素。

问：“可索引”是什么意思？

答：这意味着数组中的每个插槽/索引都可以用数字引用。

3.1.1、使用场景

1）存储和访问顺序数据
2）临时存储对象
3）由IO例程用作缓冲区
4）查找表和反向查找表
5）可用于从函数返回多个值
6）用于动态编程中以缓存子问题的答案

3.1.2、静态数组特点

只能由数组下标访问数组元素，没有其他的方式了；
第一个下标为0；
下标超过范围了会触发数组越界错误。

3.2、动态数组

动态数组的大小可以增加和缩小。

3.2.1、如何实现一个动态数组

使用一个静态数组：

创建具有初始容量的静态数组；
将元素添加到基础静态数组，同时跟踪元素的数量；
如果添加元素将超出容量，则创建一个具有两倍容量的新静态数组，然后将原始元素复制到其中。

3.3、时间复杂度

操作	静态数组	动态数组
访问	O(1)	O(1)
查找	O(n)	O(n)
插入	/	O(n)
追加	/	O(1)
删除	/	O(n)

3.4、编程实践

JDK中的实现：java.util.ArrayList
练习：

4、链表

4.1、使用场景

在许多列表，队列和堆栈实现中使用；
非常适合创建循环列表；
可以轻松地对诸如火车等现实世界的物体进行建模；
某些特定的Hashtable实现用于处理散列冲突；
用于图的邻接表的实现中。

4.2、术语

Head：链表中的第一个节点；

Tail：链表中的最后一个节点；

Pointer：指向下一个节点；

Node：一个对象，包含数据和Pointer。

4.3、实现思路

这里使用双向链表作为例子进行说明。

4.3.1、插入节点

往第三个节点插入：x

从链表头遍历，直到第三个节点，然后执行如下插入操作：

遍历到节点位置，把新节点指向前后继节点：

后继节点回溯连接到新节点，并移除旧的回溯关系：

前继节点遍历连接到新节点，并移除旧的遍历关系：

完成：

注意指针处理顺序，避免在添加过程中导致遍历出现异常。

4.3.2、删除节点

删除c节点：

从链表头遍历，直到找到c节点，然后把c节点的前继节点连接到c的后继接节点：

把c节点的后继节点连接到c的前继节点：

移除多余指向关系以及c节点：

完成：

同样的，注意指针处理顺序，避免在添加过程中导致遍历出现异常。

4.4、时间复杂度

操作	单向链表	双向链表
查找	O(n)	O(n)
Insert at head	O(1)	O(1)
中间追加	O(n)	O(n)
尾部追加	O(1)	O(1)
头部移除	O(1)	O(1)
尾部移除	O(n)	O(1)
中间移除	O(n)	O(n)

4.5、编程实践

JDK中的实现：java.util.LinkedList
练习：
- 反转链表
回文链表
- 两数相加
- 复制带随机指针的链表

5、栈

堆栈是一种单端线性数据结构，它通过执行两个主要操作（即推入push和弹出pop）来对现实世界的堆栈进行建模。

5.1、使用场景

文本编辑器中的撤消机制；
用于编译器语法检查中是否匹配括号和花括号；
建模一堆书或一叠盘子；
在后台使用，通过跟踪以前的函数调用来支持递归；
可用于在图上进行深度优先搜索（DFS）。

5.2、编程实战

5.2.1、语法校验

给定一个由以下括号组成的字符串：()[] {}，确定括号是否正确匹配。

例如：({}{}) 匹配，{()(]} 不匹配。

思路：

凡是遇到( { [ 都进行push入栈操作，遇到 ) } ] 则pop栈中的元素，看看是否与当前处理的元素匹配：

匹配完成之后，栈必须是空的。

5.3、复杂度

操作	时间复杂度
push	O(1)
pop	O(1)
peek	O(1)
search	O(n)
size	O(1)

5.4、编程实践

基于数组的实现：java.util.Stack
基于链表的实现：stack
练习：

6、队列

队列是一种线性数据结构，它通过执行两个主要操作（即入队enqueue和出队dequeue）来对现实世界中的队列进行建模。

6.1、术语

Dequeue：出队，类似命名：Polling
Enqueue：入队，类似命名：Adding，Offering
Queue Front：对头
Queue Back：队尾

队列底层可以使用数组或者链表实现

6.2、使用场景

任何排队等候的队伍都可以建模为Queue，例如在电影院里的队伍；
可用于有效地跟踪最近添加的x个元素；
用于Web服务器请求管理，保证服务器先接受的先处理；
图的广度优先搜索（BFS）。

6.2.1、请用队列实现图的广度优先遍历

提示：

遍历顺序：0 -> 2, 5 -> 6 -> 1 -> 9, 3, 2, 7 -> 3, 4, 8, 9

6.3、时间复杂度

操作	时间复杂度
入队	O(1)
Dequeue	O(1)
Peeking	O(1)
Contains	O(n)
Removal	O(n)
isEmpty	O(1)

6.4、编程实践

基于数组实现的Queue：ArrayQueue
基于链表实现的Queue：LinkedListQueue
练习：
- 设计循环队列
- 用队列实现栈

7、优先级队列PQ

优先级队列是一种抽象数据类型（ADT），其操作类似于普通队列，不同之处在于每个元素都具有特定的优先级。优先级队列中元素的优先级决定了从PQ中删除元素的顺序。

注意：优先级队列仅支持可比较的数据，这意味着插入优先级队列的数据必须能够以某种方式（从最小到最大或从最大到最小）进行排序。这样我们就可以为每个元素分配相对优先级。

为了实现优先级队列，我们必须使用到堆 Heap。

7.1、什么是堆

堆是基于树的非线性结构DS，它满足堆不变式：

堆中某个节点的值总是不大于或不小于其父节点的值；

二叉堆是一种特殊的堆，其满足：

是一颗完全二叉树^[2]。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

在同级兄弟或表亲之间没有隐含的顺序，对于有序遍历也没有隐含的顺序。

堆通常使用隐式堆数据结构实现，隐式堆数据结构是由数组（固定大小或动态数组）组成的隐式数据结构，其中每个元素代表一个树节点，其父/子关系由其索引隐式定义。将元素插入堆中或从堆中删除后，可能会违反堆属性，并且必须通过交换数组中的元素来平衡堆。

7.2、使用场景

在Dijkstra最短路径算法的某些实现中使用;
每当您需要动态获取“最佳”或“次佳”元素时；
用于霍夫曼编码（通常用于无损数据压缩）；
最佳优先搜索（BFS）算法（例如A*）使用PQ连续获取下一个最有希望的节点；
由最小生成树（MST）算法使用。

7.3、最小堆转最大堆

问题：大多数编程语言的标准库通常只提供一个最小堆，但有时我们需要一个最大PQ。

解决方法：

由于优先级队列中的元素是可比较的，因此它们实现了某种可比较的接口，我们可以简单地取反以实现最大堆；
也可以先把所有数字取反，然后排序插入PQ，然后在取出数字的时候再次取反即可；

7.4、实现思路

优先级队列通常使用堆来实现，因为这使它们具有最佳的时间复杂性。

优先级队列是抽象数据类型，因此，堆并不是实现PQ的唯一方法。例如，我们可以使用未排序的列表，但这不会给我们带来最佳的时间复杂度，以下数据结构都可以实现优先级队列：

二叉堆；
斐波那契堆；
二项式堆；
配对堆；

这里我们选取二叉堆来实现，二叉堆是一颗完全二叉树^[2:1]。

7.4.1、二叉堆排序映射到数组中

二叉堆索引与数组一一对应：

二叉堆排好序之后，即按照索引填充到数组中：

索引规则：

i节点左叶子节点：2i + 1
i节点右叶子节点：2i + 2

7.4.2、添加元素到二叉堆

insert(0)

如下图，首先追加到最后一个节点，然后一层一层的跟父节点比较，如果比父节点小，则与父节点交换位置。

7.4.3、从二叉堆移除元素

poll() 移除第一个元素

第一个元素与最后一个元素交换位置，然后删除掉最后一个元素；
第一个元素尝试sink 下沉操作：一直与子节点对比，如果大于任何一个子节点，则与该子节点对换位置；

remove(7) 移除特定的元素

依次遍历数组，找到值为7的元素，让该元素与最后一个元素对换，然后删除掉最后一个元素；
被删除索引对应节点尝试进行sink 下沉操作：与所有子节点比较，判断是否大于子节点，如果小于，那么就与对应的子节点交换位置，然后一层一层往下依次对比交换；
如果最终该元素并没有实际下沉，那么尝试进行swim 上浮操作：与父节点比较，判断是否小于父节点，如果是则与父节点对换位置，然后一层一层往上依次对比交换；

思考：请问如何构造一个小顶堆呢？

遍历数组，所有元素依次与子节点对比，如果大于子节点则交换。

7.5、尝试让删除操作时间复杂度变为O(log(n))

以上删除算法的效率低下是由于我们必须执行线性搜索**O(n)**以找出元素的索引位置。

**我们可以尝试使用哈希表进行查找以找出节点的索引位置。**如果同一个值在多个位置出现，那么我们可以维护一个特定节点值映射到的索引的Set或者Tree Set中。

数据结构如下：

这样我们在删除的时候就可以通过HashTable定位到具体的元素了。

7.6、时间复杂度

操作	时间复杂度
construction	O(n)
poll	O(log(n))
peek	O(1)
add	O(log(n))
remove	O(n)
remove with a hash table	O(log(n))
contains	O(n)
contains with a hash table	O(1)

7.7、编程实践

8、索引式优先队列 IPQ

索引优先级队列(Indexed Priority Queue IPQ)是传统的优先级队列变体，除了常规的PQ操作之外，它还提供了索引用于支持键值对的快速更新和删除。

我们知道前面的优先级队列的元素都是存放到一个list里面的，我们想知道知道某一个值在优先级队列中的位置，也是需要遍历一个个对比才知道的，要是有重复的值，那就区分不了了。既然找不到元素，那么对元素的更新和删除也就无从说起了。

为此，我们引入了如下两个索引：节点索引ki和位置索引im：

如：

请查找节点ki所在的优先级位置：可以很快可以从表1中找到 pm[ki]；
请查找优先级位置im存的是什么节点：可以很快从表2中找到节点的索引 ki[im]

与构造或更新删除PQ不同的是，IPQ需要额外维护这些索引的关系。

8.1、时间复杂度

操作	时间复杂度
delete(ki)	O(log(n))
valueOf(ki)	O(1)
contains(ki)	O(1)
peekMinKeyIndex()	O(1)
pollMinKeyIndex()	O(log(n))
peekMinValue()	O(1)
pollMinValue()	O(log(n))
insert(ki, value)	O(log(n))
update(ki, value)	O(log(n))
decreaseKey(ki, value)	O(log(n))
increaseKey(ki, value)	O(log(n))

8.2、编程实践

MinIndexedDHeap.java

9、二叉树与二叉搜索树BST

**二叉树(Binary Tree)**是每个节点最多具有两个子节点的树；

**二叉搜索树(Binary Search Tree)**是满足以下条件二叉树：左子树的元素较小，右子树的元素较大。

9.1、使用场景

某些map和set的ADT的实现；
红黑树；
AVL树；
伸展树(Splay Tree 分裂树)；
用于二叉堆的实现；
语法树；
Treap-概率DS(使用随机BST)

9.2、实现思路

9.2.1、插入元素

二叉搜索树（BST）元素必须具有可比性，以便我们可以在树中对其进行排序；
插入元素时，我们将其值与当前节点中存储的值进行比较：
- 小于节点值：向下递归左子树；
- 大于节点值：向下递归右子树；
- 等于节点值：处理重复值；
- 不存在节点：创建新节点。

极端场景：

这种情况就变为了线性结构，比较糟糕，这就是平衡二叉搜索树出现的原因。

9.2.2、移除元素

移除元素可以分为两步：

找到我们想要移除的元素；
如果存在后续节点，那么我们用后续节点替换掉要删除的节点；

移除会有以下三种情况：

9.2.2.1、移除的元素是一个叶子节点

找到对应待移除的节点，直接删除掉即可：

remove(16)：

9.2.2.2、移除的元素下面有左子树或者右子树

如果移除的元素下面带有左子树或者右子树，那么：找到对应待移除的节点，用子树的根节点作为移除元素的后继者，替换掉需要移除的元素即可：

9.2.2.3、移除的元素下面有左子树和右子树

如果移除的元素下面带有左子树和右子树，那么应该用左子树还是右子树中的节点作为删除元素的后继者呢？

答案是两者都可以！后继者可以是左侧子树中的最大值，也可以是右侧子树中的最小值。

下面我们执行remove(8)，统一选择使用右子树中的最小值。

具体步骤：

查找到需要删除的元素；
在其右子树中寻找到最小值的节点；
最小值的节点和待删除元素的值互换；
使用9.2.2.2的步骤删除掉原来最小值节点位置的节点；

9.2.3、查找元素

BST搜索元素会出现以下四种情况之一：

我们命中了一个空节点，这时我们知道该值在我们的BST中不存在；
比较器值等于0，说明找到了元素；
比较器值小于0，说明元素在左子树中；
比较器值大于0，说明元素在右子树中。

以下是find(6)操作：

9.3、树的遍历

可以分为深度优先遍历和广度优先遍历。而深度优先遍历又分为：前序遍历、中序遍历、后序遍历、层序遍历。

9.3.1、深度优先遍历

深度优先遍历都是通过递归来实现的，对应的数据结构为栈。

9.3.1.1、前序遍历

在递归方法最开始处理节点信息，代码逻辑：

void preOrder(node) {
  if (node == null) return;
  print(node.value);
  preOrder(node.left);
  preOrder(node.right);
}

如下二叉树将得出以下遍历结果：A B D H I E J C F K G

9.3.1.2、中序遍历

在递归调用完左子节点，准备右子节点之前处理节点信息，代码逻辑：

void inOrder(node) {
  if (node == null) return;
  inOrder(node.left);
  print(node.value);
  inOrder(node.right);
}

二叉搜索树使用中序遍历，会得到一个排好序的列表。

以下二叉搜索树将得出如下遍历结果：1 3 4 5 6 7 8 15 16 20 21

9.3.1.3、后序遍历

在递归完左右子树之后，再处理节点信息，代码逻辑：

void postOrder(node) {
  if (node == null) return;
  postOrder(node.left);
  postOrder(node.right);
  print(node.value);
}

以下二叉树得出如下遍历结果：1 4 3 6 7 5 16 15 21 20 8

9.3.2、广度优先遍历

在广度遍历中，我们希望一层一层的处理节点信息，常用的数据结构为队列。每处理一个节点，同时把左右子节点放入队列，然后从队列中取节点进行处理，处理的同时把左右子节点放入队列，反复如此，直至处理完毕。

9.4、BST时间复杂度

操作	平均	最差
insert	O(log(n))	O(n)
delete	O(log(n))	O(n)
search	O(log(n))	O(n)

9.5、编程实践

BST.java
练习：
- BiNode

10、平衡二叉搜索树BBST

平衡二叉搜索树(Balanced Binary Search Tree BBST)是一种自平衡的二叉搜索树。所以自平衡意味着会自行调整，以保持较低(对数)的高度，从而允许更快的操作，例如插入和删除。

10.1、树旋转

大多数BBST算法核心组成部分是：树不变式和树旋转的巧妙用法。

树不变式：是在每次操作后必须满足的属性/规则。为了确保始终满足不变式，通常会应用一系列树旋转。

在树旋转的过程中需要确保保持BST的不变式：左子树比较小，右子树比较大。

10.1.1、更新单向指针的BBST

为此，我们可以使用以下操作实现右旋转，注意观察宣传前后，BST的不变式：

public void rightRotate(Node a) {
  Node b = a.left;
  a.left = b.right;
  b.right = a;
  return b;
}

如下图，我们准备执行rightRotate(a)：

为什么可以这样变换呢？

还是那个原则：BST不变式。

所有BBST都是BST，因此对于每个节点n，都有：n.left <n && n < n.right。(这里的前提是没有重复元素)

我们在变换操作的时候只要确保这个条件成立即可，即保持BST不变性成立的前提下，我们可以对树中的值和节点进行随机变换/旋转。

注意，如上图，如果a节点还有父节点p，那么就把p节点原来指向a节点变更为指向b节点。

10.1.2、更新双向指针的BBST

在某些需要经常方位父节点或者同级节点的BBST中，我们就不是像上面那样最多更新3个指针，而是必须更新6个指针了，操作会复制些许。

以下是代码实现：

public void rightRotate(Node a) {
  Node p = a.parent
  Node b = a.left;
  a.left = b.right;
  if (b.right != null) {
    b.right.parent = a;
  }
  b.right = a;
  a.parent = b;
  b.parent = p;
  // 更新父指针
  if (p != null) {
    if (p.left == a) {
      p.left = b;
    } else {
      p.right = b;
    }
  }
  return b;
}