delete the hashed node in deque in O(1)

Question

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.

What is `deque` here? The class by that name in the built-in collections module does not have a `Node` attribute. — Daniel Roseman, Jun 24 '18 at 18:47
For that matter, the built-in deque class doesn't even have per-item nodes at all. If you're hoping to use `collections.deque`, give up and use something else. — user2357112, Jun 24 '18 at 18:50
`collections.deque` is double linked list based (https://stackoverflow.com/a/6257048/3023116), so you cannot have O(1) deletions from the middle. — taras, Jun 24 '18 at 18:50
@taras: You could if the list wasn't unrolled and it exposed node references, but neither of those things are the case. — user2357112, Jun 24 '18 at 18:51
@user2357112, I didn't know it. Thank you for pointing it out! — taras, Jun 24 '18 at 18:55
Updated. deque.Node() is just to imagine you can expose the built-in node, to explain my idea. (I tried my best to explain. Hope it is ok.) — Denly, Jun 24 '18 at 21:03

score 7 · Accepted Answer · answered Oct 07 '19 at 03:51

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 :-)

delete the hashed node in deque in O(1)

1 Answers1