Android开发者下次面试应该知道这些数据结构

糟糕的程序员担心代码。优秀的程序员担心数据结构及其关系 ——Linus Torvalds

这是非常真实的。这就是为什么每个雇主在面试时都希望候选人对数据结构有充分的了解。这也适用于 Android 开发人员。

在这篇帖子中，其中将涵盖所有的数据结构，对于任何Android开发者来说，面试和知识都是必不可少的。虽然还有很多东西要学习，但我将介绍 Android 面试中最常用和最常见的问题。

什么是数据结构？

数据结构是一种数据组织、管理和存储格式，可实现高效访问和修改。

更准确地说，数据结构是数据值、它们之间的关系以及可应用于数据的功能或操作的集合。

例如，我们有一些数据，人名“ABC”和年龄25。这里“ABC”是字符串数据类型，25 是整数数据类型。

我们可以将此数据组织为像用户记录一样的记录，其中将包含用户的姓名和年龄。现在我们可以将用户的记录作为数据结构收集并存储在文件或数据库中。

现在，让我们看看 Android 中最常用和最常被问到的数据结构。

你在准备面试吗？

Android 中最常用和询问最多的数据结构

• 数组
• 链表
• 哈希表
• 堆
• 队列
• 树
• 图形

让我们一一详细研究所有这些数据结构。

数组

数组是用于存储同类数据的最常用和最简单的数据结构。数组是存储在连续内存位置的相似项的集合。

例如，如果您要存储 10 个学生的分数，那么您可以通过为每个学生创建 10 个整数变量来做到这一点，并且您可以将分数存储在这些变量中。但是您必须在这里管理 10 个不同的变量，这是一项非常困难的任务，因为如果将来您必须存储 1000 名学生的分数，那么如果您遵循这种方法，则必须创建 1000 个变量。

因此，我们可以为此目的使用数组。您需要做的只是创建一个名为“marks”的数组，大小为 10 或 1000 或其他任何值，然后将标记存储在该数组中。

注意：在几乎所有编程语言中，我们都使用基于 0 的索引，即数组的索引将从 0 开始，一直到 n-1，其中“n”是数组的大小。

您可以借助其索引访问数组的元素：

marks[0] // to access the 1st element i.e. element at index 0
marks[2] // to access the 3rd element i.e. element at index 2
marks[4] // to access the 5th element i.e. element at index 4

数组的一些基本操作：

• 插入：在数组的特定索引处插入给定元素
• 删除：从数组中删除给定元素
• 搜索：在数组中搜索特定元素
• 更新：在特定索引处更新数组的元素
• 遍历：打印或遍历整个数组

与数组相关的几个问题要尝试：

• 数组中的最大值和最小值
• 反转数组
• 数组中的最小绝对差

  链表

链表几乎类似于数组，即它也是一种线性数据结构，用于存储相同类型的数据。这里，数据不是以连续方式存储的。链表中存储的数据是以节点的形式存储的，每个节点都可以通过一些指针或对下一个节点的引用连接到另一个节点。

因此，链表中的节点有两部分，即数据部分和指针或引用部分。数据部分存储节点的数据，而指针或引用部分存储下一个节点的地址（如果有）。

上图是单链表的一个例子，即这里我们只有下一个节点的地址。还有一个称为“双向链表”的链表，其中前一个节点和下一个节点的地址由任何节点保存。除了这两种类型的链表，我们还有一个“循环链表”。

在上图中，“Head”指向链表的第一个节点，链表的最后一个节点指向“Null”，即在该节点之后没有节点。

链表的一些基本操作：

• 插入：在这里，您必须将节点插入到链表中。您必须在链表的末尾或链表的开头或链表之间的任何位置插入节点。
• 删除：在删除操作中，您必须从前面删除节点，即您必须删除头节点，或者您必须从链表中删除任何节点。
• 搜索：您将获得一个元素，您必须在链接列表中搜索该元素。
• 遍历：遍历整个链表，得到链表的每一个元素。

与链接列表相关的几个问题要尝试：

• 将链表从位置 m 反转到 n
• 检测和删除链表中的循环
• 从链表末尾删除第 n 个节点
• 从排序列表中删除重复项

  哈希表

哈希表是一种数据结构，用于以“键值”对的形式存储数据。您将拥有一些值或数据，并基于该数据生成一个键，并在该键的帮助下将值存储在哈希表中。如果输入是均匀分布的，那么哈希表将在 O(1) 时间内执行插入、删除和搜索操作。

生成密钥并基于该密钥存储数据的过程称为“哈希”。要从数据中生成密钥，我们需要一个称为“哈希函数”的函数。哈希函数将数据作为输入，并将密钥作为输出。

例如，如果要存储的数据是：1、2、3、4、5、26、17，使用的哈希函数是：

hashFunction(k): k % 10

并且数据将通过以下方式存储在哈希表中：

使用 Hash Table 时要考虑的几点：

• 哈希函数应该使得生成的键是均匀分布的。
• 哈希表的大小取决于哈希函数。所以，哈希函数的选择应该做到完美。
• 在哈希表中发生冲突的情况下，应用适当的冲突处理技术。

与哈希表相关的几个问题可以尝试：

• 最长连续序列
• 有效的字谜
• 总和为 0 的最大子数组
• 字符串中的第一个唯一字符

堆

堆栈是使用后进先出顺序（LIFO）的线性数据结构，即最后插入的元素将首先弹出。例如，如果您将一本书放在其他书上并继续此过程 50 本书，那么将首先获取最上面的书。在这里，您可以注意到最上面的书是放在最后或最近放置的书。

在 Stack 中，我们有一个“Top”变量表示堆栈的顶部。这是必要的，因为堆栈的所有操作都是在“Top”变量的帮助下完成的。

以下是堆栈的示例：

如果要从上面的 Stack 中删除元素，那么会先删除 5，然后再删除 4、3、2、1。

Stack上的一些基本操作：

• Push()： Push 用于在栈顶插入一个元素。
• Pop()： Pop用于从栈顶删除一个元素。
• Top：顶部用于表示堆栈的顶部元素。

与 Stack 相关的几个问题可以尝试：

• 检查表达式中的平衡括号
• 使用递归反转堆栈
• 使用堆栈实现队列
• 使用另一个堆栈对堆栈进行排序

  队列

队列是使用先进先出（FIFO）顺序的线性数据结构，即队列中最先出现的元素将首先从队列中删除。例如，在排队订票时，先来的人会先订票，而新来订票的人必须站在队列的最后。

在队列中，我们有“前”和“后”。Front 用于指向队列的前面元素，而 Rear 用于指向队列的后面元素。

以下是队列的示例：

因此，如果要从上述队列中删除元素，则首先删除 1，然后删除 2、3、4 和 5。

同样，如果你想在上面的队列中插入一个元素，那么它将从 Rear 而不是Front插入。

Queue的一些基本操作：

• Enqueue()： Enqueue 用于在 Queue 的末尾插入一个元素。
• Dequeue()： Dequeue用于从Queue的最前面删除一个元素。
• Front：用于表示Queue的最前面的元素。
• Rear：用于表示Queue的Rear元素。

与队列相关的几个问题要尝试：

• 使用堆栈实现队列
• 反转队列的前 k 个元素
• LRU缓存实现

树

树是一种非线性的分层数据结构，用于以节点的形式存储数据。在这里，我们有节点，所有节点都在它们之间绘制的边的帮助下相互连接。一个父节点可以没有子节点，也可以有一个子节点或多个子节点。但是子节点不能有多个父节点。

下面是一个简单的树示例：

一些与树相关的术语是：

• 根：根是存在于树顶部的节点。一棵特定的树只能有一个根。
• 父节点：所有至少有一个子节点的节点称为父节点。
• Child：父节点下面的节点称为父节点的子节点。
• 叶：具有零个子节点的节点称为叶节点。

一些类型的树是：

• 一般树
• 二叉树
• 二叉搜索树
• AVL 树
• 红黑树
• N叉树

与树相关的几个问题要尝试：

• 在二叉树上查找高度
• 二叉树中所有节点距离K
• BST 中的第 K 个最大元素
• 合并两个 BST

图形

图形类似于树，即它也是一种非线性数据结构，以节点的形式存储数据，并且所有节点在边的帮助下相互连接。树和图之间的区别在于，图中有一个循环，但在树的情况下没有这样的循环。

图由一组有限的节点和一组负责连接节点的有限边组成。

下面是一个图表的例子：

以下是图表的类型：

• 有向图：这里的边将指向某个节点，即您将有一个箭头从一个节点指向一个节点。
• 无向图：节点之间没有箭头。上面的例子是一个无向图的例子。

一些常见的图遍历技术有：

• 深度优先搜索（DFS）
• 广度优先搜索（BFS）

与 Graph 相关的几个问题要尝试：

• 字梯问题
• 棋盘上的骑士
• 岛屿数量
• 根据给定的约束检查数组中的循环

公众号：Android Jasper 专注分享面试题｜面试技巧｜Android学习资料。（d：16）