数据结构/权衡
< 数据结构
在选择数据结构之前，全面理解需要解决的问题非常重要，因为每个结构都针对特定任务进行了优化。例如，哈希表优先考虑快速查找时间而不是内存使用，而数组则紧凑且不灵活。其他结构，如堆栈，则优化为在整个程序执行过程中对数据添加、删除和访问方式实施严格的规则。对数据结构的良好理解是基础，因为它为我们提供了以结构化方式思考程序行为的工具。
[TODO:] Use asymptotic behaviour to decide, most importantly seeing how the structure will be used: an infrequent operation does not need to be fast if it means everything else will be much faster
[TODO:] Can use a table like this one to compare the asymptotic behaviour of every structure for every operation on it.
| 数组 | 动态数组 | 数组双端队列 | 单链表 | 双链表 | |
|---|---|---|---|---|---|
| 推入（前端） | - | O(n) | O(1) | O(1) | O(1) |
| 弹出（前端） | - | O(n) | O(1) | O(1) | O(1) |
| 推入（后端） | - | O(1) | O(1) | O(n)，可能为 O(1)* | O(1) |
| 弹出（后端） | - | O(1) | O(1) | O(n) | O(1) |
| 在（给定迭代器）之前插入 | - | O(n) | O(n) | O(n) | O(1) |
| 删除（给定迭代器） | O(n) | O(n) | O(n) | O(1) | |
| 在（给定迭代器）之后插入 | O(n) | O(n) | O(1) | O(1) | |
| 在（给定迭代器）之后删除 | - | O(n) | O(n) | O(1) | O(1) |
| 获取第 n 个元素（随机访问） | O(1) | O(1) | O(1) | O(n) | O(n) |
| 适合实现堆栈 | 否 | 是（后端为顶部） | 是 | 是（前端为顶部） | 是 |
| 适合实现队列 | 否 | 否 | 是 | 可能* | 是 |
| C++ STL | std::array
|
std::vector
|
std::deque
|
std::forward_list
|
std::list
|
| Java 集合 | java.util.Array
|
java.util.ArrayList
|
java.util.ArrayDeque
|
- | java.util.LinkedList
|
* singly-linked lists can push to the back in O(1) with the modification that you keep a pointer to the last node
| 排序数组 | 排序链表 | 自平衡二叉搜索树 | 哈希表 | |
|---|---|---|---|---|
| 查找键 | O(log n) | O(n) | O(log n) | 平均 O(1) 最差 O(n) |
| 插入元素 | O(n) | O(n) | O(log n) | 平均 O(1) 最差 O(n) |
| 删除键 | O(n) | O(n) | O(log n) | 平均 O(1) 最差 O(n) |
| 删除元素（给定迭代器） | O(n) | O(1) | O(1) | O(1) |
| 可以按排序顺序遍历吗？ | 是 | 是 | 是 | 否 |
| 需要 | 比较函数 | 比较函数 | 比较函数 | 哈希函数 |
| C++ STL | - | - | std::setstd::mapstd::multiset
|
std::unordered_setstd::unordered_mapstd::unordered_multiset
|
| Java 集合 | - | - | java.util.TreeSet
|
java.util.HashSet
|
- 请更正任何错误
| 二分搜索 | AVL 树 | 二叉堆（最小堆） | 二项队列（最小堆） | |
|---|---|---|---|---|
| 插入元素 | O(log n) | O(log n) | O(log n) | O(1)（平均） |
| 删除元素 | O(log n) | O(log n) | 不可用 | 不可用 |
| 删除最小元素 | O(log n) | O(log n) | O(log n) | O(log n) |
| 查找最小元素 | O(log n) | O(log n) | O(1) | O(log n)（如果指向最小值的指针则可以为 O(1)） |
| 增加键 | 不可用 | 不可用 | O(log n) | O(log n) |
| 减少键 | 不可用 | 不可用 | O(log n) | O(log n) |
| 查找 | O(log n) | O(log n) | 不可用 | 不可用 |
| 删除元素 | O(log n) | O(log n) | 不可用 | 不可用 |
| 创建 | O(1) | O(1) | O(1) | O(1) |
| 查找第 k 小的元素 | O(log n) | O(log n) | O((k-1)*log n) | O(k*log n) |
| 哈希表（哈希映射） | |
|---|---|
| 设置值 | Ω(1)，O(n) |
| 获取值 | Ω(1)，O(n) |
| 删除 | Ω(1)，O(n) |
[TODO:] Can also add a table that specifies the best structure for some specific need e.g. For queues, double linked. For stacks, single linked. For sets, hash tables. etc...
[TODO:] Could also contain table with space complexity information (there is a significative cost in using hashtables or lists implemented via arrays, for example).