Skip to content
Advertisement

delete the hashed node in deque in O(1)

How do I hash a built-in node in deque (which is a double linked list) and delete the node in the middle in O(1)? Is the built-in node exposed?

For example, I want to save a deque’s node in dict so I can delete the node in constant time later.

This is a use case in LRU, using deque so I don’t need to write my own double linked list.

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']

I know you can do del mydeque[2] to delete by index. but I want to do key2node['k'].deleteInDeque() delete by referance.

Advertisement

Answer

The deque API doesn’t support direct reference to internal nodes or direct deletion of internal nodes, so what you’re trying to do isn’t possible with collections.deque().

In addition, the deque implementation is a doubly-linked list of fixed-length blocks where a block in a array of object pointers, so even if you could get a reference, there would be no easy way to delete just part of a block (it is fixed length).

Your best bet is to create your own doubly-linked list from scratch. See the source code for functools.lru_cache() which does exactly what you’re describing: https://github.com/python/cpython/blob/3.7/Lib/functools.py#L405

Hope this helps :-)

Advertisement