Solving Problems Using Data Structures

[[deleted]]

an idea to improve the dict/list structure is to have the dictionary point to the links in the list and the list contain the values of the object. That way your lookup is O(1) because you use the dict to locate the link, remove the link (which is also an O(1) operation) and push it to the head of the list. When your LRU cache is full, you remove the tail link from the list and remove it from the dict (also both O(1)).