LRU cache implementation in java

ghz 10months ago ⋅ 63 views

LRU (Least Recently Used) cache is a type of cache in which the least recently used items are removed when the cache reaches its maximum capacity. You can implement an LRU cache using a combination of a HashMap and a doubly linked list. Here's a Java implementation:

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

class LRUCache {

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

    private final Map<Integer, Node> cache;
    private final int capacity;
    private final Node head;
    private final Node tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>(capacity);
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node node = cache.get(key);
        if (node != null) {
            moveToHead(node);
            return node.value;
        }
        return -1;
    }

    public void put(int key, int value) {
        Node node = cache.get(key);
        if (node == null) {
            node = new Node();
            node.key = key;
            node.value = value;
            cache.put(key, node);
            addNode(node);
            if (cache.size() > capacity) {
                removeTail();
            }
        } else {
            node.value = value;
            moveToHead(node);
        }
    }

    private void moveToHead(Node node) {
        removeNode(node);
        addNode(node);
    }

    private void addNode(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

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

    private void removeTail() {
        Node tailNode = tail.prev;
        removeNode(tailNode);
        cache.remove(tailNode.key);
    }
}

In this implementation:

  • We define a nested class Node to represent a node in the doubly linked list.
  • The LRUCache class maintains a HashMap cache to store the mapping of keys to corresponding nodes in the linked list.
  • We maintain a doubly linked list with a dummy head and tail node.
  • When we access or update a key-value pair, we move the corresponding node to the head of the linked list to represent its most recently used status.
  • When the cache reaches its maximum capacity, we remove the least recently used node from the tail of the linked list and the cache.
  • The get method retrieves the value associated with the specified key from the cache. If the key is present, it moves the corresponding node to the head of the linked list and returns the value; otherwise, it returns -1.
  • The put method adds or updates a key-value pair in the cache. If the key is not present, it creates a new node, adds it to the head of the linked list, and adds the key-node mapping to the cache. If the cache reaches its maximum capacity, it removes the least recently used node from the tail of the linked list and the cache.
  • The moveToHead, addNode, removeNode, and removeTail methods are helper methods to manipulate the linked list.
#algorithm