Let's start by laying out our requirements. We're implementing a cache with a get method and a put method. There are several other methods that we want in a production cache class, but this will do for now.

1. get(key) needs to do a lookup of the key in the cache. If it does not find the key, we'll return a -1 for "not found".

2. put(key, val) needs to insert the key if it's not in the cache. If the cache has reached capacity, it needs to invalidate the least recently used key.

There are a few ways to have get and put operate in constant time. Let's think of data structures we can use that support quick access. One easy way is to use a hash table data structure, which enables lookups in O(1) time. We set the keys and values of the cache to be a hash table/hash map, and retrieval speed is taken care of.

What about put? We'll also want our addition and eviction operations to run in constant time as well. A data structure we could introduce for this is a doubly linked list. A doubly linked list node is unique in that it has references to both the next node in the list, as well as the previous node. How does that help us? We'll see in a bit!

We get a decent hash table for free, built into many programming languages already. In the case of dynamic languages, we can use objects in JS or dictionaries in Python, so let's jump to implementing a doubly linked list. Here's what a DLinkedNode definition might look like:

1class DLinkedNode {
2	constructor(key, val, pre, next) {
3		this.key = key;
4		this.val = val;
5		this.pre = pre;
6		this.next = next;
7	}
8}