LRU Cache

Implement the LRUCache class

class ListNode:
    def __init__(self,key=-1, value=-1, next=None, prev=None):
        self.key = key
        self.value = value
        self.next = next
        self.prev = prev

class LRUCache:
     def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = dict()
        self.head = ListNode()
        self.tail = ListNode()
        self.head.next = self.tail
        self.tail.prev = self.head

     def get(self, key: int) -> int:
        if key not in self.cache: return -1
        
        node = self.cache[key]
        v = node.value
        self.remove(node)
        self.add(node)
        return v

     def put(self, key: int, value: int) -> None:
        if key not in self.cache:
            if len(self.cache) >= self.capacity:
                self.pop_lru()
            self.add(ListNode(key,value))
        else:
            node = self.cache[key]
            node.value = value
            self.remove(node)
            self.add(node)
    
    def add(self, node:ListNode) -> None:
        self.tail.prev.next = node
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev = node
        self.cache[node.key] = node
    
    def remove(self, node: ListNode) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev
        del self.cache[node.key]
    
    def pop_lru(self) -> None:
        self.remove(self.head.next)

Approach2: Inneficient using Queue properties

from collections import deque, namedtuple
class LRUCache:

    def __init__(self, capacity: int):
        self.deq = deque()
        self.size = capacity
        self.Pair = namedtuple('pair', ['key', 'value'])
        
    def get(self, key: int) -> int:
        index = self.find(key)
        if index == -1: return -1
        value = self.deq[index].value
        del self.deq[index]
        self.deq.append(self.Pair(key=key, value=value))
        return value
    
    def put(self, key: int, value: int) -> None:
        index = self.find(key)
        
        if index == -1:
            if len(self.deq) >= self.size:
                del self.deq[0]
        else:
            del self.deq[index]
        self.deq.append(self.Pair(key=key, value=value))
        
    def find(self, key: int) -> int:
        for index, pair in enumerate(self.deq):
            if pair.key == key:
                return index
        return -1