LRU cache design with hash map and doubly linked list in Data Structures Theory - Mini Project: Build & Apply

LRU Cache Design with Hash Map and Doubly Linked List

📖 Scenario: You are building a system that remembers the most recently used items to speed up access. This system should forget the least recently used items when it runs out of space.To do this efficiently, you will combine a hash map for quick lookups and a doubly linked list to track usage order.

🎯 Goal: Build a simple LRU (Least Recently Used) cache that supports adding, retrieving, and automatically removing the least recently used items when full.

📋 What You'll Learn

Create a doubly linked list node class with key, value, prev, and next pointers

Create a hash map (dictionary) to store keys and their corresponding nodes

Implement methods to add nodes to the front and remove nodes from the list

Implement the LRU cache with get and put methods that update usage order and remove least recently used items when capacity is exceeded

💡 Why This Matters

🌍 Real World

LRU caches are used in web browsers, databases, and operating systems to speed up access to frequently used data by remembering recent items and discarding older ones.

💼 Career

Understanding LRU cache design is important for software engineers working on performance optimization, system design, and memory management in real-world applications.

1

Create the Node class for the doubly linked list

Define a class called Node with an __init__ method that takes key and value as parameters. Initialize self.key, self.value, self.prev, and self.next attributes. Set self.prev and self.next to None.

Data Structures Theory

# Define the Node class with key, value, prev, and next attributes
# Your code here

Hint

Think of each node as a box holding a key and value, with links to the previous and next boxes.

2

Set up the LRUCache class with capacity and initial data structures

Create a class called LRUCache with an __init__ method that takes capacity as a parameter. Inside, create a dictionary called cache to store keys and nodes. Initialize self.capacity with the given capacity. Also, create two dummy nodes called head and tail of type Node with key and value set to 0. Link head.next to tail and tail.prev to head.

Data Structures Theory

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

# Define LRUCache class with capacity, cache dictionary, and dummy head and tail nodes
# Your code here

Hint

The dummy head and tail nodes help manage the doubly linked list easily without checking for empty states.

3

Add helper methods to add and remove nodes from the doubly linked list

Inside the LRUCache class, define two methods: _add_node(self, node) and _remove_node(self, node). The _add_node method should insert the given node right after head. The _remove_node method should unlink the given node from the list by adjusting the prev and next pointers of its neighbors.

Data Structures Theory

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

    # Add node right after head
    # Your code here

    # Remove node from the list
    # Your code here

Hint

Adding a node means placing it right after the head. Removing means skipping over it by linking its neighbors.

4

Implement get and put methods for the LRUCache

Inside the LRUCache class, implement the get(self, key) method that returns the value of the node with the given key if it exists, otherwise returns -1. When accessed, move the node to the front (most recently used). Also implement the put(self, key, value) method that adds a new node or updates an existing node's value, moves it to the front, and if the cache exceeds capacity, removes the least recently used node from the end.

Data Structures Theory

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def _add_node(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def _remove_node(self, node):
        prev_node = node.prev
        next_node = node.next
        prev_node.next = next_node
        next_node.prev = prev_node

    # Define get method
    # Your code here

    # Define put method
    # Your code here

Hint

When you get a key, move it to the front. When you put a key, add or update it and remove the least used if full.

Practice

1. What is the main purpose of using a doubly linked list in an LRU cache design?

easy

A. To hash keys for constant time access

B. To store key-value pairs for fast lookup

C. To sort items by their values

D. To keep track of the order of item usage for quick updates

Solution

1. Step 1: Understand the role of doubly linked list in LRU cache

   The doubly linked list maintains the order of items from most recently used to least recently used.

2. Step 2: Explain why order tracking is important

   This order allows quick removal of the least recently used item when the cache is full.

3. Final Answer:

   To keep track of the order of item usage for quick updates -> Option D

4. Quick Check:

   Doubly linked list = usage order tracking [OK]

Hint: Doubly linked list tracks usage order in LRU cache [OK]

Common Mistakes:

• Confusing hash map role with doubly linked list
• Thinking doubly linked list stores key-value pairs
• Assuming it sorts items by value

2. Which of the following correctly describes the time complexity of the get operation in an LRU cache implemented with a hash map and doubly linked list?

easy

A. O(n), where n is the number of items in the cache

B. O(1), constant time

C. O(log n), due to sorting

D. O(n^2), because of list traversal

Solution

1. Step 1: Analyze the get operation components

   The hash map provides direct access to the node in constant time.

2. Step 2: Consider the doubly linked list update

   Moving the accessed node to the front is done in constant time using pointers.

3. Final Answer:

   O(1), constant time -> Option B

4. Quick Check:

   Hash map + doubly linked list = O(1) get [OK]

Hint: Hash map lookup + list update = O(1) get [OK]

Common Mistakes:

• Assuming list traversal causes O(n) time
• Confusing sorting with LRU operations
• Thinking get requires scanning all items

3. Consider an LRU cache with capacity 2. After these operations: put(1, 1), put(2, 2), get(1), put(3, 3), what will get(2) return?

medium

A. 2

B. 1

C. -1

D. 3

Solution

1. Step 1: Track cache state after each operation

   After put(1,1) and put(2,2), cache has keys 1 and 2. get(1) makes key 1 most recently used.

2. Step 2: Insert put(3,3) and evict least recently used

   Key 2 is least recently used and gets evicted. Cache now has keys 1 and 3.

3. Step 3: Check get(2) result

   Key 2 was evicted, so get(2) returns -1.

4. Final Answer:

   -1 -> Option C

5. Quick Check:

   Evicted key 2, so get(2) = -1 [OK]

Hint: Evicted least used key returns -1 on get [OK]

Common Mistakes:

• Forgetting eviction after capacity reached
• Assuming get updates usage but doesn't evict
• Returning wrong value for evicted key

4. In an LRU cache implementation, a developer notices that the cache never evicts any items even after exceeding capacity. What is the most likely cause?

medium

A. The eviction logic is missing or not triggered when capacity is exceeded

B. The doubly linked list is not updated to move recently used items to front

C. The hash map is not updated when items are accessed

D. The cache capacity is set to zero

Solution

1. Step 1: Understand eviction role in LRU cache

   Eviction removes the least recently used item when capacity is exceeded.

2. Step 2: Identify why eviction might not happen

   If eviction logic is missing or not triggered, items will never be removed despite capacity limits.

3. Final Answer:

   The eviction logic is missing or not triggered when capacity is exceeded -> Option A

4. Quick Check:

   Missing eviction = no item removal [OK]

Hint: Eviction missing means cache never removes items [OK]

Common Mistakes:

• Blaming hash map updates for eviction issues
• Ignoring eviction step in put operation
• Assuming capacity zero means no eviction

5. You want to extend an LRU cache to also support a peekLeastUsed() operation that returns the least recently used key without removing it. Which data structure property allows this operation to be efficient?

hard

A. The tail pointer of the doubly linked list points to the least recently used item

B. The hash map stores keys in sorted order

C. The doubly linked list is singly linked for fast traversal

D. The cache uses a priority queue to track usage

Solution

1. Step 1: Identify how least recently used item is tracked

   The doubly linked list keeps most recently used at head and least recently used at tail.

2. Step 2: Explain how to access least used without removal

   Using the tail pointer, we can directly access the least recently used key efficiently.

3. Final Answer:

   The tail pointer of the doubly linked list points to the least recently used item -> Option A

4. Quick Check:

   Tail pointer = least recently used access [OK]

Hint: Tail of doubly linked list = least recently used key [OK]

Common Mistakes:

• Assuming hash map stores sorted keys
• Thinking singly linked list is used
• Confusing priority queue with LRU structure