删除O（1）中的双端队列中的哈希节点

Question

我如何在双端队列中对内置节点进行哈希处理（这是一个双链表），并在O（1）的中间位置删除该节点？内置节点是否暴露？

例如，我想将双端队列的节点保存在dict中，以便以后可以在固定时间内删除该节点。

这是LRU中的一个用例，使用双端队列，因此我不需要编写自己的双链表。

from collections import deque

class LRU:
  def __init__(self):
    self.nodes = deque()
    self.key2node = {}

  def insertThenDelete(self):
    # insert
    node = deque.Node('k', 'v') # imagine you can expose deque node here
    self.nodes.appendleft(node) 
    self.key2node = {'k': node} 

    # delete
    self.key2node['k'].deleteInDeque() # HERE shold remove the node in DLL!
    del self.key2node['k']

我知道您可以按索引进行del mydeque[2]删除。但我想通过引用删除key2node['k'].deleteInDeque()。

Answer 1

deque API不支持直接引用内部节点或直接删除内部节点，因此，您尝试使用collections.deque（）无法实现。

此外，双端队列实现是固定长度块的双向链接列表，其中对象指针数组中的块，因此即使您可以获取引用，也无法简便地删除仅一部分块（固定长度）。

您最好的选择是从头开始创建自己的双向链接列表。请参见functools.lru_cache（）的源代码，该源代码完全符合您的描述：https://github.com/python/cpython/blob/3.7/Lib/functools.py#L405

希望这会有所帮助：-）