# LeetCode 146. LRU Cache

## Description

https://leetcode.com/problems/lru-cache/

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: `get` and `put`.

`get(key)` – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
`put(key, value)` – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Could you do both operations in O(1) time complexity?

Example:

```LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.put(4, 4);    // evicts key 1
cache.get(3);       // returns 3
cache.get(4);       // returns 4
```

## Explanation

We can use a doubly linked list and hashmap together. Everytime we save a new key value pair, we put the key into the map and create a linked list node as its value. Globally, the linked list shows the order of keys. The list node next to the head is the most recently used key, the list node next to the tail is the least recently used key.

## Python Solution

``````class ListNode:

def __init__(self, key, value):
self.key = key
self.value = value
self.next = None
self.prev = None

class LRUCache:

def __init__(self, capacity: int):
self.capacity = capacity

self.cache = {}

self.tail = ListNode(-1, -1)

def get(self, key: int) -> int:

if key not in self.cache:
return -1

node = self.cache[key]
self.remove_node(node)

return node.value

def put(self, key: int, value: int) -> None:

if key in self.cache:
node = self.cache[key]
node.value = value

self.remove_node(node)

self.cache[key] = node
else:
new_node = ListNode(key, value)
self.cache[key] = new_node

if len(self.cache) > self.capacity:
last_node = self.tail.prev
self.tail.prev = last_node.prev
last_node.prev.next = self.tail

del self.cache[last_node.key]
self.remove_node(last_node)

def remove_node(self, node):
node.prev.next = node.next
node.next.prev = node.prev