作为Android开发者；下次面试你应该知道的数据结构和二十三种

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

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

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

一丶什么是数据结构

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

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

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

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

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

你在准备面试吗？

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

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

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

1.数组

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

例如，如果您要存储 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

数组的一些基本操作：

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

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

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

2.链表

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

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

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

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

链表的一些基本操作：

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

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

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

3.哈希表

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

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

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

  hashFunction(k): k % 10

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

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

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

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

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

4.堆

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

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

以下是堆栈的示例：

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

Stack上的一些基本操作：

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

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

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

5.队列

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

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

以下是队列的示例：

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

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

Queue的一些基本操作：

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

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

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

6.树

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

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

一些与树相关的术语是：

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

一些类型的树是：

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

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

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

7.图形

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

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

下面是一个图表的例子：

以下是图表的类型：

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

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

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

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

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

三丶该说二十三种设计模式

1.设计模式概念

设计模式（Design pattern）是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结。使用设计模式是为了可重用代码、让代码更容易被他人理解、保证代码可靠性。毫无疑问，设计模式于己于他人于系统都是多赢的，设计模式使代码编制真正工程化，设计模式是软件工程的基石脉络，如同大厦的结构一样。

即12字真言：设计模式是设计经验的总结

通俗地说，就是解决问题的方法，是前辈们归纳总结出来的便于人们理解使用，增加代码的可维护性、可复用性、可扩展性。

2.设计模式的几个分类

创建型模式：对象实例化的模式，创建型模式用于解耦对象的实例化过程。结构型模式：把类或对象结合在一起形成一个更大的结构。行为型模式：类和对象如何交互，及划分责任和算法。

如下图所示：

3.每个模式分类中有哪些关键点？

单例模式：不要存在多于一个导致类变更的原因。通俗地说，即一个类只负责一项职责

简单工厂：一个工厂类根据传入的参量决定创建出哪一种产品类的实例。

工厂方法：定义一个具体功能相关的接口，由子类来决定这么实现。

抽象工厂：创建相关或依赖对象的家族，而无需明确指定具体类。

建造者模式：封装一个复杂对象的构建过程，并可以按步骤构造。

原型模式：将一个对象作为原型，通过复制的方式，克隆出多个和目标实例类似的新实例。

适配器模式：将一个类的方法接口转换成客户希望的另外一个接口。

组合模式：将对象组合成树形结构以表示“”部分-整体“”的层次结构。

装饰模式：动态地给对象添加新的功能。

代理模式：为其他对象提供一个代理以便控制这个对象的访问。

亨元模式：通过共享技术来有效地支持大量细粒度的对象。

外观模式：对外提供一个统一的方法，来访问子系统中的一群接口。

桥接模式：将抽象部分和它的实现部分分离，使它们都可以独立的变化。

模板模式：定义一个算法结构，而将一些步骤延迟到子类实现。

解释器模式：给定一个语言，定义它的文法的一种表示，并定义一个解释器。

策略模式：定义一系列算法，把它们封装起来，并且使它们可以相互替换。

状态模式：允许一个对象在其对象内部状态改变时改变它的行为。

观察者模式：对象间的一对多的依赖关系。

备忘录模式：在不破坏封装的前提下，保持对象的内部状态。

中介者模式：用一个中介对象来封装一系列的对象交互。

命令模式：将命令请求封装为一个对象，使得可以用不同的请求来进行参数化。

访问者模式：在不改变数据结构的前提下，增加作用于一组对象元素的新功能。

责任链模式：将请求的发送者和接收者解耦，使得多个对象都有处理这个请求的机会。

迭代器模式：一种遍历访问聚合对象中各个元素的方法，不暴露该对象的内部结构。

4.细说23种设计模式

由于内容偏长，这里整理了一个关于23种设计模式的文档。