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
– Daniel Roseman, Commented Jun 24, 2018 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
– user2357112, Commented Jun 24, 2018 at 18:50
collections.deque is double linked list based (stackoverflow.com/a/6257048/3023116), so you cannot have O(1) deletions from the middle. — taras
– taras, Commented Jun 24, 2018 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
– user2357112, Commented Jun 24, 2018 at 18:51
@user2357112, I didn't know it. Thank you for pointing it out! — taras
– taras, Commented Jun 24, 2018 at 18:55

Raymond Hettinger · Accepted Answer · 2019-10-07 03:51:51Z

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

Collectives™ on Stack Overflow

delete the hashed node in deque in O(1)

1 Answer 1

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Linked

Related