LRU Cache

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

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Solution: Use a doubly linked list, with a head and tail node pointers, as well as a hashMap with all the key and node pairs.

1. When get(), it first checks if the key is in the map, if it is, remove that node from its original position and move to the tail (right before the tail node). if it doesn’t exists, return -1.

2. When set(key, value), it first call get function, to see if it exists, them update the value, otherwise, check if the queue is full, then remove the first element (the one right after head node) and add the new node to the tail.

Set(), Get() O(1) Time.

public class Solution {
    public class Node {
        int key;
        int value;
        Node prev;
        Node next;
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
            this.prev = null;
            this.next = null;
        }
    }

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

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

    public int get(int key) {
        if (cache.containsKey(key)) {
            //remove it from its original place
            //put to the tail the queue
            Node node = cache.get(key);
            removeNode(node);
            addToTail(node);
            return node.value;
        }
        return -1;
    }

    public void set(int key, int value) {
        if (get(key) != -1) {
            cache.get(key).value = value;
            return;
        }
        Node newNode = new Node(key, value);
        if (cache.size() < capacity) {
            addToTail(newNode);
        } else {
            cache.remove(head.next.key);
            removeNode(head.next);
            addToTail(newNode);
        }
        cache.put(newNode.key, newNode);
    }

    public void addToTail(Node node) {
        node.prev = tail.prev;
        node.prev.next = node;
        node.next = tail;
        tail.prev = node;
    }

    public void removeNode(Node node) {
        if (node.prev != null) {
            node.prev.next = node.next;
        }
        if (node.next != null) {
            node.next.prev = node.prev;
        }
        node.next = null;
        node.prev = null;
    }
}

Share