「数据结构」的主要内容有哪些，难度如何，怎样系统地学习？ 第1页

这个题目不错，数据结构是计算机科学中非常重要的基础！

咱们就翻译一篇medium上超级超级超级火的文章，来学习八种数据结构！

原文链接：https://medium.com/free-code-camp/the-top-data-structures-you-should-know-for-your-next-coding-interview-36af0831f5e3
原文作者：Fahim ul Haq
原文平台：medium

尼克劳斯·维尔特，瑞士计算机科学家，在1976年写了一本名为《算法 + 数据结构 = 程序》的书。

40多年转瞬即逝，但这个公式依然成立。这也是今天我们程序员面试的时候，需要展示自己对数据结构以及他们应用场景的掌握的原因。

几乎所有的问题都需要面试者证明他们具有扎实的数据结构基本功。无论你是刚毕业也好（从大学还是编程培训营），还是有N多年的经验。

有时候这些面试题则是专门提到某种数据结构。比如，题目描述是这样开头的“给定一颗二叉树。。。”。其他的时候则是那种隐式的，比如说，“我们找到每个作者相关的书籍数目”。

学习数据结构是非常重要的，哪怕你只是想在当前的工作岗位上变得更赞一点。所以，就让我们从基础开始吧。

啥是数据结构？
简单来说，数据结构就是一种容器，按照某种既定的方式存储数据。这种“方式”能让一个数据结构在某些操作下很高效，相反，在另外的操作下就不太理想了。你的目标是为了理解这些数据结构，从而可以能从不同的数据结构中选择适合当前所面对的问题的那一种。

为啥需要数据结构？
因为数据结构是用来有规则地存储数据的，加上数据结构在计算机科学中神一般的存在，他们的价值就不言而喻了。

不过你要解决的问题是啥，你反正都得需要数据结构，方式可能不同而已。无论是面对员工工资，还是股票价格，购物清单，还是简单的电话本，这样的场景。

根据不同的应用场景，数据需要按照不同的方式存储。我们有好多可以将数据按照不同方式保存下来的数据结构。

常用的数据结构
我们先来列一下最最常用的八种数据结构，然后接下来我们会慢慢将他们讲明白。

数组
栈
队列
链表
树
图
字母树（其实他们就是树而已，但还是值得单独拿出来讲的）
哈希表

数组

数组是最简单也最常用的数据结构。其他的数据结构诸如栈和队列，都是从数组衍生出来的。

下面是一个拥有四个元素的简单数组，包含了元素1，2，3，4.

每个元素都依附于一个正整数，称作索引，它就对应于数组中该元素所在的位置。大多数的编程语言中，数组的起始索引都为0 （0-based，译者注）.

数组一般有以下两种：

一维数组（上图所示）
多维数组（数组里面包含数组）
数组的基本操作

插入 — 在给定位置插入一个元素
取值 — 返回给定位置的数值
删除 — 在给定位置删除元素
元素总数 — 数组包含元素的个数
数组类常问问题

数组中第二小的数
数组中出现的第一个无重复的数
合并两个已排序数组
重新排放数组的正数和负数

栈

我们平时熟悉的软件操作中的撤销（回退）操作，基本会出现在所有应用中。你好奇过它是咋工作的吗？原理是这样的：你把之前的状态（有限的数量）都存到内存中，存的顺序是最新的操作存在最近一个。这个光靠数组是不能实现的。这是栈擅长的地方。

现实中也有栈的例子。比如你把一大堆书垂直叠（一本压着另外一本）起来放。为了拿到他们里面靠中部位置的书，你得把上面的书都拿走才行。这就是著名的LIFO（后进先出）的工作原理。

下图是一个包含有三个元素的栈，数值为1，2，3. 元素3在栈顶，它会被最先删除。

栈的基本操作

进栈 — 在栈顶插入元素
出栈 — 把栈顶元素弹出（删除）
判空 — 返回栈是否为空
栈顶元素 — 只返回栈顶元素而不删除
译者注：对于栈所有的操作，都只出现在栈顶这个地方

栈常见的面试问题

借助栈来计算后缀表达式的值
将栈里的元素进行排序
判断括号表达式是否合法

队列

和栈类似，队列是另外一种线性数据结构。这种数据结构将元素按照顺序的方式存储。和栈最本质的区别就是：和后进先出相反，队列实现了先进先出的特性（FIFO， First in First Out）。

队列在生活中有非常贴切的例子：一堆人排在售票台前面。如果新来了一个人，这个人得排在队尾，而不是队伍前面。另一方面，排在第一的人则能第一个买到票，然后离开队伍。

下面是一个包含了四个元素的队列（1， 2， 3， 4）。1站在队头，会被第一个删除。

队列的常用操作

进队 — 在队尾加入一个元素
出队 — 从队头删除元素
判空 — 判断队列是否为空
队头元素 — 返回但不删除队头元素

常见的队列题

用队列实现栈
将队列里面的前k个元素翻转
借助队列来产生从1到n的二进制数

链表

链表是另外一种重要的线性数据结构。链表初看起来和数组很类似，但他们在内存分配，内部结构，以及像插入和删除这样的基本操作上，都是不一样的。

链表就是一串 串起来 的节点，他们的每一个节点都包含了数据和指向下一个节点的信息。链表有头结点，指向链表中的第一个元素。

链表结构经常用来实现文件系统，哈希表，以及邻接表。

下图是一个链表的内部结构图示。

我们常见的链表有以下两种：

Singly Linked List (Unidirectional)
Doubly Linked List (Bi-directional)
单链表 （单一方向）
双链表 （双向）

链表基本操作：

末端插入 — 在链表的末尾插入给定元素
头部插入 — 在链表的头部插入给定元素
删除 — 在链表中删除给定元素
头部删除 — 删除头部第一个元素
搜索 — 判断给定元素是否存在于链表中
判空 — 判断链表是否为空

常见的链表问题

翻转链表
检查链表中是否有环
返回距离尾部距离为N的节点
删除链表中的重复元素

图

图包含一系列的节点，这些节点通过网络相互连接起来。这些节点也被称为Vertcies。对于每个对子（x, y)，我们则称为边，表示节点x和节点y是相连的。边也可能包含权重或是花费信息，表明了从x到也所需要的消耗。

图的类型：

无向图
有向图

在计算机语言中，图通常用下面两种方法表示：

邻接矩阵
邻接表

常用的图遍历算法：

宽度优先搜索
深度优先搜索

常见的图问题

实现宽搜和深搜
判断一个图是不是一棵树
数图中的边数
找两个节点之间的最短路径

树

树是非线性数据结构，它也是由节点和边组成的。因此树和图类似，但他们最大的不同是树上没有环存在。

树被广泛应用在AI和其他复杂算法中，因为它能提供高效的存储，使得问题能得以解决。

下面是一颗简单树，图中也包含了常见的树的术语。

我们可以有以下的各种树的形状：

• N叉树
• 平衡树
• 二叉树
• 二叉搜索树
• AVL树
• 红黑树
• 2-3树

上面这些树中，以二叉树和二叉搜索树最为常用。

常见的树的问题

求二叉树的高度
求二叉搜索树中的第k大的数值
找离根节点距离为k的所有节点
找给定节点的所有祖先节点

字母树

字母树，也叫做前缀树，是一种树形的数据结构，它是一种解决字符串相关的问题的高效数据结构。能快速查询回馈信息，经常用在字典中查询单词的场景下，它能为搜索引擎提供自动补全，甚至能帮到IP查询。

下图演示了如何将三个单词（top, thus, their）插入到字母树中，并保存下来：

在字母树中，单词都是从下至下一个字母一个字母保存起来的。绿色的节点（p, s, r）表示的是该节点是一个单词的最后一个字母，p对应top，s对应thus，而r则对应于their。

常见的字母树问题：

数字母树中的单词总数
打印字母树中所有的单词
用字母树排序数组
借助字母树来从字典中取单词
建一个满足T9的字典（译者注：T9 stands forText on 9 keys）

哈希表

哈希是一个分辨不同的实体，从而将每个实体存储在某个预先计算好的索引上，这个预先算出来的值被称作“键”。因此，实体都是由键值对的形式存放的，把一大堆这样的东西称为字典。每个实体都能通过键来找到。基于哈希这种思想的数据结构有不少，但最常用的是哈希表。

哈希表一般通过数组来实现。

哈希表的效率取决于以下三个因数：

1. 哈希函数
2. 哈希表的容量
3. 冲突避免方式

下面这图演示了我们是怎么从哈希值匹配到一个数组中的。该数组的索引是通过函数函数求出来的。

常见问题：
找数组中的对称对子
追踪旅程的完整路径
检查一个数组是否为另一数组的子集
检查多个数组之间是不是没有共同元素

上面就是八种你在算法面试之前必知必会的数据结构。

具体的学习，可以参考原文作者开发educative上的数据结构课程：

专门针对数据结构的课程则有：

C++:

JavaScript：

Java：

Python：

我上过其中的Java版本，课程是把数据结构里面的基础数据结构都用java实现了一遍，对于用java的同学特别有帮助，java的基础在刷题的过程中，还是要必须掌握的。

（如果你需要上面这些算法课程，那么你可以使用 awesome-developer 的折扣码获得网站所有课程的额外15%off！上面的折扣码针对单独购买所有课程有效。

如果想买订阅（Subscriptions）的小伙伴,则可以用0820-ZH93025（必须一模一样输入）的coupon code来获取额外八折的优惠按年和按月均适用，折扣码十月四号过期，有需要的小伙伴抓紧）。

过了十月四号就只能用 ZHIHUEDU-10 的九折优惠了，大家有需要的抓紧，还有不到两周！