[LeetCode] LRU Cache

Problem:

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:

Cache should achieve the O(1) time complexity of get and set operation.

(1) To achieve the O(1) time complexity of look up operation, HashMap should be used to store the mapping relation between key and value(Node, in this solution).

(2) To achieve the O(1) time complexity of the invalidation operation of the least recently used item, double linked listed should be used. Every time, when there is a get operation, the accessed item will be moved to the head of the linked list. And the tail of the least recently used element of the cache.

Therefore, HashMap and Linked List should be used in this solution.

Code:

public class LRUCache {
    
    private int capacity;
    
    private Node head;
    private Node tail;
    
    private HashMap<Integer, Node> hs = new HashMap<Integer, Node>();
    
    private class Node {
        public int key;
        public int value;
        public Node pre;
        public Node next;
        
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        
        head.next = tail;
        head.pre = null;
        tail.pre = head;
        tail.next = null;
    }
    
    public int get(int key) {
        if (!hs.containsKey(key)) {
            return -1;
        }
        
        Node n = hs.get(key);
        n.pre.next = n.next;
        n.next.pre = n.pre;
        
        n.next = head.next;
        head.next = n;
        n.pre = head;
        n.next.pre = n;
        
        return n.value;
        
    }
    
    public void set(int key, int value) {
// Attention, made a mistake here, did not consider if the key already exist in hs.
        if (hs.containsKey(key)) {
            Node n = hs.get(key);
            n.pre.next = n.next;
            n.next.pre = n.pre;
            hs.remove(key);
            capacity++;
        }
        
        if (capacity <= 0) {
            Node n = tail.pre;
            n.pre.next = n.next;
            n.next.pre = n.pre;
            hs.remove(n.key);
            
            capacity++;
        }
        
        Node temp = new Node(key, value);
        temp.next = head.next;
        head.next = temp;
        temp.pre = head;
        temp.next.pre = temp;
        
        hs.put(key, temp);
        
        capacity--;
        
        
    }
}