Design Data Structure (Part I: LRU Cache)

LRU Cache

LeetCode 146. LRU Cache (Medium):

  • Description in short:
Implement the LRUCache class:
- LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
- int get(int key) Return the value of the key if the key exists, otherwise return -1.
- void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.
Follow up: Could you do get and put in O(1) time complexity?Eg.1:
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
[null, null, null, 1, null, -1, null, -1, 3, 4]

a. Solution I, using one dictionary and one doubly LinkedList

  • Diagram:
  • Solution:

Use 1 dictionary and 1 Doubly Linked List:

dboubly linked list: node (key,value,pre,next)         cache_key=1        cache_key=2        cache_key=3
cache_value=node1 cache_value=node2 cache_value=node3
| | |

head <-------> node1 <-------> node2 <-------> node3 <-------> tail
key=1 key=2 key=3
value=1 value=2 value=3
pre=head pre=node1 pre=node2
next=node2 next=node3 next=tail
| |
most recently used least recently used
add new node here remove node here

Add node to head:

step 1: define variables:
next_n =
step 2: modify pointers: = node
node.pre = head = next_n
next_n.pre = node

Remove from tail:

step 1: define variables:
node = tail.pre
pre_n = node.pre
step 2: modify pointers: = tail
tail.pre = pre_n

Remove node:

step 1: define variables
pre_n = node.pre
next_n =
step 2: modify pointers: = next_n
next_n.pre = pre_n
  • Code:

ListNode class:

LRUCache class:

    def __init__(self, capacity: int):

self.capacity = capacity
self.cache_dict = {}

self.head = ListNode(None, None)
self.tail = ListNode(None, None) = self.tail
self.tail.prev = self.head

def add_node_to_head(self, node):

next_n = = node
node.pre = self.head = next_n
next_n.pre = node

def remove_node(self, node):

pre_n = node.pre
next_n = = next_n
next_n.pre = pre_n

def remove_from_tail(self):

node = self.tail.pre
pre_n = node.pre = self.tail
self.tail.pre = pre_n

def move_to_head(self, node):


def get_size(self):
return len(self.cache_dict)

def get(self, key: int) -> int:
# if exist, move the node to the head

if key not in self.cache_dict:
return -1

node = self.cache_dict[key]
return node.value

def put(self, key: int, value: int) -> None:
# add the node to the head

if key in self.cache_dict:
node = self.cache_dict[key]
node.value = value
node = ListNode(key, value)
self.cache_dict[key] = node

if self.get_size() > self.capacity:
del self.cache_dict[lru_cache.tail.pre.key]

b. Solution II, using Python OrderedDict

Note. this is not the solution the interviewer is looking for. Also, Python’s OrderedDict is implemented using a dictionary and a doubly linked list. See source code:

  • Code
def get(self, key: int) -> int:

if key not in self:
return -1

return self[key]
def put(self, key: int, value: int) -> None:

if key in self:
self[key] = value
if len(self) > self.capacity:
self.popitem(last = False)

Software Engineer

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store