LRU Cache 146

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.

Hint

double linked list + hashmap OOD

Method

Time & Space

o(1)

Code

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

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

    class DoubleLinkedList{
          Node head;
          Node tail;

          public DoubleLinkedList(){
                 head = new Node(0, 0);
                 tail = new Node(0, 0);
                 head.next = tail;
                 tail.pre = head;
          }

          public void moveToHead(Node node){
                 if (node != head.next){
                     node.next.pre = node.pre;
                     node.pre.next = node.next;
                     node.next = head.next;
                     head.next.pre = node;
                     head.next = node;
                     node.pre = head;
                 }
          }

          public Node remove(){
                 if (head.next != tail){
                     Node n = tail.pre;
                     tail.pre = n.pre;
                     n.pre.next = tail;
                     return n;
                 }
                 return null;
          }

          public void add(Node node){
                 node.next = head.next;
                 head.next.pre = node;
                 node.pre = head;
                 head.next = node;
          }
    }

    DoubleLinkedList list;
    int size;
    HashMap<Integer, Node> map;

    public LRUCache(int capacity) {
           list = new DoubleLinkedList();
           size = capacity;
           map = new HashMap<Integer, Node>();
    }

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

    public void set(int key, int value) {
           if (map.containsKey(key)){
               Node node = map.get(key);
               node.value = value;
               list.moveToHead(node);
           } else {
               if (map.size() == size){
                   Node remove = list.remove();
                   map.remove(remove.key);
               }
               Node n = new Node(key, value);
               map.put(key, n);
               list.add(n);
           }
    }
}