3.9 LRU Cache

Description

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.

Method

HashMap + double LinkedList (head and tail two pointers) Since we need a strucut to store the (key, value) and we can update and get value from it. so we can use hashMap to implement this function. Usually, we use the first add time for the order of (key, value), But since when we do an operation of the (key, value), it has been used and not in the orginal order. we can use a linkedlist to record the order of the elements that been added to the cache. the least recent used to recently used from the head to tail and when we do a operation to one element in the list, we remove it from the orginal position and then add it to the tail agian, which means that it has been used recently.

Time and Space Complexity

get: o(1) set: o(1)

Code

public class LRUCache {

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

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

}
private int size;
private HashMap<Integer, Node> map;
private Node head;
private Node tail;

public LRUCache(int capacity) {
       head = new Node(0,0);
       tail = new Node(0,0);
       head.next = tail;
       tail.pre = head;
       map = new HashMap<Integer, Node>();
       this.size = capacity;
}

public int get(int key) {
       int res = -1;
       if (map.containsKey(key)){
           Node node = map.get(key);
           res = node.value;
           removeToTail(node);
       }
       return res;
}



public void set(int key, int value) {
        if (map.containsKey(key)){
            Node node = map.get(key);
            node.value = value;
            removeToTail(node);
        } else {
           if (map.size() == size){
               map.remove(head.next.key);
               deleteHead();
           }
            Node now = new Node(key,value);
            now.pre = tail.pre;
            tail.pre.next = now;
            now.next = tail;
            tail.pre = now;
            map.put(key, now);
        }
}

private void deleteHead(){
            head.next.next.pre = head;
            head.next = head.next.next;
}

private void removeToTail(Node node){
        if (node == tail.pre){
            return;
        }
        node.pre.next = node.next;
        node.next.pre = node.pre;
        node.pre = tail.pre;
        tail.pre.next = node;
        node.next = tail;
        tail.pre = node;
}

}