数据结构总结
| 访问 | 搜索 | 插入 | 删除 | 特点 | |
|---|---|---|---|---|---|
| 数组 | O(1) | O(N) | O(N) | O(N) | 读多写少 |
| 链表 | O(N) | O(N) | O(1) | O(1) | 写多读少 |
| 队列 | O(N) | O(N) | O(1) | O(1) | 先入先出 |
| 栈 | O(1)（访问栈顶元素） | O(N) | O(1) | O(1) | 先入后出 |
| 哈希表 | 不存在 | O(1)（碰撞为O(k)k为碰撞元素个数） | O(1) | O(1) | 哈希碰撞（通过哈希函数指向同一个地址） |
| 集合 | 不存在 | 无冲突：O(1) 有冲突：O(k) | 无冲突：O(1) 有冲突：O(k) | 无冲突：O(1) 有冲突：O(k) | 检查元素是否存在，检查重复元素 |
| 堆 | 不存在 | O(1)（只看堆顶元素） | O(logN) | O(logN) | 最大堆和最小堆 |
