Thinking process - hash table + doubly linked list

1. use a doubly linked list to remember all the key value pairs
2. get()
   1. delete the one
   2. add it to the head
3. insert()
   1. check whether it's gonna be larger than capacity
   2. update the value
   3. delete and then add to the head

Mistakes

count?

only remove least using one when reaches to the capacity AND it's a insert not update!!!!

don't delete the key int if you gonna use it afterwards

class Node {
    public Node prev;
    public Node next;
    public int key;
    public int value;
    public Node (int k, int v) {
        this.key = k;
        this.value = v;
    }
}

public class LRUCache {
    private int capacity;
    private int count;
    private HashMap<Integer, Node> map;
    private Node dummyHead;
    private Node dummyTail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.count = 0;
        map = new HashMap<>();
        dummyHead = new Node(0, 0);
        dummyTail = new Node(0, 0);

        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
    }

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

    public void put(int key, int value) {

        if (map.containsKey(key)) {
            deleteNode(map.get(key));
            map.remove(key);
        } else {
            if (count == capacity) {
                map.remove(dummyTail.prev.key);
                deleteNode(dummyTail.prev);
            } else {
                count++;
            }
        }

        Node node = new Node(key, value);
        map.put(key, node);
        addToHead(node);
    }

    private void deleteNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

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

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

        dummyHead.next = node;
        node.prev = dummyHead;
    }
}