# LRU Cache

Design a data structure that follows the constraints of a **Least Recently Used (LRU) cache**.

Implement the `LRUCache`

class:

`LRUCache(int capacity)`

Initialize the LRU cache with**positive**size`capacity`

.`int get(int key)`

Return the value of the`key`

if the key exists, otherwise return`-1`

.`void put(int key, int value)`

Update the value of the`key`

if the`key`

exists. Otherwise, add the`key-value`

pair to the cache. If the number of keys exceeds the`capacity`

from this operation,**evict**the least recently used key.

**Example 1:**

Input

["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]

[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]Output

[null, null, null, 1, null, -1, null, -1, 3, 4]Explanation

LRUCache lRUCache = new LRUCache(2);

lRUCache.put(1, 1); // cache is {1=1}

lRUCache.put(2, 2); // cache is {1=1, 2=2}

lRUCache.get(1); // return 1

lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}

lRUCache.get(2); // returns -1 (not found)

lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}

lRUCache.get(1); // return -1 (not found)

lRUCache.get(3); // return 3

lRUCache.get(4); // return 4

**Constraints:**

`1 <= capacity <= 3000`

`0 <= key <= 3000`

`0 <= value <= 104`

- At most
`3 * 104`

calls will be made to`get`

and`put`

.

**Intuition**

The problem can be solved with a hashmap that keeps track of the keys and its values in the double linked list. That results in O(1) time for `put`

and `get`

operations and allows to remove the first added node in O(1) time as well.

One advantage of *double* linked list is that the node can remove itself without other reference. In addition, it takes constant time to add and remove nodes from the head or tail.

One particularity about the double linked list implemented here is that there are *pseudo head* and *pseudo tail* to mark the boundary, so that we don’t need to check the `null`

node during the update.

**Code**

**Complexity Analysis**

- Time complexity : O(1) both for
`put`

and`get`

. - Space complexity : O(
*capacity*) since the space is used only for a hashmap and double linked list with at most`capacity + 1`

elements.