删除O（1）中deque中的散列节点

Question

如何散列deque中的内置节点（这是一个双链表）并删除O（1）中中间的节点？内置节点是否公开？你知道吗

例如，我想在dict中保存一个deque的节点，以便以后可以在固定时间内删除该节点。你知道吗

这是LRU中的一个用例，使用deque，所以我不需要编写自己的双链接列表。你知道吗

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

dequeAPI不支持直接引用内部节点或直接删除内部节点，因此使用收藏.deque（）。你知道吗

此外，deque实现是一个固定长度块的双链表，其中一个块位于一个对象指针数组中，因此即使您可以获得一个引用，也没有简单的方法来删除一个块的一部分（它是固定长度的）。你知道吗

最好的办法是从头开始创建自己的双链接列表。有关详细信息，请参阅源代码functools.lru\u缓存（）与您描述的完全一致：https://github.com/python/cpython/blob/3.7/Lib/functools.py#L405

希望这有帮助：-）