Now, when we new up a Cache instance, we'll want certain things predefined in the constructor. Let's flesh that out:

  1. We'll need a reference to the capacity
  2. A count for the number of keys we have
  3. The cache via a hash table itself
  4. References to the heads and tails of the doubly linked list
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