146. LRU Cache

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.

Follow up:
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.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

---
Intuition

We need data structure to

1. Move Node from middle of data structure to front
2. Evict (remove) from last

Doubly linked list supports that

We can use Map <Key, Node> to track if Node already exists in LRU cache, and update value when put is called

When LRU cache capacity is exceeded, we need to evict the last element in DLL and also remove it from the existing map

We also need DLL element to store key so that it can be used to remove Node from map

So Node is designed as
int key
int val
Node prev
Node next

Solution is simplified with dummy first, and last nodes to manage

1. Move to front
2. Evict

---