LRU Cache

LRU Cache — LeetCode

Design a Least Recently Used cache with get and put in O(1) average time.

Approach

Dictionary<int, LinkedList> + Doubly Linked List. Recently used nodes at the end. Rarely used at head.

• Keep dummy head and tails.
• Use Dictionary to lookup nodes in linked list.
• Remove from Dictionary when node is removed.
• Store key in Node.
• Make method to Insert at Tail and Remove from Head
• The single node case is tricky, don't call the method blindly.

Remarks

• After doing operations on links, do a runthrough to check if they actually work

Related

• Linked Lists
• Cache Policies