# LeetCode LRU Cache: Hash + Doubly Linked List

## Overview

The O(1) time algorithm to solve LeetCode LRU Cache is by combining hash table (access cache location) and doubly linked list (maintain the least recent).

## LeetCode LRU Cache

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

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(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.

## LeetCode LRU Cache Analysis: Hash + Doubly Linked List

Well, I personally do not consider this is a hard problem by utilizing the STL list from C++, or even we code all the things from scratch by writing  the doubly linked list from scratch as long as we are careful for the specially cases like there is only one node, or we access the most recent node which does not require relocate any of the existed cache locations and so on. Anyways, here is how I come up with the final algorithm to implement the LRU cache.

1) Using a hash map to simulate the cache memory. This is very straightforward because we see key/value pairs, and how to maintain the most/least structure? My first try is to use an array/vector in C++ and if a key is hit (either get/set) then this key becomes the most recent, we will have to move/promote it to put it in the most recent location (either the head/tail in the array). If we use array, this promote operation inlcuding find and relocate costs O(N) time and it will report TLE time limit exceeds error