[Leetcode 146]LRU缓存机制

public class Main {
    public static void main(String[] args) {
        LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1));   // 返回  1
        cache.put(3, 3);    // 该操作会使得密钥 2 作废
        System.out.println(cache.get(2));       // 返回 -1 (未找到)
        cache.put(4, 4);    // 该操作会使得密钥 1 作废
        System.out.println(cache.get(1));       // 返回 -1 (未找到)
        System.out.println(cache.get(3));       // 返回  3
        System.out.println(cache.get(4));       // 返回  4
    }


    private static class LRUCache {
        private HashMap<Integer, Node> map;
        private int size;
        private int capacity;
        private Node head, tail;

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

        public void put(int key, int value) {
            Node node = getNode(key);
            if(node == null) {
                Node curNode = new Node(key, value);
                map.put(key, curNode);
                appendToTail(curNode);
                size++;
                adjustSize();
            } else {
                node.value = value;
            }
        }

        public int get(int key) {
            Node node = getNode(key);
            return node == null ? -1 : node.value;
        }

        private Node getNode(int key) {
            Node node = map.get(key);
            if(node == null) return null;

            if(node != tail) {
                if(node == head) {
                    head = node.next;
                    head.pre = null;
                } else {
                    node.pre.next = node.next;
                    node.next.pre = node.pre;
                }
                appendToTail(node);
            }
            return node;
        }

        // 添加到尾部
        private void appendToTail(Node node) {
            if(size == 0) {
                head = node;
                tail = node;
            } else {
                tail.next = node;
                node.pre = tail;
                node.next = null;
                tail = node;
            }
        }

        private void adjustSize() {
            while(size > capacity) {
                map.remove(head.key);
                head = head.next;
                head.pre = null;
                size--;
            }
        }

        private class Node {
            int key;
            int value;
            Node pre;
            Node next;

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

}