面试题：设计支持O(1)时间CRUD且维护插入顺序的数据结构

适用的数据结构是**哈希表（Hash Table）+ 双向链表（Doubly Linked List）**的组合，这也是Java LinkedHashMap、Python OrderedDict（3.7+后普通dict也具备类似特性，底层逻辑相通）的核心实现思路。

结构组成 #

• 哈希表：负责以O(1)速度定位元素，存储「键」到「双向链表节点」的映射，每个节点包含键、值，以及前驱、后继两个指针。
• 双向链表：按元素插入顺序串联所有节点，维护表头（第一个插入元素）和表尾（最后插入元素）指针，保证顺序遍历的效率。

各操作O(1)复杂度的实现原理 #

Insert（插入） #

1. 借助哈希表的键查找，O(1)时间判断键是否已存在。
2. 若不存在，创建新的双向链表节点，通过表尾指针直接将节点追加到链表尾部（仅需更新表尾节点的后继指针和新节点的前驱指针，O(1)操作）。
3. 在哈希表中存入键与新节点的映射，O(1)完成。

Update（更新） #

1. 通过哈希表直接定位到目标节点，O(1)时间。
2. 直接修改节点存储的值即可；如果业务要求更新后将元素移到顺序末尾（比如最近访问优先），也可通过双向链表的O(1)删除+尾部插入完成。

Remove（删除） #

1. 哈希表定位目标节点，O(1)时间。
2. 利用节点的前驱、后继指针，跳过当前节点修改链表指针（无需遍历链表），O(1)完成节点移除。
3. 从哈希表中删除对应键的映射，O(1)完成。

Contains（存在性检查） #

直接通过哈希表的键查询功能判断，O(1)时间得出结果。

按插入顺序打印元素（O(n)时间） #

从双向链表的表头节点开始，逐个遍历到表尾，每个节点仅访问一次，总时间复杂度为O(n)。

内容的提问来源于stack exchange，提问作者umesh