# Super clear O(1) solution using Minimum BASIC data structure (TWO hash tables + ONE doubly linked list)

• The basic idea is using ONE doubly linked list to maintain all the data in the cache, wherein each node accommodates a key-value pair. This is the key difference from other solutions using two or 2-d doubly linked list. Storing all the node in a 1-d linked list can avoid many complex 2-d linked list operations, which is error-prone. The nodes that have been accessed for the same frequency are grouped together like in a bucket. And the groups are arranged in the ascending order of frequency in the linked list, where less frequently-accessed node are put behind. So when cache is full, the first node in the linked list will be evicted.

Two hash tables. One is used for O(1) access from key to its node. And the other is for O(1) access from frequency to boundary node of frequency buckets. More precisely, the boundary nodes are the rightmost node of the buckets, because when we need to add a new node to the bucket, we can easily find the position to add it.

`````` ------------>    direction of more ```frequent and recent``` access ----->

dummy head <-> n1 <-> n2 <-> n3 <-> n4 <-> n5 <-> n6 <-> n7 <-> dummy tail
buckets        ----------------     ----------------     ---
freq = 1             freq = 3       freq = 9
frequency table f  f[1]=n3              f[3]=n6        f[9]=n7
``````
``````class DLinkNode(object):  # Doubly Linked List Node
def __init__(self, key, value):
self.key, self.value = key, value
self.freq = 0
self.prev = self.next = None

node.prev = self
self.next = node

def connect(self, node):  # Connect node behind self

def disconnect(self):  # Disconnect self from Linked List
self.prev.next = self.next
self.next.prev = self.prev

class LFUCache(object):
def __init__(self, capacity):
self.remain = self.capacity = capacity

self.tail = DLinkNode(-2, -2)  # dummy tail

self.cache = {}  # mapping from key to DLinkNode

def remove(self, key):  # Remove node from linked list
node = self.cache[key]
if self.freq[node.freq] is node:  # node is sentinel
if node.prev.freq == node.freq:
self.freq[node.freq] = node.prev  # re-assign sentinel
else:  # node is the only node in the frequency bucket
del self.freq[node.freq]
node.disconnect()

node = self.cache[key]
f = node.freq = node.freq + 1
if f in self.freq:  # freq+1 bucket exists
self.freq[f].connect(node)
elif f - 1 in self.freq:  # freq bucket exists
self.freq[f - 1].connect(node)
else:  # both buckets not exsits
node.prev.connect(node)
self.freq[f] = node

def move(self, key):
self.remove(key)

def get(self, key):
if key in self.cache:
self.move(key)
return self.cache[key].value
return -1

def put(self, key, value):
if not self.capacity: # handle the 0-capacity case
return
if key in self.cache:
self.cache[key].value = value
self.move(key)
else:
if not self.remain: