We're now in business. Let's start adding stuff by implementing the put method. put should check if the value exists or not in this.cache based on the key. If it doesn't, we can add it in.

However, it's not enough to just add it in-- the whole reason for using a doubly linked list is also to see the order of use. Thus, if we're adding a new value, it means that it's the most recently used, and we should thus move it to the front of the linked list. This serves to be an indication that we should NOT evict it.

Step Five

put checks if the node is in the cache. If it's not, we create a new node in the doubly linked list (added to the head), and increment our length. We also check at this point if we're over capacity-- if we are, we get rid of the node at the tail, as it's the least recently used.

Alternatively, if the node already exists, we simply overwrite the existing node value and move it to the start.

1class Cache:
2    def __init__(capacity):
3        self.count = 0
4        self.capacity = capacity
5        self.cache = {}
6        self.head = DLinkedNode()
7        self.head.pre = null
8        self.tail = DLinkedNode()
9        self.tail.next = None
10        self.head.next = self.tail
11        self.tail.pre = self.head
12
13    def put(key, value):
14        node = self.cache[key]
15        if not node:
16            new_node = DLinkedNode(key, value, None, None)
17            self.cache[key] = new_node
18            self.addNode(new_node)
19            self.count += 1
20            # the overcapacity scenario
21            # evict the value at the end of the linked list
22            if self.count > self.capacity:
23                tail = self.popTail()
24                self.cache.pop(tail.key)
25                self.count -= 1
26        else:
27            node.val = value
28            # move to head as it's the most recently used
29            self.moveToHead(node)