LRU 缓存

双向链表加map

public class LRUCache {

        class LinkNode{
            int key;
            int val;
            LinkNode pre;
            LinkNode next;
            public LinkNode(){}
            public LinkNode(int key,int val){
                this.key = key;
                this.val = val;
            }
        }

        private Map<Integer, LinkNode> mp = new HashMap<Integer, LinkNode>();
        private int capacity;
        private LinkNode head,tail;
        private int size;

        public LRUCache(int capacity) {
            this.capacity = capacity;
            this.size = 0;
            head = new LinkNode();
            tail = new LinkNode();
            head.next = tail;
            tail.next = head;
        }

        public int get(int key) {
            if(mp.get(key) == null) return -1;
            else{
                LinkNode lk = mp.get(key);
                moveToHead(lk);
                return lk.val;
            }
        }

        public void put(int key, int value) {
            if(mp.get(key) == null){
                LinkNode lk = new LinkNode(key, value);
                mp.put(key, lk);
                addToHead(lk);
                size++;

                if(size > capacity){
                    LinkNode res = tail.pre;
                    removeNode(res);
                    mp.remove(res.key);
                    size--;
                }
            }
            else{
                LinkNode lk = mp.get(key);
                lk.val = value;
                moveToHead(lk);
            }
        }


        private void removeNode(LinkNode lk){
            lk.pre.next = lk.next;
            lk.next.pre = lk.pre;
        }

        private void addToHead(LinkNode lk){
            lk.pre = head;
            lk.next = head.next;
            head.next.pre = lk;
            head.next = lk;
        }

        private void moveToHead(LinkNode lk){
            removeNode(lk);
            addToHead(lk);
        }


}

/**
 * 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);
 */