本文全面概述了编码面试中必不可少的基本数据结构。数据结构是组织和存储数据的特定方式，能够实现高效操作。理解数据结构对于编写高效代码和在Google、Amazon、Microsoft等公司的技术面试中取得成功都至关重要。
有关与这些数据结构配对的算法复杂度分析，请参阅算法复杂度 / 大O表示法 / 渐近分析。
有关利用这些数据结构的算法，请参阅算法。
数据结构是高效算法的基石。为特定问题选择正确的数据结构可以显著提高性能并简化代码。
数组是最基本的数据结构，由存储在连续内存位置的元素组成。
| 操作 | 时间复杂度 | 注意 |
|---|---|---|
| 访问 | O(1) | 直接索引访问 |
| 搜索（未排序） | O(n) | 线性搜索 |
| 搜索（已排序） | O(log n) | 二分查找 |
| 在末尾插入（分摊） | O(1) | 使用动态数组时 |
| 在任意位置插入 | O(n) | 需要移动元素 |
| 在末尾删除 | O(1) | 无需移动 |
| 在任意位置删除 | O(n) | 需要移动元素 |
动态数组（如 Java 中的 ArrayList 或 C++ 中的 vector）在达到容量时会自动调整大小，通常会将其大小加倍。
size() - 项目数量capacity() - 最大项目数量is_empty()at(index) - 返回给定索引处的项目push(item) - 在末尾添加项目insert(index, item) - 在索引处插入，并移动后面的元素prepend(item) - 在开头插入pop() - 移除并返回最后一个项目delete(index) - 移除索引处的项目remove(item) - 如果找到则移除项目find(item) - 返回项目的第一个索引resize(new_capacity) - 调整数组大小的私有函数链表是线性数据结构，元素存储在节点中，每个节点包含数据和指向下一个节点的引用。
| 操作 | 时间复杂度 | 注意 |
|---|---|---|
| 访问 | O(n) | 必须从头节点遍历 |
| 搜索 | O(n) | 线性遍历 |
| 在开头插入 | O(1) | 更改头节点引用 |
| 在末尾插入 | O(1) | 带有尾指针 |
| 在指定位置插入 | O(n) | 必须遍历到指定位置 |
| 在开头删除 | O(1) | 更改头节点引用 |
| 在末尾删除 | O(n) 或 O(1) | 使用双向链表时为 O(1) |
| 在指定位置删除 | O(n) | 必须遍历到指定位置 |
链表的优点
链表的缺点
链表实现应包括以下操作：
size() - 返回数据元素的数量empty() - 如果为空则返回 truevalue_at(index) - 返回第 n 个位置的值push_front(value) - 添加到开头pop_front() - 移除开头项目push_back(value) - 添加到末尾pop_back() - 移除末尾项目front() - 获取开头项目的值back() - 获取末尾项目的值insert(index, value) - 在索引处插入值erase(index) - 移除索引处的节点value_n_from_end(n) - 返回从末尾算起第 n 个位置的节点值reverse() - 反转列表remove_value(value) - 移除值的首次出现栈是一种遵循后进先出（LIFO）原则的线性数据结构。
| 操作 | 时间复杂度 |
|---|---|
| 推送 | O(1) |
| 弹栈（Pop） | O(1) |
| 查看栈顶/栈顶（Peek/Top） | O(1) |
| 搜索 | O(n) |
| 判断是否为空（IsEmpty） | O(1) |
队列是一种遵循先进先出（FIFO）原则的线性数据结构。
| 操作 | 时间复杂度 |
|---|---|
| 入队（Enqueue） | O(1) |
| 出队（Dequeue） | O(1) |
| 队头（Front） | O(1) |
| 队尾（Rear） | O(1) |
| 判断是否为空（IsEmpty） | O(1) |
循环缓冲区通过在元素出队后重用数组元素来优化空间。
enqueue(value) - 在队尾添加值dequeue() - 返回值并移除最近添加的元素empty()enqueue(value) - 在末尾添加项目dequeue() - 返回值并移除最近添加的元素empty()full()哈希表（也称为哈希映射）是一种实现关联数组的数据结构，它将键映射到值。
| 操作 | 平均时间 | 最坏时间 |
|---|---|---|
| 插入 | O(1) | O(n) |
| 删除 | O(1) | O(n) |
| 搜索 | O(1) | O(n) |
一个好的哈希函数应该
hash(k, m) - m 是哈希表的大小add(key, value) - 如果键存在，则更新值exists(key)get(key)remove(key)虽然树将在单独的章节中详细介绍，但它们是值得在此提及的基本数据结构。
一种二叉树，其中
一种专门的基于树的数据结构
一种用于存储字符串的类树数据结构
有关树的更多详细信息，请参阅学习计划的树部分。
图是由节点（顶点）和连接这些节点的边组成的非线性数据结构。
表示图的两种常用方式
邻接矩阵:
matrix[i][j] = 1邻接表:
有关图的更多详细信息，请参阅学习计划的图部分。
了解数据结构操作的时间和空间复杂度对于技术面试至关重要。
| 数据结构 | 访问 | 搜索 | 插入 | 删除 | Space键 |
|---|---|---|---|---|---|
| 数组 | O(1) | O(n) | O(n) | O(n) | O(n) |
| 动态数组 | O(1) | O(n) | O(1)/O(n)* | O(1)/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(1) | O(1) | O(n) |
| 哈希表 | 不适用 | O(1)*** | O(1)*** | O(1)*** | O(n) |
| 二叉搜索树 | 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) |
*末尾操作为均摊时间，任意位置为最坏情况
**当位置已知时（例如，在头/尾部）
***平均情况，最坏情况为 O(n)
****平衡树，非平衡树的最坏情况为 O(n)
†仅限最大/最小元素
来源：README.md627-632 README.md642-647 README.md689-693
在编程面试中，你通常需要从头开始实现数据结构或理解其底层原理。
来源：README.md518-532 README.md602-694
不同的问题需要不同的数据结构。以下是一些常见模式：
| 问题类型 | 推荐数据结构 |
|---|---|
| 按键快速查找 | 哈希表 |
| 先进先出处理 | 队列 |
| 后进先出处理 | 栈 |
| 频繁插入/删除的有序数据 | 平衡二叉搜索树 |
| 字符串前缀匹配 | Trie树 |
| 动态连通性 | 并查集 |
| 图遍历 | 邻接表/矩阵 |
| 优先级调度 | 堆 |
| 维护带插入的排序数据 | 二叉搜索树或堆 |
| 缓存 | 哈希表 + 链表（LRU 缓存） |
掌握基本数据结构对于编程面试至关重要。理解何时以及如何使用每种数据结构，以及它们各自的权衡，将帮助你高效解决问题。
练习从头开始实现这些结构，并解决利用它们的问题。请记住，面试问题通常会结合多种数据结构来解决复杂问题。
如需更多练习，请参阅学习计划的编码问题练习部分。