LRU Cache

Design a Least Recently Used (LRU) cache with get(key) and put(key,value) operations, both O(1). Evict the least recently used item when capacity is exceeded.

Example 1

LRUCache(2), put(1,1), put(2,2), get(1)→1, put(3,3) [evicts 2], get(2)→-1, get(3)→3

Solution Approach

Use a HashMap + Doubly Linked List. Map stores key→node. DLL keeps order (head=most recent, tail=LRU). On access, move node to front.

DLL with sentinel head and tail.
get: if exists, move to front, return val.
put: if exists update and move to front; else insert at front; if over capacity remove tail.

Java

import java.util.*;

class LRUCache {
    class Node { int key, val; Node prev, next; Node(int k,int v){key=k;val=v;} }
    Map<Integer,Node> map = new HashMap<>();
    Node head = new Node(0,0), tail = new Node(0,0);
    int cap;

    public LRUCache(int capacity) {
        cap=capacity; head.next=tail; tail.prev=head;
    }
    private void remove(Node n) { n.prev.next=n.next; n.next.prev=n.prev; }
    private void insertFront(Node n) { n.next=head.next; n.prev=head; head.next.prev=n; head.next=n; }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node n=map.get(key); remove(n); insertFront(n); return n.val;
    }
    public void put(int key, int value) {
        if (map.containsKey(key)) { Node n=map.get(key); n.val=value; remove(n); insertFront(n); return; }
        Node n = new Node(key,value); map.put(key,n); insertFront(n);
        if (map.size()>cap) { map.remove(tail.prev.key); remove(tail.prev); }
    }
}

Time Complexity: get/put: O(1)
Space Complexity: O(N)