|
69
|
1 from typing import Optional
|
|
|
2
|
|
|
3
|
|
|
4 class Node:
|
|
|
5 def __init__(self, key, value):
|
|
|
6 self.key = key
|
|
|
7 self.value = value
|
|
|
8 self.next: Optional[Node] = None
|
|
|
9 self.prev: Optional[Node] = None
|
|
|
10
|
|
|
11 class LRUCache:
|
|
|
12
|
|
|
13 def __init__(self, capacity: int):
|
|
|
14 self.capacity = capacity
|
|
|
15 self.map = {}
|
|
|
16 self.head = Node(-1, -1)
|
|
|
17 self.tail = Node(-1, -1)
|
|
|
18 self.head.next, self.tail.prev = self.tail, self.head
|
|
|
19
|
|
|
20 def get(self, key: int) -> int:
|
|
|
21 if not key in self.map:
|
|
|
22 return -1
|
|
|
23 node = self.map[key]
|
|
|
24 self._deleteAndAdd(node)
|
|
|
25 return node.value
|
|
|
26
|
|
|
27 def put(self, key: int, value: int) -> None:
|
|
|
28 newNode = Node(key, value)
|
|
|
29 if key in self.map:
|
|
|
30 self._delete(self.map[key])
|
|
|
31 else:
|
|
|
32 if len(self.map.keys())+1 > self.capacity:
|
|
|
33 del self.map[self.head.next.key]
|
|
|
34 self._delete(self.head.next)
|
|
|
35 self._add(newNode)
|
|
|
36 self.map[key] = newNode
|
|
|
37
|
|
|
38 def _deleteAndAdd(self, node):
|
|
|
39 self._delete(node)
|
|
|
40 self._add(node)
|
|
|
41
|
|
|
42 def _delete(self, node):
|
|
|
43 node.prev.next, node.next.prev = node.next, node.prev
|
|
|
44
|
|
|
45 def _add(self, node):
|
|
|
46 node.prev, node.next, self.tail.prev.next, self.tail.prev = self.tail.prev, self.tail, node, node
|
