With that, we can initialize doubly linked list nodes easily by calling new DLinkedNode(key, value, null, null).
In the Cache class, we'll also want to add the standard addNode and removeNode helper methods, as we'll be doing that quite a bit. addNode specifically adds a new node to the head of the doubly linked list. removeNode removes it place by manipulating the pre and next values of its neighbors.
1class DLinkedNode:
2 def __init__(self, key, val, pre, next):
3 self.key = key
4 self.val = val
5 self.pre = pre
6 self.next = next
7
8# for our Cache class
9def addNode(node):
10 node.pre = self.head
11 node.next = self.head.next
12 self.head.next.pre = node
13 self.head.next = node
14
15def removeNode(node):
16 # take a node's predecessor
17 pre = node.pre
18 # find the node after it
19 next = node.next
20 # assign the predecessor's "next" node as the one after current
21 pre.next = next
22 next.pre = pre