LRU cache [Doubly LInked List]

146.LRU Cache

Hash Table

Linked List

Design

Problem Statement:

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class with get and put operations in O(1) time complexity.

Example:

Input:

["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

→

Output:

[null, null, null, 1, null, -1, null, -1, 3, 4]

Algorithm:

1. Use HashMap + Doubly Linked List for O(1) operations
2. HashMap: Quick access to nodes
3. Doubly Linked List: Quick removal/addition of nodes
4. Most recent items at tail end
5. Remove from head when cache is full

Java Solution:

class LRUCache {
    // Core components: HashMap for O(1) lookup, Doubly-Linked List for O(1) removal
    int capacity;
    int size;
    Map<Integer, Node> cache;    // key → node mapping
    Node head;    // Dummy head - least recently used end
    Node tail;    // Dummy tail - most recently used end
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.cache = new HashMap<>();
        
        // Initialize dummy nodes for easier list manipulation
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;              
    }
    
    public int get(int key) {
        if (!cache.containsKey(key)) return -1;
        
        Node node = cache.get(key);
        // Move to end (mark as most recently used)
        removeNode(node);
        addToEnd(node);      
        return node.val;
    }
    
    public void put(int key, int value) {
        // If key exists, update value and move to end
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            node.val = value;
            removeNode(node);
            addToEnd(node);
            return;
        }
         
        // Add new node to cache and list
        Node node = new Node(key, value);
        cache.put(key, node);
        addToEnd(node);
        
        // Handle capacity - remove LRU if needed
        if (size + 1 > capacity) {
            cache.remove(head.next.key);  // Remove LRU from cache
            removeNode(head.next);        // Remove LRU from list
        } else {
            size++;
        }
    }
    
    // Helper to remove node from current position
    private void removeNode(Node node) {
        Node prev = node.prev;
        Node next = node.next;
        prev.next = next;
        next.prev = prev;
    }
    
    // Helper to add node to end (most recently used)
    private void addToEnd(Node node) {
        node.prev = tail.prev;
        node.next = tail;
        node.prev.next = node;
        tail.prev = node;
    }
    
    // Node class for doubly-linked list
    private class Node {
        int key;
        int val;
        Node prev;
        Node next;
        
        public Node() {}
        
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
}

Complexity:

Time: O(1) for both get and put | Space: O(capacity)