LeetCode 146. LRU缓存

地址：146.LRU缓存

语言Java

class LRUCache {

    //插入删除O(1)，使用双向链表
    class DNode {
        int key;
        int value;
        DNode next;
        DNode pre;

        public DNode(int key, int value, DNode next, DNode pre) {
            this.key = key;
            this.value = value;
            this.next = next;
            this.pre = pre;
        }

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

    private int capacity = 0;

    //随机访问O(1)，使用哈希表
    private HashMap<Integer, DNode> keyMap;

    private DNode dummy;
    private DNode tail;

    private int size = 0;


    public LRUCache(int capacity) {
        this.capacity = capacity;
        keyMap = new HashMap<>();
        dummy = new DNode(-1, -1);
        tail = new DNode(-2, -2);
        dummy.next = tail;
        tail.pre = dummy;
    }
    
    public int get(int key) {
        DNode node = keyMap.getOrDefault(key, null);
        if(node == null) {
            return -1;
        } 

        //移动到链表头
        move2Head(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        DNode node = keyMap.getOrDefault(key, null);

        if(node != null) {
            node.value = value;
            //移动到链表头
            move2Head(node);
        } else {

            if (size + 1 > capacity) {
                //移除最后一个
                removeTail();
            }  else {
                size++;
            }

            //插入到链表头
            DNode newNode = new DNode(key, value);
            insert2Head(newNode);
            keyMap.put(key, newNode);
        }
    }

    private void insert2Head(DNode node) {
        DNode temp = dummy.next;
        dummy.next = node;
        node.pre = dummy;
        node.next = temp;
        temp.pre = node;
    }

    private void move2Head(DNode node) {
        DNode pTemp = node.pre;
        DNode nTemp = node.next;
        pTemp.next = nTemp;
        nTemp.pre = pTemp;

        insert2Head(node);
    }

    private void removeTail() {
        DNode temp = tail.pre;
        if (temp != dummy) {
            DNode pTemp = temp.pre;
            tail.pre = pTemp;
            pTemp.next = tail;
            
            keyMap.remove(temp.key, temp);
            temp.key = -3;
            temp.value = -3;
            temp.pre = null;
            temp.next = null;
        }
    }
}