A hash map over a doubly linked list

Two structures, each covering the other's weakness. The most useful design pattern in the unit.

Key idea

Why doubly linked

Removing a node from the middle requires rewiring the node before it, and in a singly linked list you cannot get there from the node itself. So each node stores both prev and next.

That is the only reason. If nothing ever had to be removed from the middle, a singly linked list would do.

1class Node:2    def __init__(self, key=0, value=0):3        self.key, self.value = key, value4        self.prev = self.next = None5 6def unlink(node):7    node.prev.next = node.next8    node.next.prev = node.prev9 10def insert_after(anchor, node):11    node.prev, node.next = anchor, anchor.next12    anchor.next.prev = node13    anchor.next = node14 15head, tail = Node(), Node()          # two sentinels, never removed16head.next, tail.prev = tail, head17 18a, b = Node(1, "a"), Node(2, "b")19insert_after(head, a)20insert_after(head, b)                 # b is now most recent21 22order = []23walk = head.next24while walk is not tail:25    order.append(walk.value)26    walk = walk.next27print(order)28 29unlink(a)30order = []31walk = head.next32while walk is not tail:33    order.append(walk.value)34    walk = walk.next35print(order)

The two operations in terms of the pieces

A read: look the key up in the dict. If absent, report a miss. If present, unlink the node and reinsert it at the most recent end, then return its value.

A write: if the key exists, update the value and move the node to the most recent end. If not, create a node, insert it at the most recent end, and record it in the dict. Then, if the size now exceeds the limit, unlink the node at the least recent end and delete its key from the dict.

Both are three or four lines once unlink and insert_after exist. Build those first.

Complexity· 5 min

Cost of the combined structure

Time for a single get or put on the cache, and total space for a cache holding at most k entries.

Python

1node = self.by_key[key]      # dict lookup2unlink(node)                 # constant, thanks to prev and next3insert_after(self.head, node)4return node.value

Problem· 35 min

Lru Cache

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

CodeGround