每位程序员都必须了解的顶级数据结构

引言

软件工程的基本组成部分，信息结构有效地协调和存储信息，以便进行高效的修改和检索。它们是创建算法和解决各种领域中的棘手问题的关键组成部分。

通常，数据结构决定了数据在计算机内存中的组织、存储和使用方式。它提供了一种有序的方式来管理和操作数据，使诸如插入、删除和搜索等任务更加高效。每种数据结构都是独一无二的，最适合特定的任务集。

每位开发人员都应该了解数据结构，因为它允许他们为特定问题选择最佳结构，从而提高算法性能和整体程序效率。精通数据结构的软件工程师能够优雅有效地解决各种计算问题。

所有程序员都需要了解的基本数据结构

1. 数组

在软件工程中，数组是最基本且最常用的数据结构之一。它们提供了一种在固定大小的结构中存储相同数据类型值的有序集合的方法。由于数组提供对元素的有效随机访问，因此它们适用于需要元素的位置顺序和检索的环境。现在，让我们更详细地看看数组。

特点

• 统一数据：数组通过存储完全相同数据类型的项来提供集合的同质性。
• 不可更改的大小：数组的大小在运行时无法更改；它在声明时就已确定。通常，大小表示为数值常量或在启动时提供的项目数量。
• 恒定的内存分配：由于数组的元素存储在连续的内存地址中，因此可以使用指针算法来有效地访问和遍历内存。

活动

• 索引 (访问)：索引用于访问数组中的元素；元素的索引告诉您它在数组中的位置。在许多计算机语言中，数组索引通常从 0 开始。
• 插入：必须将值分配给特定的数组索引才能将元素添加到数组中。然而，对于大型数组，插入过程可能效率低下，特别是当需要移动元素来为新元素腾出空间时。
• 删除：对于大型数组，从数组中删除元素可能在计算上成本很高，因为它需要重新定位其他元素以覆盖被删除成员留下的空间。
• 方向的改变：通过遍历数组中的每个元素来执行诸如打印、添加或搜索之类的操作。

时间复杂度

• 索引 (访问)：O(1)：由于元素存储在连续的内存位置，因此访问时间复杂度是恒定的。
• 添加和删除：最后，如果已知索引的值，则为 O(1) - 显示固定时间。O(n) - 在开始或中间时为线性时间复杂度，因为必须移动元素。

好处

• 有效的随机访问：数组在需要按位置快速获取元素的情况下非常有用，因为它们提供通过索引进行元素的恒定时间可访问性。
• 内存效率：数组使用的连续内存分配减少了内存开销，并促进了有效的内存访问。
• 易于使用的实现：由于它们与大多数编程语言兼容并且实现简单，因此开发人员可以轻松使用和访问数组。

缺点

• 不可更改的大小：由于其有限的大小，数组的灵活性可能不如它们可能的那样，特别是在集合的大小可能随时间变化的场合。
• 无效的添加和减法：由于它们可能需要重新定位元素以保持数组的连续性，因此插入和删除等操作可能效率低下，尤其对于大型数组而言。

用例

• 许多不同类型的数据结构，如列表、向量矩阵、表格和数据库，都使用数组。
• 由于其有效的随机访问，它们经常用于数据修改、排序和搜索的算法。

2. 链表

连接记录是直线型数据结构，由节点或项的有序列表组成。连接列表不像数组那样将元素保存在连续的内存位置中。相反，每个节点包含一个数据元素以及一个指向序列中下一个节点的引用（通常称为指针），从而形成类似于链的结构。通过这种动态内存分配，可以有效地创建或收缩连接列表。

链表类型

• 仅含一个链接的列表：链中的每个节点包含一个数据元素和指向链中下一个节点的引用。当最后一个节点连接到 null 时，列表结束。
• 包含两个链接的列表：每个节点都包含一个数据以及两个指针，一个指向它之前的节点，另一个指向它之后的节点。此双向链接可用于朝任一方向移动。
• 链接列表：当连接的循环列表中的最后一个节点引用第一个节点时，会形成一个循环结构。这可以简化某些过程，并且在需要连续循环时很有用。

使用链表管理操作

• 方向改变：迭代浏览或编辑连接列表的条目。
• 插入：在列表的开头、中间或结尾添加新节点。
• 消除：从名单中删除一个节点。
• 查找：在数据库中搜索特定部分。
• 接入：合并两个链表以创建一个单一的链接列表。
• 拆分：根据某个标准将一个链表分成两个独立的链表。
• 反转：改变链表的元素顺序。

互联列表的优点

• 可变大小：由于链表可以动态地增长或收缩，因此它们提供高效的内存分配。
• 更改和添加：插入和删除操作比数组操作更有效，因为它们涉及修改指针而不是移动对象，特别是对于大型列表。
• 内存利用：与数组相比，链表可以更好地利用内存，因为它们仅在需要时才为条目和引用使用内存。

链表的缺点

• 意外访问：与数组不同，链表不提供对其元素的随机访问。访问条目需要从头开始遍历列表，这增加了线性时间复杂性。
• 空间过载：由于链表需要更多内存来存储指针，因此与数组相比，它们的空间成本更高。
• 缓存位置：由于内存的非连续分配导致缓存局部性不足，因此性能可能比数组差，特别是对于大型列表。

用例

• 当需要频繁进行删除和插入操作时，可以使用链表来创建队列、栈或诸如哈希表之类的反应式数据库。
• 它们还用于内存系统管理，其中需要高效的内存分配和处理。

3. 栈

后进先出 (LIFO) 概念适用于栈，栈是线性系统，其中最先移除的元素是最后添加的项。它们用于顺序存储和管理数据；元素可以从栈顶添加和移除。

基本用途

• Push (入栈)：将对象放置在栈顶。
• Pop (出栈)：移除并替换栈顶元素。
• Peek (查看)，通常称为 Top (栈顶)，通过检索栈的顶部组件而不移除它。
• 使用 IsEmpty (判空) 函数检查集合是否为空。
• Size (大小)：返回栈中对象的总数。

执行

• 基于数组的栈：在此方法中，栈的项存储在固定大小的数组中。一个索引参数，根据元素的压入或弹出而增加或减少，代表栈的顶部。
• 基于链表的栈：在这种情况下，栈是使用链表实现的。链接列表的每个节点都包含数据以及指向下一个节点的引用。链表顶部的元素代表栈的最高点。

好处

• 易于使用和高效：使用和实现栈很容易。基于数组和基于链接列表实现的 push 和 pop 操作的时间复杂度为 O(1)。
• 内存处理：栈刚性的插入和删除顺序简化了内存管理，在操作顺序至关重要的情况下特别有用。
• 递归：递归算法使用栈通过调用栈来处理函数调用。每个函数调用都压入调用栈，并在函数返回时从调用栈中弹出。
• 反向操作：允许用户返回到早期状态或活动允许用户回溯的应用程序经常使用栈来提供撤销功能。

缺点

• 受限条目：栈只能执行某些操作，即 push、pop 和 peek。在不弹出所需元素之上的元素的情况下，无法实现元素的随机访问。
• 过载和缺额：基于数组的实现中的栈在尝试从空栈弹出时可能出现下溢，而在数组已满时出现上溢。基于链表的实现可能存在内存分配问题。

用例

• 表达式求值：为了求算术表达式、解析和将中缀表达式转换为后缀或前缀表示法，使用了栈。
• 函数调用管理：编译器和解释器使用栈来控制返回地址、局部变量和函数调用。
• 返回路径算法：在深度优先搜索 (DFS) 等回溯算法中，使用栈来保存路径或状态数据。

4. 队列

根据先进先出 (FIFO) 原则，先进先出原则指出最先添加的元素是最先移除的元素，队列是线性数据结构。它们模拟实际的队列或队伍，其中对象按到达顺序处理。在技术领域和日常应用中，队列常用于作业管理、进程调度和顺序数据处理。

基本功能

• Organise (入队)：将组件添加到队列的后部（尾部）。
• Dequeue (出队)：从队列的前部（头部）移除组件并将其返回。
• Peek (查看) (或 Front (队首))：在不删除的情况下，返回队列头部的组件。
• IsEmpty (判空)：验证等待列表是否为空。
• Dimensions (大小)：返回队列中项目的总数。

执行

• 基于数组的队列：在此方法中，队列的项存储在固定大小的数组中。第一个元素由前指针指示，最后一个元素由后指针指示。为了执行入队和出队操作，必须更新这些指针。然而，此技术在移动和调整项目大小时可能会出现问题。
• 基于链表的队列：在这里，队列是使用链表实现的。链表中的每个节点都包含数据以及指向下一个节点的引用。链表的头部和尾部分别由前指针和后指针表示。此方法消除了调整大小的开销，并提供了有效的入队和出队操作以及动态内存分配。

好处

• 易于使用和高效：队列易于设置和管理。基于数组和基于链表的解决方案在入队和出队过程中的时间复杂度均为 O(1)。
• 内存处理：与栈一样，队列具有刚性的插入和移除顺序，这有助于内存管理，特别是在操作顺序很重要的应用程序中。
• 任务组织：在调度算法中，队列常用于根据到达时间或优先级来组织和执行进程或活动。
• 资源共享：在支持多线程或并发操作的编程环境中，队列用于处理共享资源并维护有序的资源访问。

缺点

• 受限条目：队列支持的主要操作是入队、出队和查看。在未先出队的情况下，无法对元素进行随机使用。
• 过载和缺额：当数组已满时，基于数组的实现中的队列可能会溢出，而当队列为空时，可能会下溢。基于链表的实现可能存在内存分配问题。

用例

• BFS，或广度优先搜索：在图遍历算法（如 BFS）中，使用队列按找到的顺序处理节点。
• 组织方法：任务调度、操作系统作业调度和网络协议消息调度等算法都涉及队列。
• 打印假脱机：打印假脱机系统使用队列按提交顺序组织要打印的作业。

5. 树

在计算机科学中，树是常见的分层数据结构，用于以分层方式组织和排列数据。除了根节点（没有父节点）之外，它们由通过边连接的节点组成，每个节点有零个或多个子节点。由于树是递归数据结构，因此子树可以存在于其中。

使用的术语

• 根：树的最高节点。它是遍历树的起点，没有父节点。
• 节点：节点是树结构中的任何组件。节点可能与有效负载或值相关联。
• 父节点：连接到子节点的节点。
• 子节点：从根节点出发直接相互关联的节点。
• 叶子节点：没有子节点的节点。
• 子树：树内部包含的、本身也是一棵树的部分。
• 高度：连接叶子节点到其根节点的最长路径上的距离。它象征着树的深度。
• 深度：节点在树中的级别。根节点的深度为零，并且在此之后每个级别增加一。

树类型

• 二叉结构：树，其中左子节点和右子节点是每个节点最多可以拥有的两个子节点。由于它们在各种环境中都很有效且简单，因此二叉树得到了广泛使用。
• BST，或二叉搜索树：一棵二叉树，其中右子节点的值大于节点的值，左子节点的值小于节点的值。BST 提供有效的插入、删除和搜索功能。
• 平衡树：一棵树，它通过限制每个节点的左右子树之间的高度差异来保证高效的操作。
• AVL 树：一种自平衡二叉搜索树，通过限制每个节点的左右子树之间的高度差异来保持平衡。AVL 树保证了插入、删除和搜索操作的对数时间复杂度。
• B 树：一种为磁盘存储系统优化的平衡树数据结构。数据库和文件系统经常使用 B 树进行有效的数据索引和检索。

活动

• 方向改变：以中序、前序或后序方式遍历树，以特定的顺序访问和处理每个节点。
• 搜索：在树中搜索特定值或节点。
• 插入：将新节点添加到树中。
• 删除：从树中删除一个节点，而不影响其结构完整性。

用途

• 信息存储：为了有效的数据存储和检索，树用于索引结构、文件系统和数据库。
• 层次结构组织：组织图、文件目录和 XML/HTML 文档等层次结构被表示为树。
• 算法：多种算法，包括排序、二分搜索和动态规划，都使用树。

好处

• 有效搜索：对于需要快速获取数据的应用程序，树是一个不错的选择，因为它们提供了有效的搜索操作。
• 组织结构：层次结构：树提供了一种表示数据片段之间层次关系的自然方法。
• 适应性：树足够灵活，可以适应各种数据格式和应用程序。

缺点

• 复杂性：某些树活动，如遍历和平衡，可能很复杂，需要谨慎进行。
• 内存开销：由于树比线性数据结构需要更多的指针和元数据，因此它们的内存开销可能更大。

6. 图

图是用于显示对象连接的灵活数据结构。它们由一组节点（顶点）组成，节点通过边（线或弧）连接。图经常用于描述复杂的交互，并在计算、社交媒体、交通网络和生物网络等各个行业的广泛问题中得到解决。

图类型

• 无向图：具有顶点之间对称交互的图，由无方向的边表示。如果顶点 A 和 B 之间存在一条边，则它们之间存在边，反之亦然。
• 有向图：顶点之间的交互是单向的，边具有方向的图。除非存在从顶点 A 到顶点 B 的直接边，否则不能保证存在从顶点 B 到顶点 A 的边。
• 加权图：在其边上附加成本或权重的图。这些权重表示顶点之间链接的强度、成本或距离。
• 无权图：所有边的权重都相同或相等的图。
• 循环图：至少包含一个循环的图，表示一条路径从单个顶点开始并结束于该顶点。
• 无环图：不包含任何循环的图。有向无环图 (DAG) 在动态规划和拓扑排序等技术中特别有用。
• 连通图：任意一对顶点之间都存在一条路径的图。
• 非连通图：其中某些顶点对之间缺乏路径的网络，表明它具有两个或多个不连通的分量。

图的表示

• 邻接矩阵：二维数组，其中索引 [i][j] 的值表示顶点 i 和 j 之间是否存在边。加权图的条目可能是边的权重。
• 邻接表：数组或列表的集合，其中每个顶点都有一个相邻顶点的列表。对于加权图，每个条目可能还包含相关边的权重。

图操作

• 遍历：使用系统方法，如深度优先搜索 (DFS) 或广度优先搜索 (BFS)，来访问图中的每个顶点和边。
• 最短路径：在加权网络中，查找两个顶点之间的最短路径，有时使用 Bellman-Ford 或 Dijkstra 等算法。
• MST，或最小生成树，是：识别具有最低可行总边权重的边子集，该子集连接树中的所有顶点。为了找到 MST，两种流行的算法是由 Prim 开发的算法和 Kruskal 的方法。
• 拓扑排序：将有向边无环图的顶点按线性顺序排列，以便对于连接 u 到 v 的每条有向边 uv，u 都出现在 v 之前。
• 图着色：为图中的每个顶点分配一种颜色，以便没有两个相邻的顶点具有相同的颜色。编译器使用图着色进行寄存器分配、调度和地图着色。

图的应用

• 社交媒体：对 Twitter、Facebook 和 LinkedIn 等社交网络上的用户连接进行建模。
• 交通网络：表示公共交通系统、航空链接和道路网络。
• 网络路由：确定计算机网络上数据传输的最佳路径。
• 推荐系统：根据关系和用户偏好推荐商品、电影或服务。
• 生物信息学领域：检查生物网络，例如基因调控和蛋白质-蛋白质相互作用的网络。

好处

• 灵活性：图在许多不同学科中都有用，因为它们可以表示各种各样的关系和问题。
• 表达：图以简洁直观的方式表示复杂的交互，这有助于理解和分析。

缺点

• 复杂性：特别是对于大型网络，一些图算法，例如发现最大流或最短路径的算法，可能具有显著的时间和空间复杂度。
• 实现成本：与数组或链表等简单数据结构相比，图方法和数据结构的实现可能更复杂。

7. 哈希表

哈希表是存储键值对的数据结构，并提供快速的查找、插入和删除过程。它们也称为哈希映射或关联数组。它们应用一种称为哈希的方法将键映射到数组索引，从而实现常数时间平均情况下的项使用。

哈希

使用哈希函数（该函数使用输入键生成固定大小的数值（哈希码））可以将键哈希到数组索引。在存储匹配值的底层数组中，哈希码充当索引。为了减少冲突，哈希函数最好应将键均匀分布在整个数组中（即各种键映射到单个索引的情况）。

活动

• 插入：哈希函数接收键值对，计算键的哈希码，这告诉我们在数组中存储该值的位置索引。如果地址索引已经被占用，则使用冲突解决方法（例如链表法或开放地址法）来解决冲突。
• 获取：哈希函数搜索数组中的相关索引，并生成键的哈希码，以获取与特定键相关联的值。如果键在计算出的索引处不存在，则使用冲突解决方法来查找正确的条目。
• 删除：当删除键值对时，会使用键的哈希码找到相应的项，并根据冲突解决方法，将其从列表中删除或标记为已删除。
• 冲突解决方法：当多个键映射到相同的数组索引时，会使用冲突解决方法。常见的冲突解决方法技术有：
  • 链表法：为了处理冲突，每个数组索引都存储一个链表或其他等效数据结构。在连接到索引的链表中，冲突的键被存储为节点。
  • 直接寻址：通过在数组中搜索另一个空闲位置来避免冲突。双重散列、二次探测和线性探测是探测技术的示例。

时间复杂度

• 典型示例：O(1)：假设有效的冲突解决方法和分布良好的哈希函数，插入、检索和删除等操作具有常数时间复杂度。
• 最坏情况：在最坏的情况下，如果冲突没有得到充分控制，性能将下降，复杂度将是线性的。

用途

• 数据库：数据库索引和哈希连接算法使用哈希表来快速查找记录并执行连接操作。
• 缓存：在缓存系统中，哈希表用于存储频繁请求的数据，以便快速检索。
• 符号表：编译器、翻译器和符号解析系统使用哈希表来实现符号表。

好处

• 快速查找：哈希表在存储和检索数据方面非常有效，因为它们提供平均情况下的常数时间搜索、插入和删除操作。
• 可变尺寸：为了确保最佳的内存消耗和效率，哈希表可以动态地扩展以适应可变数量的项目。

缺点

• 内存开销：由于冲突解决方法和可能的空位，哈希表可能需要更多的内存。
• 确定性行为：在极端情况下，如果冲突管理不当，哈希表可能表现 erratic。

8. 堆

满足父子节点之间特定排序要求（称为堆属性）的完整二叉树结构称为堆。最大堆中的任何单个节点 i 的值都大于或等于其所有后代的任何值。最小堆中的任何给定节点 i 的值都小于或等于其所有后代的任何值。

堆的特征

• 完整二叉树：由于堆是完整二叉树，除了可能从左到右填满的最后一层外，所有层都已填满。
• 堆属性：最大堆中的每个节点的值至少等于其后代的值。最小堆中的每个节点的值都小于或等于其后代的值。
• 子父关系：堆中每个节点的值要么大于或等于其子节点的值（最大堆），要么小于或等于其子节点的值（最小堆）。

活动

• 插入：在不破坏堆属性的情况下增大堆的大小。插入后，新元素及其父节点会根据堆属性进行交换，直到堆属性恢复。
• 删除：在删除堆的根元素（在最大堆中可能是最大值，在最小堆中可能是最小值）后，重新排列剩余的元素以恢复堆属性。
• 堆化：从一组元素构建堆。此阶段涉及对每个子树多次应用堆结构，以确保整个树满足堆属性。

时间复杂度

• 插入：O(log n)：将额外元素添加到堆所需的遍历时间，从起始点到根，是元素数量的指数级。
• 删除：O(log n)：删除堆属性和根元素也需要对数时间。
• 堆化：O(n) - 从 n 个元素的数组构建堆需要 O(n) 次操作。

堆的类型

• 最大堆：在最大堆中，每个父节点的值大于或等于其所有子节点的值。最大值位于堆的根部。
• 最小堆：在最小堆中，每个父节点的值小于或等于其子节点的值。最小值位于堆的底部。

应用

• 优先级队列：堆通常用于构建优先级队列，其中根据其重要性（最大值或最小值）出队项目。
• 堆排序：高效的排序算法堆排序通过使用堆数据结构，以升序或降序对对象进行排序。
• 图算法：多种图算法，如 Dijkstra 的最短路径算法和 Prim 的最小生成树方法，使用堆来根据权重高效地选择下一个顶点或边。

优点

• 可用操作：对于访问、删除和插入操作，堆在最坏情况下的时间复杂度为 O(logn)。
• 空间效率：堆能高效地利用内存，因为它们只需要存储对象和必要指针所需的空间。

缺点

• 不稳定排序：尽管堆排序是一种强大的排序算法，但它缺乏稳定性，因此具有相同键的项可能不会以相同的顺序出现。
• 访问限制：与其他数据结构（如数组或链表）不同，堆不允许对项进行有效的随机访问。