146. LRU Cache

[DavidWang1997]

[DavidWang1997]

`class LRUCache {

private int maxCapacity;
private int cap;
private Map<Integer, ListNode> map;
private ListNode head, tail;

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

    head = new ListNode();
    tail = new ListNode();
    head.next = tail;
    tail.prev = head;

}

public int get(int key) {
    ListNode target = map.get(key);

    if(target == null) return -1;

    moveToHead(target);

    return target.val;
}

public void put(int key, int value) {
    ListNode target = map.get(key);

    if(target != null){
        target.val = value;
        map.put(key, target);
        removeFromList(target);
        addToHead(target);
        return;
    }

    if(cap == maxCapacity) removeLast();

    target = new ListNode();

    target.val = value;
    target.key = key;

    addToHead(target);

    map.put(key,target);

    cap++;

}

private void removeLast(){
    ListNode node = tail.prev;
    ListNode prev = node.prev;
    map.remove(node.key);
    prev.next = tail;
    tail.prev = prev;
    cap --;
}

private void moveToHead(ListNode node){
    removeFromList(node);
    addToHead(node);
}

private void removeFromList(ListNode node){
    ListNode prev = node.prev;
    ListNode next = node.next;

    prev.next = next;
    next.prev = prev;
}

private void addToHead(ListNode node){
    ListNode next = head.next;

    head.next = node;

    node.next = next;
    node.prev = head;

    next.prev = node;
}

private class ListNode{
    int val;
    int key;
    ListNode prev;
    ListNode next;
}

}

/**

• Your LRUCache object will be instantiated and called as such:
• LRUCache obj = new LRUCache(capacity);
• int param_1 = obj.get(key);
• obj.put(key,value); */`

[DavidWang1997]