Implementing an LRU Cache

Last week, I wrote about caching and discussed different caching approaches and ways to keep your cache data in sync with the database. A cache is a super effective way to make your application or website more performant, as it can store frequently requested data in a fast-retrieval, data storage layer instead of querying the database every time.

However, a cache is limited in size and memory. To maintain what gets stored in memory, there needs to be a way for the cache to regulate what goes in (cached) and what goes out (evicted).

This post is dedicated to a common cache policy (that often comes up in coding interviews): the Least Recently Used (LRU) cache. An LRU cache will discard the least recently used item in the cache to make space for new item(s).

Implementation

Implementing a Least Recently Used (LRU) cache traditionally involves a hash map and a doubly linked list.

The linked list would have the most-recently used item at the head of the list and the least-recently used item stored at the tail.

At this point, getting the least-recently used item would take O(1) time since we can look at the tail, but accessing any other specific item that's not the tail or head would take O(n) time since we would have to walk through the entire list.

Access and Eviction

Below are the following steps to go through each time an item is accessed in the cache.

• Look up the item in the hash map
• If the item is the hash map, hooray, it's a "cache hit" and it's already in the cache
  1. Find the corresponding linked list node with the hash map
  2. Move the item's linked list node to the head of the linked list. It's now the most recently used item.
• If the item is not in the hash map, boo, it's a "cache miss" and you'll have to load the item into the cache
  1. Cache full? Then an item will have to be evicted (evict the LRU cache item, the tail, by removing it from the linked list and hash map)
  2. Create a new linked list node for the item and insert it at the head of the linked list
  3. Add the item to the hash map, with the new node as the value

Code

Like I mentioned above, implementing an LRU cache can often come up in coding interviews. Leetcode features an LRU cache problem where you have to implement get and put operations for the cache.

• get(key) gets the value of the key if the key exists in the cache
• put(key, value) sets or inserts the value if the key is not already present
• If the cache has reached its capacity, it should invalidate the least recently used item before inserting a new item.

In my solution below, it features a few classes including LRUCache, DoublyLinkedList, and Node.

Happy coding!

Resources
LRU Cache - Interview Cake
LRU Cache - Leetcode