LRU Cache设计为O(1)复杂度 为何存在O(N)操作仍被视为常数时间？

你对时间复杂度的判断规则理解完全正确：你当前写出的这版LRU Cache实现，put操作的最坏时间复杂度确实是O(N)，但这个问题来自实现缺陷，并非标准LRU Cache本身的时间复杂度为O(N)。

你代码中标记的localList.remove(key)操作之所以是O(N)，是因为你使用的链表结构要删除指定key的节点，必须从头遍历逐个匹配key才能定位到待删除节点，这个遍历过程没有任何优化空间，自然是O(N)复杂度。按照单操作时间复杂度取最坏情况的规则，你这版实现的put操作复杂度就是O(N)。

标准LRU Cache能做到get、put全操作O(1)，核心是你漏掉了两个关键设计点：

• 不能使用普通单链表、或者仅支持按位置/按值遍历删除的链表，必须使用双向链表，每个节点同时存储key、value、前驱节点指针、后继节点指针。当你已经拿到节点的引用时，删除节点只需要修改前后节点的指针指向，不需要遍历，时间复杂度O(1)。
• HashMap不能只存储key到value的映射，必须存储key到对应双向链表节点的引用，不需要遍历链表就能直接定位到要操作的节点位置。

针对你代码中O(N)的已存在key更新分支，正确的O(1)写法逻辑如下：

} else {
    // 直接通过HashMap拿到key对应的链表节点引用，O(1)
    ListNode targetNode = localCache.get(key);
    targetNode.value = value;
    // 已知节点引用，双向链表删除仅需修改前后指针，O(1)
    removeLinkedListNode(targetNode);
    // 将节点插入链表头部，标记为最近使用，O(1)
    addNodeToHead(targetNode);
}

缓存容量满了之后的淘汰逻辑也同理：直接通过双向链表拿到尾节点（最久未使用的节点），O(1)时间完成链表删除，同时取出尾节点中存储的key，删掉HashMap中对应的条目即可，全程不存在任何遍历链表的操作。

简单说，你当前的版本属于没有按照LRU的最优设计实现，才会出现O(N)的操作，补全上述两个设计点之后，所有操作的时间复杂度就都能达到O(1)。

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