在 O(1) 中删除双端队列中的散列节点

Question

如何在deque（双链表）中散列一个内置节点并在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().

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

最好的办法是从头开始创建自己的双向链表。请参阅 functools.lru_cache() 的源代码，它完全符合您的描述：https://github.com/python/cpython/blob/3.7/Lib/functools.py#L405

希望这对您有所帮助:-)

在 O(1) 中删除双端队列中的散列节点

delete the hashed node in deque in O(1)

python

deque

python-internals