LRU Cache | HashMap + Doubly Linked List

Problem Statement

Design an LRU (Least Recently Used) Cache supporting:

get(key)



put(key,value)

Both operations must run in:

O(1)

Brute Force Intuition

Use:

ArrayList

Whenever an element is accessed:

Search it.

Move it to the front.

If capacity exceeds:

Remove last element.

Complexity

• get → O(N)


• put → O(N)

Moving Towards the Optimal Approach

We need:

Fast Lookup

and

Fast Deletion / Insertion

Use:

HashMap



+



Doubly Linked List

Pattern Recognition

Need O(1) Lookup



+



Need O(1) Update



=> HashMap + DLL

Key Observation

HashMap:

key



↓



Node Address

DLL stores usage order.

Most Recently Used:

Front

Least Recently Used:

Back

Operations

get()

Found ?



↓



Move Node to Front



↓



Return Value

put()

Already Exists?

Update



Move Front

Else:

Insert Front

If capacity exceeded:

Remove Tail

Complexity Analysis

Interview One-Liner

Combine a HashMap for O(1) lookup and a Doubly Linked List for O(1) insertion, deletion, and eviction of the least recently used element.

Pattern Learned

Cache



+



Order Matters



=> HashMap + Doubly Linked List