# Leetcode 146 - LRU cache

`Note:`

- To
`get`

something is O(1), that must be a`hash`

. - But hash has
`no order`

. How can we know the updating order? We need another data structure. - It can’t be an array because searching is at least O(n) for array. It can’t be a single linked list coz seaching is also O(n).
- Let’s use a
`double linked list`

! And store the`reference in hash`

. - Use
`dummyHead`

and`dummyTail`

are techniques in linked list to bring convenience. - We need several helpers
`moveToHead(node)`

.`addToHead(node)`

.`removeLRUItem()`

`removeNodeFromList(node)`

.

`Question:`

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.

The functions`get`

and`put`

must each run in`O(1)`

average time complexity.

`Example:`

1 | Input |

`Code:`

1 | /** |