数组和链表的区别与适用场景
哪些公司问过
答案要点
- 数组内存连续,链表节点分散、靠指针连接
- 随机访问:数组 O(1),链表 O(n)
- 插入删除:链表在已知位置时 O(1),数组要移动元素 O(n)(查找位置本身仍是 O(n))
- 缓存与空间:数组缓存友好、没有指针开销;链表缓存不友好、每个节点有指针开销
- 实际场景中 vector 往往优于 list,除非频繁在已知位置的中间增删
易错点
- 只说“链表插入 O(1)、数组 O(n)”,忽略定位节点本身要 O(n)
- 忽略缓存局部性:大 O 相同甚至更差的数组实际更快
- 把数组和动态数组(vector)混为一谈:扩容会拷贝
- 说链表没有额外空间开销:每个节点都有指针
面试官常见追问
- ArrayList 和 LinkedList 有什么区别?
- 为什么链表插入是 O(1),实际却不一定快?
- 数组扩容是怎么做的?
- 什么场景适合用链表?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 经典算法题:最长回文子串、无重复最长子串、最大子数组和141 场
- 合并有序数组与合并区间66 场
- 三数之和:排序加双指针50 场
- 字符串相加(大数加法)20 场
- 字符串匹配:KMP 算法18 场
- 字符串反转的实现与注意事项17 场
- 接雨水问题的三种解法14 场
- 螺旋矩阵遍历14 场
- 两数之和的几种解法12 场
- 实现 atoi:字符串转整数11 场