Design and implement a data structure for Least Recently Used (LRU) cache

Rajeev SinghAlgorithms1 mins read

Problem Statement: Design an LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations:

  • get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

  • put(key, value) - Set or insert the value for the given key in the cache. When the cache has reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Example:

LRUCache cache = new LRUCache(2);

cache.put(5, 7);
cache.put(8, 20);
cache.get(5);       // returns 7
cache.put(3, 6);    // evicts key 8
cache.get(8);       // returns -1 (not found)
cache.put(4, 12);   // evicts key 5
cache.get(5);       // returns -1 (not found)
cache.get(3);       // returns 6
cache.get(4);       // returns 12

LRU Cache implementation in Java

Note that, we need to track which keys are recently accessed so that we can invalidate the key which was least recently used when the cache is full.

We’ll use a HashMap and a Doubly Linked List for implementing our LRU cache. The HashMap will hold the key and the reference to the Node of the Doubly Linked List.

HashMap data structure is used for O(1) operations on get(key) and put(key, value). And Doubly Linked List is chosen because it supports fast insertion and deletion of nodes.

Whenever a key is accessed in the cache, we’ll move its corresponding node to the front of the doubly linked list. When the cache is full, we’ll remove the node from the back of the doubly linked list.

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

class Node {
    int key;
    int value;
    Node next;
    Node prev;

    Node(int key, int value) {
        this.key = key;
        this.value = value;
    }

    @Override
    public String toString() {
        return String.valueOf(value);
    }
}

class LRUCache {
    private int capacity;
    private Map<Integer, Node> cache;
    private Node head;
    private Node tail;

    LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>(capacity);
    }

    public int get(int key) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            moveToFront(node);
            return node.value;
        }
        return -1;
    }

    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            node.value = value;
            moveToFront(node);
            return;
        }

        Node node = new Node(key, value);

        if (cache.size() == capacity) {
            cache.remove(tail.key);
            removeNode(tail);
        }

        cache.put(key, node);
        addFirst(node);
    }

    private void moveToFront(Node node) {
        removeNode(node);
        addFirst(node);
    }

    private void removeNode(Node node) {
        Node prevNode = node.prev;
        Node nextNode = node.next;

        if (prevNode != null) {
            prevNode.next = nextNode;
        } else {
            head = nextNode;
        }

        if (nextNode != null) {
            nextNode.prev = prevNode;
        } else {
            tail = prevNode;
        }
    }

    private void addFirst(Node node) {
        node.next = head;
        node.prev = null;

        if (head != null) {
            head.prev = node;
        }
        head = node;

        if (tail == null) {
            tail = node;
        }
    }
}

class LRUCacheExample {
    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);

        int capacity = keyboard.nextInt();
        LRUCache cache = new LRUCache(capacity);

        while (true) {
            String[] commandLine = keyboard.nextLine().trim().split("\\s");
            String command = commandLine[0];
            if (command.isEmpty()) {
                continue;
            }
            switch (command) {
            case "get": {
                int num = Integer.parseInt(commandLine[1]);
                System.out.println(cache.get(num));
                break;
            }
            case "put": {
                int key = Integer.parseInt(commandLine[1]);
                int value = Integer.parseInt(commandLine[2]);
                cache.put(key, value);
                break;
            }
            case "exit": {
                return;
            }
            default:
                System.out.println("Invalid command");
            }
        }
    }
}
# Output
$ javac LRUCacheExample.java

$ java LRUCacheExample
2
put 5 7
put 8 20
get 5
7
put 3 6
get 8
-1
put 4 12
get 5
-1
get 3
6
get 4
12
exit