8种基本数据结构简介，了解最常见数据结构背后的基本概念

我们对作为程序员的数据结构的理解主要限于以编程语言在更高的抽象水平上使用它们。尽管我们知道如何使用一种特定的编程语言来存储和检索来自不同数据结构的数据，但是我们大多数人都不会试图弄清楚这些数据结构的较低层实现中发生的情况。

8种基本数据结构

在大多数情况下，数据结构的表面知识足以以某种方式完成我们的工作。但是，在为给定任务选择最佳数据结构时，了解不同数据结构在较低级别的行为至关重要。在本文中，我们将介绍8种不同的数据结构，并探讨它们如何处理数据。

---

数组

数组数据结构存储单个数据类型的固定数量的数据。数组中的元素（项目）存储在一块连续的内存插槽中。因此，为数组中的元素分配了从0或1开始的连续数字作为其“索引”。

可以使用其唯一索引随机访问数组中存储的单个元素。使用索引访问元素的时间复杂度为Θ（1）。以这种方式可以容易地实现读取或更新数组元素。由于数组元素的位置连续，因此与大多数其他数据结构相比，数组遍历更快。

在数组中插入或删除数组是一项相当复杂且耗时的任务。插入时，当前数组中的所有元素都将被复制到具有增加的大小的新创建的数组中，并且新元素将被添加到新数组的末尾。还以类似的方式实现删除以减小阵列大小。

应用范围：

数组可以是多维的（数组数组）。这使数组成为存储矩阵和向量的好选择。数组经常用于实现其他数据结构，例如列表，堆，堆栈和队列。

---

队列

队列数据结构类似于我们在日常生活中看到的队列：第一个进入队列的人是第一个获得下一次退出队列的机会的人。在编程世界的队列版本中，添加到队列中的每个新数据元素都存储在后端，从队列中删除的每个元素都从前端获取（基于先进先出）。

队列操作

• 排队：将元素插入队列的末尾。新添加的元素成为队列的后部元素。

• 出队：从队列的前面删除元素。入队和出队操作的时间复杂度均为Θ（1）。

• 窥视：读取队列开头的元素，而无需删除或修改它。

应用领域

队列用于实现缓冲区。多线程使用队列来管理等待线程执行的任务。

---

堆

堆栈与队列非常相似，但是堆栈是基于后进先出而不是先进先出的基础来实现的。考虑一堆盘子，最后添加的盘子是将要删除的第一个盘子。

堆栈操作

• 推送：在堆栈顶部插入一个新元素。新添加的元素将成为新的顶级元素。
• 弹出：从堆栈顶部删除元素。推和弹出操作的时间复杂度均为Θ（1）。
• 窥视：读取堆栈顶部的元素，而无需删除或修改它。

应用领域

堆栈用于处理和评估数学表达式。它们还用于使用回溯过程的算法中。在递归编程中处理递归函数调用是另一个应用程序。

---

链表

链表是一种动态数据结构。这意味着存储在链接列表中的数据项的数量可以轻松扩展或缩小。与具有固定大小的数组相比，这使链表具有更大的灵活性。链接列表通过将每个项目存储为单独的对象来实现这种动态质量。

链表中的元素不必存储在连续的内存插槽中，而是每个元素（称为节点）都存储指向下一个节点位置的指针。这些指针维护与链表中各个节点的连接。除了指向下一个节点的指针之外，节点还存储数据字段。

链表中有两个重要节点：头和尾。

• 头：链表的第一个节点。
• 尾巴：链接列表的最后一个节点。尾巴的指针值设置为null。

将新元素插入链表时，新数据字段将存储在内存中的特定位置，并且前一节点中的指针将更新为指向新节点。新节点存储先前存储在先前节点中的指针。

在删除节点时，将为删除节点之前的节点提供先前存储在删除节点中的指针。

但是，对于链接列表，如果不从头开始遍历列表，就无法直接访问单个数据项。这使访问操作的时间复杂度为Θ（n）。

链接列表类型

• 单链接列表：上面示例中显示的链接列表都是单链接列表。一个节点仅包含指向下一个节点的指针。
• 双链表：双链表中的节点包含指向给定节点之前和之后的节点的指针。列表的遍历可以向前和向后进行。
• 圆形链表：尾巴的指针指向头部，而不是null。本质上，圆形链表没有尾巴，只有一个头。

应用领域

链接列表用于实现数据结构，如堆栈，队列和图形。当执行多项式代数运算时，使用链表存储常数。

---

图形

图形由称为顶点（V）的有限数量的数据项组成。这些顶点中的某些对通过边（E）彼此链接。通过一条边连接的两个顶点彼此相邻。

可以使用不同的属性对图形进行分类。这样的分类之一是有向图和无向图。

• 在有向图中，连接两个顶点的边具有起点和终点。遍历图形时，只能从起始顶点到结束顶点相交。

• 在无向图中，可以无限制地在两个方向上遍历边。

常见数据结构应用

诸如Facebook之类的社交媒体应用程序使用图形将用户表示为顶点，将其友谊表示为边缘。Google页面排名算法使用图形表示网页和连接网页的链接。Google Maps使用图形表示其交通系统中的道路网络。

---

二叉树

二叉树与有向图相似。两者之间的区别在于，在一棵二叉树中，数据以分层结构存储，其中上层节点称为父级，下层节点称为子级。二叉树中的一个节点只能有一个父节点，最多两个孩子。

让我们看一些与二叉树相关的术语。

• 根：树顶部的节点。它没有父节点。
• 叶：树底部的一个节点。它没有子节点。
• 密钥：存储在节点中的数据值。
• 子树：由节点的所有后代组成的树

有许多特殊的二叉树，例如Binary Search Tree，Treap，Binary Tries和Heap。

二进制搜索树

二进制搜索树按排序顺序存储数据值。二进制搜索树中节点的左子节点的值必须小于父节点，而右子节点的值必须大于父节点。

顾名思义，BST的主要优点是能够快速搜索存储的数据。在BST中搜索存储元素的时间复杂度为O（log n）。

应用领域

• 二进制搜索树用于以编程语言实现映射和设置对象
• 二进制尝试用于存储路由器表。
• 挖掘用于无线网络。

---

堆

堆是二叉树的另一种特殊情况。在堆中，将根的密钥与其子代的密钥进行比较，以特定方式进行排列。有两种类型的堆。

• 最大堆：父项的密钥大于或等于子项的密钥。根节点将最大值存储在给定的数据集中。
• 最小堆：父项的密钥小于或等于子项的密钥。根节点将最小值存储在给定的数据集中。

假设我们获得了整数值（33、24、45、12、90、78、23、53）作为数据集。我们可以根据此数据构造一个单独的最大堆和最小堆。

最小堆

最大堆

在堆中插入，删除和提取最大（或最小）函数的时间复杂度为O（log n）。但是找到最大值（或最小值）仅具有O（1）的时间复杂度。

应用领域

堆用于实现堆排序算法。堆还用于实现优先级队列，因为堆的第一个元素始终存储具有最大（或最小）优先级的值。

---

哈希表

当我们要保持对大型数据集的搜索和插入操作的速度时，哈希表是可以使用的最高效的数据结构之一。哈希表中存储的每个数据值都与一个键相关联，如果我们知道该键，该键可以快速访问存储的值。考虑一个学生注册系统，其中每个学生都有一个唯一的学生ID，可以用作将其数据存储在哈希表中的密钥。

哈希表使用数组来存储数据值。该键用于在存储值的数组中查找索引。但是，哈希表如何将这些键及其值映射？

可以使用的一种方法是直接寻址。它使用一对一映射：每个关键点都指向其数据存储在的确切位置。但是这种方法不能有效地使用内存，尤其是当键值对的数量增加并且键的大小变大时。因此，哈希表使用哈希函数。

哈希函数

哈希表使用哈希函数将数据值映射到其键。它将一系列键值转换为一系列数组索引。通过将键传递给哈希函数生成的索引或值称为哈希值。这是示例哈希函数。

h(k) = k % m

• h是哈希函数
• h（k）是对应于密钥k的哈希值
• k是关键
• m是哈希表的大小。m的一个不错选择是质数不接近2的幂。

让我们考虑几个键的哈希值。考虑m = 20。

• k = 1001，h（k）= 1001％20 = 1
• k = 1055，h（k）= 1055％20 = 15
• k = 20123，h（k）= 20123％20 = 3

对于k个值1001、1055和20123，它们的关联值分别存储在哈希表中的索引1、15和3处。

考虑密钥2021的哈希值1。我们之前看到与密钥1001相关的值存储在哈希表的索引1中。当两个键生成的哈希值相似时，我们称其为冲突。哈希表使用链接和开放式寻址等技术来解决此冲突问题。

哈希表的搜索和插入时间复杂度为O（1）。

应用领域

哈希表用于实现数据库索引。编译器使用哈希表来标识编程语言中的关键字。计算机使用哈希表将文件名与其路径链接。

---

结论

本文提供了对我们作为程序员每天与之交互的8种数据结构的基本逻辑的基本介绍。了解了不同数据结构的独特属性后，从今天起，您可以更加谨慎地为编程任务选择最合适的数据结构。但是请记住，这只是一个基本介绍。您可以做更多的事情，并且应该了解数据结构。

本文翻译自：https://towardsdatascience.com/introduction-to-8-essential-data-structures-7ef867bd1dd