链表检索时间复杂度为O(n)，因其节点内存不连续、无索引，查找key必须从头逐个比对，最坏遍历全部节点，开销随数据量线性增长；即使仅10个键值对，平均也需查5次。
链表在小型缓存中做简单键值对检索，时间复杂度天然就是 O(n)，不适合高频、低延迟场景，但对资源极受限或访问频次很低的嵌入式小缓存，它有不可替代的轻量优势。
为什么链表检索是 O(n)
链表节点在内存中非连续分布，没有索引能力。要查一个 key，必须从头开始逐个比对节点中的 key 字段，最坏情况遍历全部节点。即使只存 10 个键值对，平均也要查 5 次；存 50 个，平均就要查 25 次——这个开销随数据量线性增长，无法规避。
小型缓存里用链表的合理场景
不是“能用”，而是“值得用”：当满足以下多个条件时，单链表反而比哈希表更合适：
- 缓存容量固定且很小（比如 ≤ 16 项），O(n) 查找实际耗时可忽略（纳秒级）
- 硬件资源紧张，无法支持哈希函数计算或额外哈希桶内存（如裸机 MCU、无 malloc 环境）
- 写远少于读，且插入/删除不频繁（例如仅初始化加载一次，后续只读）
- 代码体积敏感，链表实现只需几十行 C，而安全哈希表往往需几百行甚至依赖库
怎么让链表检索更实用一点
不做大改动，仅靠小技巧就能提升体验：
- 访问局部性优化：把最近查过的节点移到链表头部（类似微型 LRU），下次再查同 key 就大概率在前几位
- 有序链表 + 早停：若 key 可排序（如整型 ID），维持链表按 key 升序，查到比目标大的 key 就终止，减少无效遍历
- 哨兵节点：头结点不存真实数据，简化空链表和首节点操作逻辑，降低出错概率
- 静态数组模拟链表：用固定大小结构体数组 + next_index 字段代替指针，在无堆环境更可控、无内存碎片
链表不是过时技术，它在小型缓存里不是妥协，而是精准匹配约束的选择。关键不在“快”，而在“稳、省、可控”。
