数据结构（一）：面试前你应该知道的数据结构

快来打我* 2022-04-23 14:48 275阅读 0赞

> 原文地址：[https://medium.freecodecamp.org/the-top-data-structures-you-should-know-for-your-next-coding-interview-36af0831f5e3][https_medium.freecodecamp.org_the-top-data-structures-you-should-know-for-your-next-coding-interview-36af0831f5e3]  
> 本文在每种数据结构下给出了常见面试题及对应的题解

### 文章目录 ###

*   *  1、开篇简述
     *  2、什么是数据结构
     *  3、为什么我们需要数据结构
     *  4、常用的数据结构
     *   *  4.1、数组（Arrays）
         *   *  4.1.1、数组的基本操作
             *  4.1.2、数组常见面试题
         *  4.2、栈（Stacks）
         *   *  4.2.1、栈的基本操作
             *  4.2.2、栈常见面试题
         *  4.3、队列（Queues）
         *   *  4.3.1、队列的基本操作
             *  4.3.2、队列常见面试题
         *  4.4、链表（Linked List）
         *   *  4.4.1、链表的基本操作
             *  4.4.2、链表常见面试题
         *  4.5、图（Graphs）
         *   *  4.5.1、图的分类与遍历算法
             *  4.5.2、图常见面试题
         *  4.6、树（Trees）
         *   *  4.6.1、树的分类
             *  4.6.2、树常见面试题
         *  4.7、前缀树（Trie）
         *   *  4.7.1、Trie 常见面试题：
         *  4.8、散列表（Hash Table）
         *   *  4.8.1、常见的哈希面试题

## 1、开篇简述 ##

瑞士计算机科学家Niklaus Wirth在1976年写了一本书，名为《算法+数据结构=编程》。  
40多年后，这个等式仍被奉为真理。这就是为什么在面试过程中，需要考察软件工程师对数据结构的理解。

几乎所有的问题都需要面试者对数据结构有深刻的理解。无论你是刚毕业职场新人，还是拥有数十年经验的职场老人。

有些面试题会明确提及某种数据结构，例如，“给定一个二叉树。”而另一些则隐含在面试题中，例如，“我们希望记录每个作者相关的书籍数量。”

即便是对于一些非常基础的工作来说，学习数据结构也是必须的。那么，就让我们先从一些基本概念开始入手。

## 2、什么是数据结构 ##

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。【百度百科】

## 3、为什么我们需要数据结构 ##

由于数据结构用于以有组织的形式存储数据，并且由于数据是计算机科学中最重要的实体，因此数据结构的真正价值是显而易见的。

无论你解决什么问题，你都必须以某种方式处理数据 - 无论是员工的工资，股票价格，购物清单，还是简单的电话簿。

根据不同的场景，数据需要以特定格式存储。我们有一些数据结构可以满足我们以不同格式存储数据的需求。

## 4、常用的数据结构 ##

我们首先列出最常用的数据结构，然后我们将逐一介绍它们：

1.  数组（Arrays）
2.  栈（Stacks）
3.  队列（Queues）
4.  链表（Linked List）
5.  树（Trees）
6.  图（Graphs）
7.  字典树（Trie）
8.  散列表（Hash Table）

### 4.1、数组（Arrays） ###

数组是最简单和最广泛使用的数据结构。其他数据结构（如堆栈和队列）是从数组派生的。

下图展示了1个数组，它有4个元素：  
![在这里插入图片描述][20190317154411817.png]  
为每个数据元素分配一个称为索引的正数值，该值对应于该项目在数组中的位置。大多数语言将数组的起始索引定义为0。

以下是两种类型的数组：

*  一维数组（如上图所示）
 *  多维数组（数组中的数组）

#### 4.1.1、数组的基本操作 ####

Insert - 在某个索引处插入元素  
Get - 读取某个索引处的元素  
Delete - 删除某个索引处的元素  
Size - 获取数组的长度

#### 4.1.2、数组常见面试题 ####

*  [查找数组的第二个最小元素][Link 1]
 *  [查找数组中的第一个非重复整数][Link 2]
 *  [合并两个排好序的数组][Link 3]
 *  [原地删除有序数组中的重复数][Link 4]

### 4.2、栈（Stacks） ###

我们都熟悉常用的撤销操作（Ctrl+Z），它几乎存在于每个应用程序中。有没有想过它是如何工作的？答案是这样的：把之前的应用状态(限制个数)保存到内存中，最近的状态放到第一个。这时，我们需要栈(stack)来实现这个功能。

栈中的元素采用 LIFO (Last In First Out)，即后进先出。

Stack 的现实例子就好像是一堆垂直排列的书籍。为了获得位于中间位置的书，您需要先拿走放在其上的所有书籍。这就是LIFO（后进先出）方法的工作原理。

下图的栈有3个元素，3在最上面，因此它会被第一个移除：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA2NDcwMzU_size_16_color_FFFFFF_t_70]

#### 4.2.1、栈的基本操作 ####

*  Push — 在顶部插入元素
 *  Pop — 返回栈最上方的元素，并将其删除
 *  isEmpty — 查询栈是否为空
 *  Top — 返回栈最上方的元素，并不删除

#### 4.2.2、栈常见面试题 ####

*  [使用栈计算后缀表达式][Link 5]
 *  [使用栈为栈中的元素排序][Link 6]
 *  [检查表达式中的括号是否匹配正确][Link 7]
 *  [使用栈实现队列][Link 8]

### 4.3、队列（Queues） ###

与Stack类似，Queue是另一种线性数据结构，以顺序方式存储元素。Stack和Queue之间唯一的显着区别是，Queue不使用 LIFO 方法，而是实现 FIFO（先进先出） 方法，即 First in First Out。

Queue的一个现实生活例子：一排人在售票亭等候。如果一个新人来了，他们将从最后加入线，而不是从头开始，站在前面的人将是第一个获得票。

下图展示了一个队列，1是顶部的元素，它会被第一个移除：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA2NDcwMzU_size_16_color_FFFFFF_t_70 1]

#### 4.3.1、队列的基本操作 ####

*  Enqueue — 在队列末尾插入元素
 *  Dequeue — 从队列头部删除一个元素
 *  isEmpty — 查询队列是否为空
 *  Top — 返回队列的第一个元素

#### 4.3.2、队列常见面试题 ####

*  [使用队列实现栈][Link 9]
 *  [反转队列的前K个元素][K]
 *  使用队列生成从1到n的二进制数

### 4.4、链表（Linked List） ###

链表是另一个重要的线性数据结构，它可能看起来类似于数组，但在内存分配，内部结构以及如何执行插入和删除的基本操作方面有所不同。

链表就像一个节点链，每个节点包含数据和指向链中后续节点的指针等信息。有一个头指针，它指向链表的第一个元素，如果列表是空的，那么它指向null。

链接列表用于实现文件系统，哈希表和邻接表。

下图是链表内部结构的直观展示，它有3个节点：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA2NDcwMzU_size_16_color_FFFFFF_t_70 2]

链表分为2中类型：

*  单链表（单向）
 *  双向链表（双向）

#### 4.4.1、链表的基本操作 ####

*  InsertAtEnd—在链表结尾插入元素
 *  InsertAtHead—在链表开头插入元素
 *  Delete—删除链表的指定元素
 *  DeleteAtHead—删除链表第一个元素
 *  Search—在链表中查询指定元素
 *  isEmpty—查询链表是否为空

#### 4.4.2、链表常见面试题 ####

*  反转链表
 *  检查链表中是否存在循环
 *  返回链表倒数第N个元素
 *  移除链表中的重复元素

### 4.5、图（Graphs） ###

图是一组相互连接的节点。节点也称为顶点。一对节点连线（x，y）称为边（edge），表示顶点x连接到顶点y。边可能包含权重 （weight/cost）。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA2NDcwMzU_size_16_color_FFFFFF_t_70 3]

#### 4.5.1、图的分类与遍历算法 ####

图分为两种:

*  无向图
 *  有向图

在编程语言中，图有有以下两种形式表示：

*  邻接矩阵(Adjacency Matrix)
 *  邻接表(Adjacency List)

常见的图遍历算法：

*  广度优先搜索(Breadth First Search)
 *  深度优先搜索(Depth First Search)

#### 4.5.2、图常见面试题 ####

*  实现广度优先搜索
 *  实现深度优先搜索
 *  检查图是否为树
 *  统计图中边的个数
 *  查找两个节点之间的最短距离

### 4.6、树（Trees） ###

树是一种分层数据结构，由顶点（节点）和连接它们的边组成。树类似于图形，但区分树和图形的关键点是树中不存在循环。

树广泛用于人工智能和复杂算法，以提供解决问题的有效存储机制。

下图是一个简单树，以及树数据结构中使用的基本术语：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA2NDcwMzU_size_16_color_FFFFFF_t_70 4]

#### 4.6.1、树的分类 ####

*  N叉树(N-ary Tree)
 *  平衡树(Balanced Tree)
 *  二叉树(Binary Tree)
 *  二叉查找树(Binary Search Tree)
 *  平衡二叉树(AVL Tree)
 *  红黑树(Red Black Tree)
 *  2-3树(2–3 Tree)  
    其中 二叉树 和 二叉查找树是最常用的树

#### 4.6.2、树常见面试题 ####

*  计算树的高度
 *  在二叉搜索树中查找第k个最大值
 *  查找树中与根节点距离为k的节点
 *  查找二叉树中某个节点所有祖先节点

### 4.7、前缀树（Trie） ###

Trie，也称为“前缀树”，是一种树状数据结构，对于解决与字符串相关的问题非常有效。它提供快速检索，主要用于搜索字典中的单词，在搜索引擎中提供自动建议，甚至用于IP路由。

以下展示了三个单词“top”，“so”和“their”，在Trie中是如何存储的：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA2NDcwMzU_size_16_color_FFFFFF_t_70 5]

单词是按照字母从上往下存储，“p”, “s”和“r”节点分别表示“top”, “thus”和“their”的单词结尾

#### 4.7.1、Trie 常见面试题： ####

*  计算Trie中的单词总数
 *  打印存储在Trie中的所有单词
 *  使用Trie对数组的元素进行排序

### 4.8、散列表（Hash Table） ###

哈希(Hash)也叫做散列，它将对象转换为唯一标识符，该标识符通常用一个短的随机字母和数字组成的字符串来代表。哈希可以用来实现各种数据结构，其中最常用的就是哈希表(hash table)。

散列表通常使用数组实现。

散列数据结构的性能取决于以下三个因素：

*  哈希函数
 *  哈希表的大小
 *  碰撞处理方法

下图展示了有数组实现的哈希表，数组的下标即为哈希值，由哈希函数计算，作为哈希表的键(key)，而数组中保存的数据即为值(value)：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA2NDcwMzU_size_16_color_FFFFFF_t_70 6]

#### 4.8.1、常见的哈希面试题 ####

*  在数组中查找对称对
 *  查找数组是否是另一个数组的子集
 *  检查给定的数组是否互斥

[https_medium.freecodecamp.org_the-top-data-structures-you-should-know-for-your-next-coding-interview-36af0831f5e3]: https://medium.freecodecamp.org/the-top-data-structures-you-should-know-for-your-next-coding-interview-36af0831f5e3
[20190317154411817.png]: /images/20220307/a3b2a71c5efb470c8d9e04e1d8839d2c.png
[Link 1]: https://blog.csdn.net/u010647035/article/details/88628394
[Link 2]: https://blog.csdn.net/u010647035/article/details/88628405
[Link 3]: https://blog.csdn.net/u010647035/article/details/88650039
[Link 4]: https://blog.csdn.net/u010647035/article/details/88650003
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA2NDcwMzU_size_16_color_FFFFFF_t_70]: /images/20220307/9f357230601248918b579f3ee4bd7cf5.png
[Link 5]: https://blog.csdn.net/u010647035/article/details/88673959
[Link 6]: https://blog.csdn.net/u010647035/article/details/88674601
[Link 7]: https://blog.csdn.net/u010647035/article/details/88776388
[Link 8]: https://blog.csdn.net/u010647035/article/details/88776574
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA2NDcwMzU_size_16_color_FFFFFF_t_70 1]: /images/20220307/fae73e4e572749f1bf19d6a40ca4c110.png
[Link 9]: https://blog.csdn.net/u010647035/article/details/88778512
[K]: https://blog.csdn.net/u010647035/article/details/88776771
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA2NDcwMzU_size_16_color_FFFFFF_t_70 2]: /images/20220307/f13aed58aaa44695a77959bdb1c7c350.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA2NDcwMzU_size_16_color_FFFFFF_t_70 3]: /images/20220307/06b5ada4063c48f4875797cc3e80c3b5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA2NDcwMzU_size_16_color_FFFFFF_t_70 4]: /images/20220307/d40dffb5ed1a43b1a237ecdfc0fbb8f9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA2NDcwMzU_size_16_color_FFFFFF_t_70 5]: /images/20220307/9d21ca20cdd343e287b86ef14ddf441e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA2NDcwMzU_size_16_color_FFFFFF_t_70 6]: /images/20220307/a55876ab49da4c03801436c23c046b02.png