什么情况下会使用链表
哪些公司问过
答案要点
- 适合频繁在已知位置插入删除,只改指针O(1)
- 节点按需分配,不需要连续内存和扩容拷贝
- 典型场景:LRU缓存、哈希冲突链、空闲块链表、队列
- 按下标访问O(n),缓存不友好,有指针额外开销
- 随机访问和遍历为主时优先用数组
易错点
- 认为链表任何插入都是O(1),忽略查找位置的O(n)
- 忽略链表的缓存不友好和指针开销
- 随机访问频繁的场景仍选链表
面试官常见追问
- 为什么很多时候vector比list更快?
- 单链表和双链表怎么选?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 链表的几种经典操作247 场
- 判断链表是否有环70 场
- 合并 K 个有序链表45 场
- Y 型链表找第一个相交节点21 场
- 链表反转及其变形20 场
- 链表重排(找中点、反转、合并)20 场
- K 个一组翻转链表17 场
- 删除链表的倒数第 N 个节点15 场
- 链表排序:归并排序与快速排序9 场
- 链表每两个节点翻转8 场