LRUCache

Implement LRU Cache

Sol#0: HashMap and Doubly Linked List

class DListNode {
  int key;
  int val;
  DListNode left;
  DListNode right;
}

private Map<Integer, DListNode > map = new HashMap<Integer, DListNode>();

/**
 * Always add the new node right after head;
 */
private void addNode(DListNode node) {    
  node.left = head;
  node.right = head.right;

  head.right.left = node;
  head.right = node;
}

/**
 * Remove an existing node from the linked list.
 */
private void removeNode(DListNode node){  DListNode pre = node.left;
  DListNode post = node.right;

  pre.right = post;
  post.left = pre;
}

/**
 * Move certain node in between to the head.
 */
private void moveToLatest(DLinkedNode node){
  removeNode(node); // Remove from Linked List
  addNode(node); // Add to Linked List so that it should be most recent
}

public int get(int key) {

  DListNode node = map.get(key);
  if(node == null){
    return -1; // should return -1 here.
  }

  // move accessed node to the latest;
  moveToLatest(node);

  return node.val;
}

// pop the current tail. 
private DListNode removeFirst(){  DListNode res = rear.left;
  removeNode(res);
  return res;
}

public void put(int key, int value) {
  DListNode node = map.get(key);

  if(node == null){

    DListNode newNode = new DListNode();
    newNode.key = key;
    newNode.val = value;

    map.put(key, newNode);
    addNode(newNode);

    ++count;

    if(count > capacity){
      // Remove first node i.e. oldest node
      DListNode tail = removeFirst();
      map.remove(tail.key);
      --count;
    }
  } else {
    // update the value.
    node.val = value;
    moveToLatest(node);
  }
}

}

Sol#1:

public class LRUCache {

    LinkedHashMap<Integer, Integer> map = null;
    private final int CAPACITY;
 
    public LRUCache(int capacity) {
         CAPACITY = capacity;
        map = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true){
                protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                    return size() > CAPACITY;
                }
        };
    }
 
    public int get(int key) {
        return map.getOrDefault(key, -1);
    }
 
    public void put(int key, int value) {
        map.put(key,value);
    }
     
}

Sol#2:

LinkedHashMap<Integer, Integer> map = new LinkedHashMap<Integer, Integer> ();

public int get(int key) {
    if(map == null || map.get(key) == null) return -1;
    int value = map.get(key);
    map.remove(key); 
    map.put(key, value);
    return value;
}
   
public void set(int key, int value) {
    if(map == null) return;
    get(key);
    map.put(key, value);
}

Sol#3:

class LRUCache extends LinkedHashMap<Integer, Integer>{
    int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }
    
    public int get(int key) {
        return super.getOrDefault(key, -1);
    }
    
    public void put(int key, int value) {
        super.put(key, value);
    }
    
    
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest){
        return size()>capacity;
    }
}