常见数据结构的特点、复杂度与适用场景
哪些公司问过
答案要点
- 数组连续存储,随机访问 O(1),中间插入删除 O(n),缓存友好
- 链表已知位置插入删除 O(1),随机访问 O(n),额外指针开销
- 栈后进先出,队列先进先出,可基于数组或链表实现
- 哈希表平均增删查 O(1)、最坏 O(n),无序
- 红黑树增删查 O(log n),有序,支持范围查询
易错点
- 说链表插入删除是 O(1) 时忽略需先找到位置
- 以为哈希表最坏情况也是 O(1)
- 只背复杂度不讲适用场景
面试官常见追问
- 为什么数组遍历通常比链表快?
- 哈希表和红黑树怎么选?
- 红黑树和 AVL 树有什么区别?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。