Trick behind LRU cache

Introduction

If you've never implemented an LRU cache, and it's your first time, it's gonna be very hard.

This post isn't about what an LRU cache is, or how to implement one.

I want to talk about the trick behind how it works.

Two key points

We need a Map so that we can store the key-value pairs and have O(1) access time. This map serves as our cache.

This is quite straightforward. The tricky part here is, how to deal with the order of the entries?

This is where doubly linked list comes into play.

A doubly linked list is like a normal linked list, but each node has a pointer to the previous node as well as the next node.

Because you have both the head and the tail, you know the most recent (head) and the least recent (tail) entries.

Essentially, you start off with an empty doubly linked list. Well, not exactly empty. You have a dummy head and dummy tail. They will always be there. Their goal is to make the operations easier.

If you need to access the "real" head -> this.head.next. If you need to access the "real" tail -> this.tail.prev.

To visualize how we construct the doubly linked list:

DUMMY_HEAD <-> DUMMY_TAIL

When you add the first element:

DUMMY_HEAD <-> NEW_NODE <-> DUMMY_TAIL

When you add the second element:

DUMMY_HEAD <-> NEW_NODE_1 <-> NEW_NODE_2 <-> DUMMY_TAIL

this.head.next is NEW_NODE_1 and this.tail.prev is NEW_NODE_2.

Need to remove the "real" tail?

const NEW_NODE_2 = this.tail.prev;
NEW_NODE_2.prev.next = this.tail;
this.tail.prev = NEW_NODE_2.prev;

What did we just do?

We removed NEW_NODE_2 from the list. We need to change next of NEW_NODE_2.prev (NEW_NODE_1) to point to this.tail and we need to change prev of this.tail to point to NEW_NODE_1.

We will end up with:

DUMMY_HEAD <-> NEW_NODE_1 <-> DUMMY_TAIL

Now, NEW_NODE_1 serves as both the head and the tail.

Capacity

When you construct the LRU cache, you need to specify the capacity. Which brings me to the next thing I forgot, you also need to keep track of the size of the cache. The size excludes the dummy head and dummy tail. So don't get that confused.

When adding an element, if the cache is full, you need to remove the least recent element.

Typically, you've a private method like removeTail() to remove the least recent element.

Ending words

This post was just some thoughts that helped me clarify my understanding of how an LRU cache works.

Trick behind LRU cache

Comments

More from this blog

Become a cracked product engineer today

Bipedal, humanoid, and the words for creature shapes in games

Lerp and smoothstep, what they actually do

IK and FK, what they actually are

How to make your textures fast on the GPU

Introduction

Two key points

Capacity

Ending words

Command Palette

Comments

More from this blog

Introduction

Two key points

Capacity

Ending words