基本数据结构

相关源文件

• assets/wechat-group-chat.jpeg
• problems/101.symmetric-tree.md
• problems/155.min-stack.md
• problems/167.two-sum-ii-input-array-is-sorted.md
• problems/203.remove-linked-list-elements.md
• problems/219.contains-duplicate-ii.md
• problems/220.contains-duplicate-iii.md
• problems/26.remove-duplicates-from-sorted-array.md
• problems/283.move-zeroes.md
• problems/349.intersection-of-two-arrays.md
• problems/42.trapping-rain-water.en.md
• problems/42.trapping-rain-water.md
• selected/README.md
• thinkings/basic-data-structure.md
• thinkings/binary-tree-traversal.md
• thinkings/graph.md

本文概述了算法问题解决中使用的基本数据结构。我们将重点介绍线性数据结构和非线性数据结构，包括它们的实现、操作和实际应用。本页涵盖了构成存储库中更复杂算法和解决方案基础的核心数据结构。

有关更高级的图特定结构和算法的信息，请参阅图。

线性数据结构

数据结构可以逻辑上分为线性或非线性。线性结构包括数组、栈、队列和链表，而非线性结构包括树和图。

需要注意的是，线性或非线性的逻辑分类不一定反映这些结构在内存中的存储方式——它纯粹是一种逻辑区别。例如，我们可以使用数组来存储二叉树。

来源：thinkings/basic-data-structure.md7-11

数组

数组是最简单的数据结构，它允许以常数时间O(1)进行索引访问来存储元素集合。许多其他数据结构都是基于或使用数组实现的。

数组支持以下基本操作：

• 通过索引进行O(1)时间的随机访问
• 插入/删除通常需要O(n)时间，因为涉及到元素移位
• O(n)时间的线性搜索（除非已排序，在这种情况下可以使用O(log n)的二分查找）

在仓库中，数组被广泛用于涉及以下问题：

• 双指针技巧
• 滑动窗口
• 前缀和

来源：thinkings/basic-data-structure.md13-17 problems/26.remove-duplicates-from-sorted-array.md61-72 problems/283.move-zeroes.md36-43

队列

队列是一种受限的序列，元素只能在队尾添加（入队），从队头移除（出队），遵循先进先出（FIFO）原则。

实际应用：HTTP请求处理以及解决HTTP/1.1与HTTP/2中的队头阻塞问题

在HTTP/1.1中，请求被排队并且必须等待之前的响应（队头阻塞），而HTTP/2使用多路复用以允许同时进行请求和响应。

来源：thinkings/basic-data-structure.md70-114

栈

栈是一种受限的序列，元素只能从顶部添加和移除，遵循后进先出（LIFO）原则。

栈广泛应用于：

• 函数调用管理（调用栈）
• 表达式求值和解析
• 撤销机制
• 深度优先搜索算法

一个实际例子是JavaScript的执行栈

仓库中的例子：实现一个支持push、pop、top操作，并能在常数时间内获取最小元素的最小栈。

来源：thinkings/basic-data-structure.md128-176 problems/155.min-stack.md41-79

链表

链表是一种线性数据结构，其中元素存储在节点中，每个节点包含数据和指向下一个节点的引用。

基本操作：

• 插入：若已知位置则为O(1)，若需搜索则为O(n)
• 删除：若已知位置则为O(1)，若需搜索则为O(n)
• 遍历：O(n)
• 访问：O(n)（相比数组的O(1)）

链表用于实现其他数据结构，如栈、队列，以及需要高效插入和删除操作的场景。

React实现中的一个实际应用是Fiber架构

React Fiber使用链表结构来使工作可以暂停和恢复，从而允许对UI更新进行优先级排序。

来源：thinkings/basic-data-structure.md182-243 problems/203.remove-linked-list-elements.md28-39

非线性数据结构

非线性数据结构用于数据元素之间存在层级或网络关系而非顺序关系的场景。它们在表示复杂关系和支持动态操作方面特别高效。

来源：thinkings/basic-data-structure.md246-250

树

树是具有根节点和子节点的层次结构。它们用于表示层次关系、组织数据以进行高效搜索等。

树的关键属性：

• 对于n个顶点，树恰好有n-1条边
• 任意两个节点之间恰好有一条路径
• 树没有环

树的遍历方法：

• 前序遍历：先访问根节点，然后左子树，然后右子树
• 中序遍历：先访问左子树，然后根节点，然后右子树
• 后序遍历：先访问左子树，然后右子树，然后根节点
• 层序遍历：从上到下逐层访问节点

来源：thinkings/basic-data-structure.md252-271 thinkings/binary-tree-traversal.md24-44

二叉树

二叉树是一种树，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树的特殊类型：

• 满二叉树：每个节点有0个或2个子节点
• 完全二叉树：除了最后一层外，所有层都被完全填充
• 完美二叉树：所有内部节点都有两个子节点，且所有叶子节点都在同一层
• 平衡二叉树：高度为O(log n)，其中n是节点数

二叉树遍历的实现可以是：

1. 递归（使用调用栈）
2. 迭代（使用显式栈）
3. Morris遍历（常数空间）

来源：thinkings/basic-data-structure.md277-305 thinkings/binary-tree-traversal.md5-23

堆

堆是一种特殊的基于树的数据结构，满足堆属性。它通常用于实现优先队列。

堆的属性：

• 在最小堆中，如果P是C的父节点，则P的键值小于或等于C的键值
• 在最大堆中，如果P是C的父节点，则P的键值大于或等于C的键值
• 根节点总是最小堆中的最小元素或最大堆中的最大元素

基本操作：

• 插入：O(log n)
• 提取最小/最大值：O(log n)
• 查找最小/最大值：O(1)
• 堆化：O(n)

堆用于：

• 优先队列
• 调度算法
• Dijkstra等图算法
• 中位数查找算法

来源：thinkings/basic-data-structure.md307-324

二叉搜索树

二叉搜索树（BST）是一种二叉树，具有以下属性：

• 左子树中所有节点的值都小于根节点的值
• 右子树中所有节点的值都大于根节点的值
• 左右子树也都是二叉搜索树

BST操作：

• 搜索：平均情况O(log n)，最坏情况O(n)
• 插入：平均情况O(log n)，最坏情况O(n)
• 删除：平均情况O(log n)，最坏情况O(n)

BST的一个关键特性是，中序遍历会生成一个排序后的值序列。

BST用于：

• 字典
• 集合
• 查找表
• 优先队列

来源：thinkings/basic-data-structure.md330-353

平衡二叉树

平衡二叉树是保持对数高度的二叉树，以确保无论插入顺序如何，操作都具有O(log n)的时间复杂度。

常见的平衡二叉树类型：

• AVL树：左右子树的高度差最大为1
• 红黑树：使用“红”和“黑”节点着色并具有特定属性来维持平衡
• B树和B+树：用于数据库和文件系统

这些树使用旋转操作在插入和删除后维持平衡。

来源：thinkings/basic-data-structure.md356-382

Trie（前缀树）

Trie，也称为前缀树，是一种树状数据结构，用于存储字符串集合，其中共享前缀由共享路径表示。

Trie的属性：

• 根节点不包含字符
• 每个节点包含一个字符（根节点除外）
• 从根到任何节点的每条路径都代表一个前缀
• 一个节点的所有后代共享一个共同的前缀
• 一个节点的子节点包含不同的字符

Trie用于：

• 自动补全/预测文本
• 拼写检查
• IP路由（最长前缀匹配）
• 带通配符的文本搜索

ImmutableJS库使用类似Trie的结构来实现其高效的数据共享。

来源：thinkings/basic-data-structure.md384-408

时间和空间复杂度比较

下表总结了不同数据结构上操作的时间和空间复杂度：

数据结构	访问	搜索	插入	删除	Space键
数组	O(1)	O(n)	O(n)	O(n)	O(n)
栈	O(n)	O(n)	O(1)	O(1)	O(n)
队列	O(n)	O(n)	O(1)	O(1)	O(n)
链表	O(n)	O(n)	O(1)*	O(1)*	O(n)
二叉树	O(n)	O(n)	O(n)	O(n)	O(n)
BST	O(log n)**	O(log n)**	O(log n)**	O(log n)**	O(n)
堆	O(1)***	O(n)	O(log n)	O(log n)	O(n)
Trie树	O(m)	O(m)	O(m)	O(m)	O(n*m)

* 假设位置已知。如果需要搜索，复杂度变为O(n)。
** 平均情况。对于不平衡树，最坏情况是O(n)。
*** 仅用于查找最小/最大元素。
m = Trie操作中键/字符串的长度

此比较有助于根据应用程序中最常执行的操作来选择适当的数据结构。

来源：基于所有引用文件中的信息进行分析。

仓库中的实际应用

本仓库展示了这些数据结构在解决算法问题中的各种实际应用：

1. 数组的双指针技巧

   • 从已排序数组中删除重复项 problems/26.remove-duplicates-from-sorted-array.md
   • 将零移动到数组末尾 problems/283.move-zeroes.md
   • 查找和为目标的两个数字 problems/167.two-sum-ii-input-array-is-sorted.md

2. 栈的应用

   • 实现具有常数时间操作的最小栈 problems/155.min-stack.md
   • 接雨水 problems/42.trapping-rain-water.md

3. 二叉树操作

   • 检查树是否对称 problems/101.symmetric-tree.md
   • 树遍历算法 thinkings/binary-tree-traversal.md

4. 哈希表的使用

   • 检测范围内的重复项 problems/219.contains-duplicate-ii.md
   • 查找数组交集 problems/349.intersection-of-two-arrays.md

5. 链表操作

   • 删除具有特定值的元素 problems/203.remove-linked-list-elements.md

这些例子展示了掌握这些基本数据结构对于高效解决各种算法问题至关重要。

来源：本节中引用的所有问题文件。