双向链表与哈希表协同实现有序映射：链表维护插入/访问顺序，哈希表提供o(1)键查找；哨兵节点简化操作，节点含key、value、prev、next，结构体持head/tail及哈希表。

用双向链表实现自定义有序映射，核心是把“键值对的顺序性”和“快速查找能力”结合起来——单靠链表查得慢，单靠哈希表没顺序，所以必须两者协同。

用双向链表维护插入顺序

每个节点存一个键值对（如 key、value），并带两个指针：prev 指向前一个节点，next 指向后一个节点。新元素总追加到链表尾部，这样遍历时自然按插入顺序输出。头尾各设哨兵节点（dummy head/tail），避免空指针判断，简化插入删除逻辑。

• 插入时：新建节点 → 接到 tail 前面 → 更新 tail->prev 和新节点的前后指针
• 删除时：跳过目标节点，重连其前后节点的指针 → 释放该节点内存
• 遍历只需从 head->next 开始，一路 next 到 tail->prev，无需额外排序

用哈希表加速键查找

光有链表还不够：按 key 查 value 或删 key 时，遍历链表是 O(n)。所以必须配一个哈希表（比如 C 的 uthash 或 Python 的 dict），把 key 映射到对应链表节点的地址。

JavaStoryDevelop

你接手一个需求时，是不是经常这样："改一个小字段 → 结果把不相关的代码也改了"、"需求说得很模糊 → 做着做着发现跑偏了"、"数据库加个字段 → 上线才发现漏了数据兼容"、"做了个新功能 → 一个月后自己都忘了当时怎么设计的"、"写到一半被中断 → 再回来不知道从哪继续"；这个 Skill 就是专门解决这些问题的。 它会自动探测你的项目环境（JDK、Spring Boot、ORM、数据库、前端框架），记在

下载

• put(key, value)：先查哈希表是否存在；若存在，更新 value 并保持链表位置（或按需移到尾部）；若不存在，新建节点插入链表尾，并把 key→节点指针存入哈希表
• get(key)：直接查哈希表拿到节点，取 value 即可，O(1) 平均时间
• remove(key)：哈希表查出节点 → 链表中摘除 → 从哈希表中删 key

支持访问顺序（可选 LRU 行为）

如果需要“最近访问的排最后”（比如缓存淘汰），可在 get 操作时把对应节点从原位置摘下，再插到链表尾部。这就要求链表支持任意节点的快速摘除和尾部插入——双向链表天然支持，只要保存好节点的 prev/next，就能 O(1) 完成。

• 启用 accessOrder 后，每次 get 都触发一次“移尾”操作
• 淘汰策略就简单了：删 head->next（最久未用）即可
• 注意：哈希表里 key→节点的映射始终有效，不随位置变化而失效

节点与结构体设计要点

节点结构至少包含 key、value、prev、next 四个字段；整个映射结构体要持有 head、tail 哨兵指针，以及哈希表句柄（或指针数组+哈希函数）。

• C 语言中常用 struct + void* 泛型字段，或模板化宏处理不同类型 key/value
• key 必须可哈希且可比较（用于哈希冲突处理和去重）
• 内存管理要一致：节点 malloc 后，必须在 remove 或 destroy 时 free，哈希表也要同步清理