удалить хешированный узел в deque в O (1) - PullRequest
Новая
       5

удалить хешированный узел в deque в O (1)

0 голосов
/ 24 июня 2018

Как мне хэшировать встроенный узел в deque (который является двойным связанным списком) и удалять узел посередине в O (1)?Открыт ли встроенный узел?

Например, я хочу сохранить узел deque в 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() удалить по ссылке.

...