LRUCache.java

package com.learning.leet.problems;

import java.util.HashMap;
import java.util.Map;

/**
 * Created by sargonbenjamin on 7/17/19.
 * https://leetcode.com/problems/lru-cache/
 */
public class LRUCache {
    int capacity = 0;
    CacheNode head;
    CacheNode tail;
    Map<Integer, CacheNode> map;


    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>(capacity);

        this.capacity = capacity;
    }

    public int get(int key) {
        if(!map.containsKey(key))return -1;
        CacheNode curr = map.get(key);
        put(curr.key,curr.value);
        return curr.value;
    }

    public void put(int key, int value) {
        CacheNode curr;
        if(tail==null){
            tail = new CacheNode(key, value);
            head = tail;
            curr = tail;
        }else if(map.containsKey(key)){
            curr = map.get(key);
            curr.prev.next = curr.next;
            curr.next.prev = curr.prev;
            curr.prev = tail;
            tail.next = curr;
            tail = curr;
        }else if(map.size()<this.capacity){
            curr = promote(key,value);
        }else {
            //first remove head
            map.remove(head.key);
            CacheNode tmp = head.next;
            head.next = null; //garbage collection
            head = tmp;
            head.prev = null;
            curr = promote(key,value);
        }

        map.put(curr.key,curr);
    }

    public CacheNode promote(int key, int value){
        CacheNode curr = new CacheNode(key, value);
        curr.prev = tail;
        tail.next = curr;
        tail = curr;
        return curr;
    }

    class CacheNode {
        int key;
        int value;
        CacheNode prev;
        CacheNode next;

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

}