数组与链表 list 的区别
哪些公司问过
答案要点
- 数组内存连续、按下标 O(1) 随机访问,缓存友好
- 数组中间插入删除需要移动元素,复杂度 O(n)
- 链表节点不连续,按位置访问 O(n),已知位置插删 O(1)
- 链表每个节点额外存指针,内存开销大,缓存局部性差
- Python 的 list 是动态数组,C++ 的 std::list 才是双向链表
易错点
- 只看大 O 认为链表插删一定比数组快,忽略了查找位置的 O(n) 和缓存失效
- 把 Python 的 list 当成链表
- 忽略链表节点指针带来的额外内存开销
面试官常见追问
- vector 和 list 怎么选?
- 动态数组扩容是怎么做的?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。