Leetcode 146. 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.

Thinking:

LRU(Least Recently Used) is a algorithm for cache using main storage efficiently, in which new data replace data in storage locations that have not been accessed for the longest period. In other words, the cache will delete the least recently used data once the cache reach the capacity.
We should think a data structure that can restore the least-recently-used data. Which can be LinkedList/Array/ArrayList. However, the LinkedList can achieve the O(1) insert and delete. So we choose LinkedList, specially, double Linkedlist(which can delete itself by itself). Also, we need a map to store key and value. So we also need a HashMap.

Complexity:

The operation of set and get is O(1). And the space complexity is O(n), since we use a HashMap and Double LinkedList.

Steps:

Using double Linkedlist to store the data. Using Hashmap for searching.
For the get(key)(), check whether Hashmap contains this key. If not, return -1. If yes return value, and put this key in the head.
For the ```set(key, value), check whether hashmap contian this key. If yes, put it in head. If not, check whether it reach the capacity. If not, remove the least used data first and then put the new node in the head. If not, remove the node and put it in the head.

Code:

class ListNode{
    int key;
    int value;
    ListNode prev;
    ListNode next;
    public ListNode(int key, int value){
        this.key = key;
        this.value = value;
    }
}
public class LRUCache {
    int capacity;
    HashMap<Integer, ListNode> map;
    ListNode head;
    ListNode tail;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        head = new ListNode(0,0);
        tail = new ListNode(0,0);
        head.next = tail;
        tail.prev = head;
        head.prev = null;
        tail.next = null;
    }

    public int get(int key) {
        if(map.containsKey(key)){
            remove(map.get(key));
            addToHead(map.get(key));
            return map.get(key).value;
        }
        else{
            return -1;
        }
    }

    public void set(int key, int value) {
        if(map.containsKey(key)){
            ListNode node = map.get(key);
            node.value = value;
            remove(node);
            addToHead(node);
        }
        else{
            ListNode node = new ListNode(key,value);
            if(map.size() == capacity){
                map.remove(tail.prev.key);
                remove(tail.prev);
            }
            addToHead(node);
            map.put(key,node);
        }
    }
    private void addToHead(ListNode node){
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
        node.prev = head;
    }
    private void remove(ListNode node){
        node.next.prev = node.prev;
        node.prev.next = node.next;
    }
}

Conclusion:

Though we define a head and a tail. But actually, we only insert the node between them. It's like a dummy node in one-direction Linkedlist, which can store the head and tail of the list.

Leetcode 146. LRU Cache