数据结构 cheatsheet

1. 数组

- 定义：由相同数据类型的元素组成的有限集合。
- 时间复杂度：随机访问 O(1)，插入 O(n)，删除 O(n)。
- 适用场景：数据量较小且需要随机访问的情况。

2. 链表

- 定义：由节点组成的线性数据结构，每个节点包含数据和指向下一个节点的指针。
- 时间复杂度：访问 O(n)，插入 O(1)，删除 O(1)。
- 适用场景：频繁插入和删除元素的情况，不需要随机访问。

3. 栈

- 定义：一种特殊的线性数据结构，遵循先进后出的原则。
- 时间复杂度：插入 O(1)，删除 O(1)。
- 适用场景：需要后进先出的情况，如表达式求值、函数调用等。

4. 队列

- 定义：一种线性数据结构，遵循先进先出的原则。
- 时间复杂度：插入 O(1)，删除 O(1)。
- 适用场景：需要先进先出的情况，如消息队列、缓存等。

5. 树

- 定义：由节点组成的非线性数据结构，每个节点包含数据和指向子节点的指针。
- 时间复杂度：搜索 O(log n)，插入 O(log n)，删除 O(log n)。
- 适用场景：需要高效搜索和插入的情况，如数据库索引、算法中的分治思想等。

6. 图

- 定义：由节点和边组成的非线性数据结构，节点表示对象，边表示它们之间的关系。
- 时间复杂度：搜索 O(n + m)，插入 O(1)，删除 O(n + m)。
- 适用场景：需要处理对象之间关系的情况，如社交网络、路由算法等。

7. 哈希表

- 定义：一种基于哈希函数实现的数据结构，将键映射到值，可以快速访问、插入和删除元素。
- 时间复杂度：访问 O(1)，插入 O(1)，删除 O(1)。
- 适用场景：需要快速查找和插入的情况，如缓存、字典等。

8. 堆

- 定义：一种完全二叉树的结构，满足堆属性，即父节点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
- 时间复杂度：插入 O(log n)，删除 O(log n)。
- 适用场景：需要维护一组元素中的最大或最小值的情况，如堆排序、优先队列等。

9. 字符串

- 定义：由字符组成的有限序列。
- 时间复杂度：搜索 O(n)，插入 O(n)，删除 O(n)。
- 适用场景：需要处理文本的情况，如搜索引擎、文本编辑器等。

10. 树状数组

- 定义：一种用于高效维护数列前缀和的数据结构。
- 时间复杂度：查询 O(log n)，修改 O(log n)。
- 适用场景：需要高效查询数列前缀和的情况，如求逆序对、求区间和等。