链表的结构、特点与应用
哪些公司问过
答案要点
- 链表由节点组成,节点含数据域和指针域,通过指针串联成线性结构
- 节点在内存中不连续,按需动态分配,无需预先确定容量
- 已知位置插入删除 O(1),按下标访问需遍历 O(n),缓存局部性差
- 常见类型有单链表、双向链表、循环链表,各有适用场景
- 典型应用:LRU 缓存、哈希冲突拉链法、内核侵入式链表、队列实现
易错点
- 笼统说链表插入删除是 O(1),忽略了先找到位置需要 O(n)
- 忽视链表的指针额外内存和缓存不友好,以为链表总比数组快
- 操作指针时顺序错误导致断链,或忘记处理头节点和空链表
面试官常见追问
- 链表有哪些应用?
- 什么场景选数组,什么场景选链表?
- 怎么判断链表有没有环?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 链表的几种经典操作247 场
- 判断链表是否有环70 场
- 合并 K 个有序链表45 场
- Y 型链表找第一个相交节点21 场
- 链表反转及其变形20 场
- 链表重排(找中点、反转、合并)20 场
- K 个一组翻转链表17 场
- 删除链表的倒数第 N 个节点15 场
- 链表排序:归并排序与快速排序9 场
- 链表每两个节点翻转8 场