Implementing an LRU Cache
Tags: javascript
Published: 2020-06-27 23:47:07

Last week, I wrote about [caching](https://dev.to/katkelly/cache-me-if-you-can-ak) 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.** 

I love Interview Cake's examples of visualizing an LRU cache. Below is the doubly linked list illustrated sweetly (see what I did there?):
![interview-cake doubly linked list](https://www.interviewcake.com/images/svgs/lru_cache__most_and_least_recently_used_items.svg?bust=206)
<figcaption>Via Interview Cake</figcaption>

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. 

**To make lookups efficient, a hash map is used to map items to linked list nodes.** More sweetness from Interview Cake illustrating this:
![interview-cake hash map](https://www.interviewcake.com/images/svgs/lru_cache__doubly_linked_list.svg?bust=206)
<figcaption>Via Interview Cake</figcaption>

### 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](https://leetcode.com/problems/lru-cache/) 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`.

{% gist https://gist.github.com/kat-star/b3e32df218c78f13bf1e5bc0f145cc0a.js %}

Happy coding!

*Resources*
[LRU Cache - Interview Cake](https://www.interviewcake.com/concept/java/lru-cache)
[LRU Cache - Leetcode](https://leetcode.com/problems/lru-cache/)