LRU cache design with hash map and doubly linked list in Data Structures Theory - Step-by-Step Execution

Concept Flow - LRU cache design with hash map and doubly linked list

Start: Cache empty

↓

Insert new key

↓

Is cache full?

No→Add node at head of DLL

↓

Add key-node to hashmap

↓

Remove tail node

↓

Add new node at head

↓

Update hashmap with new node

↓

Access key?

Yes↓

Move node to head

↓

Return value

↓

End

The cache stores keys in a doubly linked list (DLL) for order and a hashmap for fast access. On insert, if full, remove tail node (least recently used). On access, move node to head (most recently used).

Execution Sample

Data Structures Theory

cache = LRUCache(2)
cache.put(1, 'A')
cache.put(2, 'B')
cache.get(1)
cache.put(3, 'C')
cache.get(2)

This code creates an LRU cache of size 2, adds two items, accesses one to update usage, adds a third causing eviction, then tries to access an evicted key.

Analysis Table

Step	Operation	Hashmap State	DLL State (Head->Tail)	Eviction	Output
1	put(1, 'A')	{1:'A'}	[1:A]	No	None
2	put(2, 'B')	{1:'A', 2:'B'}	[2:B <-> 1:A]	No	None
3	get(1)	{1:'A', 2:'B'}	[1:A <-> 2:B]	No	'A'
4	put(3, 'C')	{1:'A', 3:'C'}	[3:C <-> 1:A]	Evict key 2	None
5	get(2)	{1:'A', 3:'C'}	[3:C <-> 1:A]	No	-1 (not found)

💡 Step 5: get(2) returns -1 because key 2 was evicted in step 4.

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5
Hashmap	{}	{1:'A'}	{1:'A', 2:'B'}	{1:'A', 2:'B'}	{1:'A', 3:'C'}	{1:'A', 3:'C'}
DLL Head	null	1:A	2:B	1:A	3:C	3:C
DLL Tail	null	1:A	1:A	2:B	1:A	1:A
Cache Size	0	1	2	2	2	2

Key Insights - 3 Insights

Why do we move a node to the head of the DLL on access?

Moving the accessed node to the head marks it as most recently used, so it won't be evicted soon. See step 3 in execution_table where get(1) moves key 1 to head.

Why do we remove the tail node when the cache is full?

The tail node is the least recently used item. Removing it frees space for new entries. Step 4 shows eviction of key 2 at the tail when adding key 3.

How does the hashmap help in this design?

The hashmap allows O(1) access to nodes in the DLL by key, avoiding traversal. This is why get operations are fast, as shown in steps 3 and 5.

Visual Quiz - 3 Questions

Look at the execution_table at step 3. What is the DLL state after get(1)?

A [1:A <-> 2:B]

B [2:B <-> 1:A]

C [1:A]

D [2:B]

💡 Hint

Check the DLL State column at step 3 in execution_table.

At which step does the cache evict a key due to capacity?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look for 'Eviction' column in execution_table.

If we increase cache size to 3, what would happen at step 4?

A Eviction of key 2 still happens

B No eviction, key 3 added at head

C Cache becomes empty

D Key 1 is evicted

💡 Hint

Consider cache capacity and eviction logic in concept_flow.

Concept Snapshot

LRU Cache uses a hashmap + doubly linked list.
Hashmap: O(1) key-node lookup.
DLL: Maintains usage order, head = most recent.
On get: move node to head.
On put: add at head, evict tail if full.
Eviction removes least recently used item.

Full Transcript

An LRU cache stores data so that the most recently used items stay available, and the least recently used items get removed when full. It uses a hashmap for quick key lookup and a doubly linked list to track usage order. When you add a new item and the cache is full, it removes the tail node (the least recently used). When you access an item, it moves that item to the head of the list to mark it as recently used. This design ensures fast access and efficient eviction.

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