[Leetcode Solution] LRU Cache

Good Problem

Analysis

• In order to implement a LRU cache which has get and set operation. And each operation should be constant time.
• Because the feature of LRU, previous used node should be transferred as latest. Thus a linked list type data structure should be applied. 
• In order to achieve constant time for get, obviously a hash table will be used which maintains the mapping from the key to value. However the value is stored at linked list and the list is mutable. Thus the mapping should be from the key to the pointer pointing to the location where the value stored in the linked list.

Note

• Long time no use STL container, a great review of them. See this summary of STL container
• List.end() is not the iterator point to list.back()

Code

Code At LeetCode 2nd Pass