python - 在 O(1) 中删除 deque 中的散列节点

Question

如何散列 deque 中的内置节点(这是一个双链表)并删除 O(1) 中间的节点？内置节点是否暴露？

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

这是 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

deque API 不支持直接引用内部节点或直接删除内部节点，因此 collections.deque() 无法实现您的操作。

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

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

希望这可以帮助 :-)