| 6 | |
| 7 | |
| 8 | class LRUCache: |
| 9 | def __init__(self, capacity: int): |
| 10 | self.capacity = capacity |
| 11 | # A hash map that maps keys to nodes. |
| 12 | self.hashmap = {} |
| 13 | # Initialize the head and tail dummy nodes and connect them to |
| 14 | # each other to establish a basic two-node doubly linked list. |
| 15 | self.head = DoublyLinkedListNode(-1, -1) |
| 16 | self.tail = DoublyLinkedListNode(-1, -1) |
| 17 | self.head.next = self.tail |
| 18 | self.tail.prev = self.head |
| 19 | |
| 20 | def get(self, key: int) -> int: |
| 21 | if key not in self.hashmap: |
| 22 | return -1 |
| 23 | # To make this key the most recently used, remove its node and |
| 24 | # re-add it to the tail of the linked list. |
| 25 | self.remove_node(self.hashmap[key]) |
| 26 | self.add_to_tail(self.hashmap[key]) |
| 27 | return self.hashmap[key].val |
| 28 | |
| 29 | def put(self, key: int, value: int) -> None: |
| 30 | # If a node with this key already exists, remove it from the |
| 31 | # linked list. |
| 32 | if key in self.hashmap: |
| 33 | self.remove_node(self.hashmap[key]) |
| 34 | node = DoublyLinkedListNode(key, value) |
| 35 | self.hashmap[key] = node |
| 36 | # Remove the least recently used node from the cache if adding |
| 37 | # this new node will result in an overflow. |
| 38 | if len(self.hashmap) > self.capacity: |
| 39 | del self.hashmap[self.head.next.key] |
| 40 | self.remove_node(self.head.next) |
| 41 | self.add_to_tail(node) |
| 42 | |
| 43 | def add_to_tail(self, node: DoublyLinkedListNode) -> None: |
| 44 | prev_node = self.tail.prev |
| 45 | node.prev = prev_node |
| 46 | node.next = self.tail |
| 47 | prev_node.next = node |
| 48 | self.tail.prev = node |
| 49 | |
| 50 | def remove_node(self, node: DoublyLinkedListNode) -> None: |
| 51 | node.prev.next = node.next |
| 52 | node.next.prev = node.prev |
nothing calls this directly
no outgoing calls
no test coverage detected