图解数据结构

• 作者：天行

参加了 lucifer 的 91 天学算法活动，不知不觉中已经一月有余。从盲目地做到有目的、有套路地去做。

在 lucifer 的 91 课程中，从基础到进阶到专题，在这个月中，经历了基础篇的洗礼，不管在做题思路，还是做题速度都有了很大的提升，这个课程，没什么好说的，点赞点赞再点赞。也意识到学习好数据结构有多重要，不仅是思维方式的改变，还是在工程上的应用。

对一个问题使用画图、举例、分解这 3 种方法将其化繁为简，形成清晰思路再动手写代码，一张好的图能够更好地帮助去理解一个算法。因此本次分享如何使用画图同时结合经典的题目的方法去阐述数据结构。

​<!-- more -->

数据结构与算法有用么？

这里我摘录了一个知乎的高赞回答给大家做参考：

个人认为数据结构是编程最重要的基本功没有之一！学了顺序表和链表，你就知道，在查询操作更多的程序中，你应该用顺序表；而修改操作更多的程序中，你要使用链表；而单向链表不方便怎么办，每次都从头到尾好麻烦啊，怎么办？你这时就会想到双向链表 or 循环链表。
学了栈之后，你就知道，很多涉及后入先出的问题，例如函数递归就是个栈模型、Android 的屏幕跳转就用到栈，很多类似的东西，你就会第一时间想到：我会用这东西来去写算法实现这个功能。
学了队列之后，你就知道，对于先入先出要排队的问题，你就要用到队列，例如多个网络下载任务，我该怎么去调度它们去获得网络资源呢？再例如操作系统的进程（or 线程）调度，我该怎么去分配资源（像 CPU）给多个任务呢？肯定不能全部一起拥有的，资源只有一个，那就要排队！那么怎么排队呢？用普通的队列？但是对于那些优先级高的线程怎么办？那也太共产主义了吧，这时，你就会想到了优先队列，优先队列怎么实现？用堆，然后你就有疑问了，堆是啥玩意？自己查吧，敲累了。
总之好好学数据结构就对了。我觉得数据结构就相当于：我塞牙了，那么就要用到牙签这“数据结构”，当然你用指甲也行，只不过“性能”没那么好；我要拧螺母，肯定用扳手这个“数据结构”，当然你用钳子也行，只不过也没那么好用。学习数据结构，就是为了了解以后在 IT 行业里搬砖需要用到什么工具，这些工具有什么利弊，应用于什么场景。以后用的过程中，你会发现这些基础的“工具”也存在着一些缺陷，你不满足于此工具，此时，你就开始自己在这些数据结构的基础上加以改造，这就叫做自定义数据结构。而且，你以后还会造出很多其他应用于实际场景的数据结构。。你用这些数据结构去造轮子，不知不觉，你成了又一个轮子哥。

既然这么有用，那我们怎么学习呢？我的建议是先把常见的数据结构学个大概，然后开始安装专题的形式突破算法。这篇文章就是给大家快速过一下一部分常见的数据结构。

从逻辑上分，数据结构分为线性和非线性两大类。

• 线性数据结构包括数组、链表、栈、队列。
• 非线性结构包括树、哈希表、堆、图。

而我们常用的数据结构主要是数组、链表、栈、树，这同时也是本文要讲的内容。

数据结构一览

数组

数组的定义为存放在连续内存空间上的相同类型数据的集合。因为内存空间连续，所以能在 O(1)的时间进行存取。

剑指 offer03.数组中的重复的数字

题目描述：

在一个长度为 n 的数组 nums 里的所有数字都在 0 ～ n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

分析：

重复意味至少出现两次，那么找重复就变成了统计数字出现的频率了。那如何统计数字频率呢？（不使用哈希表），我们可以开辟一个长度为 n 的数组 count_nums，并且初始化为 0，遍历数组 nums，使用 nums[i]为 count_nums 赋值.

图解：

(注意：数组下标从 0 开始)

剑指 offer21. 调整数组顺序使奇数位于偶数前面

题目描述：

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

分析：

根据题目要求，需要我们调整数组中奇偶数的顺序，那这样的话，我们可以从数组的两端同时开始遍历，右边遇到奇数的时候停下，左边遇到偶数的时候停下，然后进行交换。

1122.数组的相对排序

题目描述：

给你两个数组，arr1 和  arr2，
arr2  中的元素各不相同
arr2 中的每个元素都出现在  arr1  中
对 arr1  中的元素进行排序，使 arr1 中项的相对顺序和  arr2  中的相对顺序相同。未在  arr2  中出现过的元素需要按照升序放在  arr1  的末尾。

示例

输入：arr1 = [2,3,1,3,2,4,6,7,9,2], arr2 = [2,1,4,3,9,6]

输出：[2,2,2,1,4,3,3,9,6,7]

分析：

观察输出，发现数字，因为 arr1 总是根据 arr2 中元素的相对大小来排序，所以只相当于在 arr2 中进行填充，每个地方该填充多少呢？这个时候就需要去统计 arr1 中每个数字出现的频率。

小结

在数组中，因为数组是一个有序的结构，这里的有序是指在位置上的有序，所以大多数只需要考虑顺序或者相对顺序即可。

链表

链表是一种线性数据结构，其中的每个元素实际上是一个单独的对象，每一个节点里存到下一个节点的指针（Pointer）。
就像我们玩的寻宝游戏一样，当我们找到一个宝箱的时候，里面还存在寻找下一个宝箱的藏宝图，依次类推，每一个宝箱都是如此，一直到找到最终宝藏。

通过单链表，可以衍生出循环链表，双向链表等。

我们来看下链表中比较经典的几个题目。

面试题 02.02. 返回倒数第 k 个节点

题目描述：

实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

示例：

输入： 1->2->3->4->5 和 k = 2
输出： 4

分析：

想要找到倒数第 k 个节点，如果此时在数组中，那我们只需要用最后一个数组的索引减去 k 就能找到这个值，但是链表是不能直接通过索引得到的。如果此时，我们知道最后一个节点的位置，然后往前找 k 个不就找到我们需要的节点了吗？等价于我们要找的节点和最后一个节点相隔 k 个位置。所以当有一个指针 front 出发 k 步后，我们再出发，等 front 到达终点时，我们刚好到达倒数第 k 个节点。

我们把这种解法叫做双指针，或者快慢指针，或者前后指针，这种方法可以用于寻找链表中间节点，判断是链表中是否存在环（循环链表）并寻找环入口。

61. 旋转链表

题目描述：

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例：

输入: 1->2->3->4->5->NULL, k = 2

输出: 4->5->1->2->3->NULL

分析：

每个数字向后移动 k 位，那么最后 k 位就需要移动到前面，和找倒数第 k 位数字很相似，k 位后面的都移到开头。唯一需要注意的地方就是，k 的值可能大于链表长度的 2 倍及以上，所以需要算出链表的长度，以保证尽快找到倒数 k 的位置。

解法 1

找到位置后，直接断开

解法 2

制作循环链表，然后再找倒数第 k 个数，然后断开循环链表

24. 两两交换链表中的节点

题目描述：

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例：

输入：head = [1,2,3,4]

输出：[2,1,4,3]

分析：

原理很简单，两个指针，分别指向相邻的两个节点，然后再添加一个临时指针做换交换的中介添加 dummy 节点，不用考虑头节点的情况，更加方便。直接上图：

除了同时操作一个链表之外，有的题目也会给出两个或者更多的链表，如两数相加，如 leetcode 中 2.两数相加、21.合并两个有序链表、160.相交链表

21.相交节点

题目描述：

编写一个程序，找到两个单链表相交的起始节点。

如下面的两个链表

分析：

我们知道，对于任意两个数 ab，一定有 a+b-c=b+a-c，

基于 a+b-c=b+a-c，我们可以设置两个指针，分别指向 A 和 B，以相同的步长同时移动，并在第一次到达尾节点的时候，指向另一个链表，如果存在相交节点，也就是说 c > 0，那么两个指针一定会相遇，相遇处也就是相交节点。而当不存在时，即 c=0，那么两个指针最终都会指向空节点。

小结

链表中的操作无非就是两种，插入，删除。解题方法无非就是添加 dummy 节点(解决头节点的判断问题)、快慢指针(快慢不一定是单次步长一样，应该理解为平均步长，即使用了相同的时间，走的路程的长度来定义快慢)。

栈

栈是一种先进后出(FILO, First In Last Out)的数据结构
可以把栈理解为

<center>

</center>

没错，就是上图的罐装薯片，想要吃到最底下的那片，必须依次吃完上面的。而在装薯片的时候，最底下的反而是最先装进去的。

在 leetcode 里面关于栈比较经典的题目有：20.有效的括号；150.逆波兰表达式求值

20.有效的括号

题目描述：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

示例：
"{[()][]}()"

| 0   | 1   | 2   | 3   | 4   | 5   | 6   | 7   | 8   | 9   |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| {   | [   | (   | )   | ]   | [   | ]   | }   | (   | )   |

分析：

• 一个有效的括号为，右边必须和左边对应，且存在至少一对有效括号的索引为[i, i+1]。 那么，我们只要是括号左边部分，就入栈，右边部分，就和栈顶元素比较。

图解：

150.逆波兰表达式求值

题目描述：

根据 逆波兰表示法，求表达式的值。
有效的运算符包括 +, -, \*, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

示例：
["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+"]

分析：

• 根据运算法则，我们可以知道，一个运算有 num1，operation，num2 三部分组成。在一个逆波兰表达式中，运算符前面两个 num 就是这个运算的组成。
• 我们要做事情就是，找到一个运算符的时候，同时找到他前面的两个数，而栈的现金先去特性满足这个需求，使用栈来解决。

227.基本计算器 II

题目描述：

实现一个基本的计算器来计算一个简单的字符串表达式的值。字符串表达式仅包含非负整数，+， - ，\*，/ 四种运算符和空格 。 整数除法仅保留整数部分。

示例：3+5\*2/2-3

分析：

• 与逆波兰表达式不同的地方是，这里运算符两边是操作数。但是，这又有什么问题呢？万变不离核心，我们只需要在找到运算符的同时，得到运算符两边的操作数。问题来了，还需要考虑运算符的优先级，想到的一个方法就是，只进行乘除法运算，最后进行加法运算，不进行减法运算（减去一个数 ⟺ 加上这个数的负数）

• 如果能够把这个字符串表达式相似地转换位逆波兰表达式，那就能直接套用逆波兰表达式的代码了，回顾一下，逆波兰表达式是，每次有操作符的时候，就从栈顶出来两个元素。可以通过使用两个栈来实现，一个栈用来存储操作数，一个栈用来存储操作符。如果比栈顶的操作符符优先级低或者相同，那么就从操作符栈取出栈顶运算符号

496.下一个更大元素 I

题目描述：

给定两个 没有重复元素的数组  nums1 和  nums2 ，其中 nums1  是  nums2  的子集。找到  nums1  中每个元素在  nums2  中的下一个比其大的值。nums1  中数字  x  的下一个更大元素是指  x  在  nums2  中对应位置的右边的第一个比  x  大的元素。如果不存在，对应位置输出 -1。

示例：

输入: nums1 = [4,1,2], nums2 = [1,3,4,2].

输出: [-1,3,-1]

分析：

题目要求我们找出 nums1 中每个元素在 nums2 中的下一个比这个元素大的值，又提到 nums1 是 nums2 的一个子集，我们不妨找出 nums2 中每个元素的下一个比他大的值，然后映射到 nums1 中。

那如何找出 nums2 中每个元素的下一个比他大的值呢？对于当前元素，若下一个元素比他大，则找到了，否则的话，就把这个元素添加到栈中，一直到找到一个元素比栈顶元素大，这时候把栈里面所有小于这个元素的元素都出栈，听起来很绕，无妨，看图---->

最后栈中依然有数据存在，这是为什么呢？因为这些元素后面找不到比他更大的值了。观察示例数据，4 后面没有比他更大的值了，5 和 1 也是。我们还能观察到栈中元素是从大到小的，可以称这个栈为==单调递减栈==(如 1019.寻找链表中的下一个更大节点，503.下一个更大元素 II、402.移掉 k 位数字，39.每日温度，在 1673.找出最具有竞争力的子序列中，其实只需要构建一个单调递增栈，然后截取前 k 个。)。

回到题目，需要找到 nums1 中元素在 nums2 中的下一个比其大的值，只需要在刚才保存的信息中进行查找，找不到的则不存在，可以使用哈比表保存每个数对应的下一个较大值。

小结

栈由于其随时可以出栈和进栈，产生非常多的组合，带来了非常多的变化，所以读懂题目非常重要，然后选择方法，正所谓题目是有限的，方法是有限的。所以紧跟 lucifer 大佬学习套路，是一条值得坚持的道路，毕竟自古深情留不住，唯有套路得人心，这里推荐 lucifer 大佬的《单调栈模板带你秒杀八道题》，带你乱杀。

树

树虽相比于链表来说，至少有两个节点（n 个节点就叫 n 叉树），但是树是一个抽象的概念，可以理解为一个不停做选择的过程，给定一个起始条件，会产生多种结果，而这些结果又成为新的条件，以此类推，直到不再有新的条件。在树种，起始条件就是根节点，不再产生新的条件的就是叶子节点。在树种，使用较多的是二叉树。一颗二叉树不管有多大，我们都可以把他拆分为五种形式,

不管是在树上进行什么操作，都需要进行遍历，遍历的方式有两种：广度优先遍历（BFS）和深度优先遍历（DFS）。
简单来说，广度就是先找到有多少种可能，然后找出这些可能有多少种可能；而深度就是每次只根据一个条件来找，直到最终没有条件。
话不多说，上图。

如果是试错的话，广度是一次把所有的结果都试一试，深度则是一条路走到黑。

这里直接借用 lucifer 大佬的广度、深度优先遍历模板（套路）

function dfs(root) {
 if (满足特定条件）{
  // 返回结果 or 退出搜索空间
 }
 for (const child of root.children) {
        dfs(child)
 }
}

深度优先遍历根据逻辑处理（==敲黑板，很重要==）的先后分为前序遍历、中序遍历、后序遍历

// 前序遍历
function dfs(root) {
 if (满足特定条件）{
  // 返回结果 or 退出搜索空间
    }
    // 主要逻辑
    dfs(root.left)
    dfs(root.right)
//中序遍历
function dfs(root) {
 if (满足特定条件）{
  // 返回结果 or 退出搜索空间
    }
    dfs(root.left)
    // 主要逻辑
    dfs(root.right)
// 后序遍历
function dfs(root) {
 if (满足特定条件）{
  // 返回结果 or 退出搜索空间
    }
    dfs(root.left)
    dfs(root.right)
    // 主要逻辑
}
}

接下来就要实操了

199. 二叉树的右视图

题目描述：

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例：

输入: [1,2,3,null,5,null,4]

输出: [1, 3, 4]

解释:

分析：

此题即可以使用广度优先，也可以深度优先。
使用广度优先，只需要将每一层的节点用一个数组保存下来，然后输出最后一个
使用深度优先，这里我使用的是根右左的方式，这样能保证在每进入到一个新的层时，第一个访问到的就是最右边的元素。

上图：

112. 路径总和

题目描述：

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。

示例：

分析：

求一条路径（根节点到叶子节点），这不就一条路走到底吗，没什么好犹豫的，选择深度优先遍历。因为需要获得路径上的和，我们需要把每个节点的值（状态）传递给下一个节点。

在 113. 路径总和 II 中，和本题类似，只需要把节点加入到数组中传递给下一个节点；在 129. 求根到叶子节点数字之和，需要把当前值*10 传递给下一个节点。

662. 二叉树最大宽度

题目描述：

给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。
每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的 null 节点也计入长度）之间的长度。

示例：

分析：

最大宽度，不就是找出哪一层最长吗？广度优先搜索会更加方便，需要注意的是，非两端节点的 null 节点也要算到长度中，所以现在每一层存储的不仅仅是有值节点。

上图

513. 找树左下角的值

题目描述：

给定一个二叉树，在树的最后一行找到最左边的值。

示例：

<center>

</center>
分析：
两个关键信息，一个最后一行，一个最左边。好像广度，深度都可以找到，在这里以深度进行说明，最后一行就是depth最大的，所以在深度遍历的时候，每次给一层传递depth信息。

与此题类似的还有 111. 二叉树的最小深度，104.二叉树的最大深度

感觉，就这？好像也没什么难的啊，学完 lucifer 的课程，我就是这么膨胀。

小结

无非就是，深度遍历时，是否传递信息给下一层，给下一层传递什么信息；广度遍历时，是否保存每一层，是否保存空节点。

总结

本次给大家介绍了四种比较常见的数据结构，分别是数组，链表，栈和树。这四种只有树是逻辑上的非线性数据结构，因为一个节点可能有多个孩子，而其他数据结构只有一个前驱和一个后继。

由于先进后出的特性，我们可以用数组轻松地在 $O(1)$ 时间复杂度模拟栈的操作。但是队列就没那么好命了，我们必须使用链表来优化时间复杂度。

链表的考题相对比较单一，只要记住那几个点就好了。

树的题目比较丰富，和它的非线性数据结构有很大关系。由于其是非线性的，因此有了各种遍历方式，常见的是广度优先和深度优先，很多题目都是灵活运用这两种遍历方式问题就迎刃而解。

关注公众号力扣加加，学习算法不迷路。

参考：

• 基础的数据结构（总览）
• 几乎刷完了力扣所有的链表题，我发现了这些东西
• 几乎刷完了力扣所有的树题，我发现了这些东西
• 回炉重铸， 91 天见证不一样的自己（第二期）