面试题库 › C++ / 后端 › 如何让链表查找达到O(1)

如何让链表查找达到O(1)

难度 ★★☆在 1 场真实面经中被问到 方向:C++ / 后端考点:哈希表

哪些公司问过

大华1

常见岗位:嵌入式软件

答案要点

  1. 链表不支持随机访问,按值查找只能顺序遍历,时间O(n)
  2. 哈希表存key到节点指针的映射,查找平均O(1),链表负责维护顺序
  3. 用双向链表,拿到节点后可O(1)删除,无需遍历找前驱
  4. 典型应用是LRU缓存,get/put均为O(1);Java的LinkedHashMap即此结构
  5. 代价是额外空间,且O(1)是平均复杂度,哈希冲突严重时会退化

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题