手写LRU Java实现

笔试、面试的常客 - 手写LRU，一般是使用双链表和哈希表来做实现：

class LRUCache {

    int capacity;
    int size;
    Map map = new HashMap<>();
    Node head;
    Node tail;

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

    public int get(int key) {
        Node node = map.getOrDefault(key, null);
        if (node == null) return -1;
        deleteNode(node);
        addNodeAtTail(node);
        return node.val;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            deleteNode(node);
            node.key = key;
            node.val = value;
            addNodeAtTail(node);
            map.put(key, node);
            return;
        }
        if (size == capacity) {
            Node realHead = head.next;
            deleteNode(realHead);
            map.remove(realHead.key);
        } else {
            size++;
        }
        Node node = new Node(value);
        node.key = key;
        addNodeAtTail(node);
        map.put(key, node);
    }

    static class Node {
        int key;
        int val;
        Node pre;
        Node next;
        public Node() {
            this.val = 0;
        }
        public Node(int val) {
            this.val = val;
        }
    }

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

    void addNodeAtHead (Node node) {
        Node next = head.next;
        node.next = next;
        head.next = node;
        node.pre = head;
        next.pre = node;
    }

    void addNodeAtTail (Node node) {
        Node pre = tail.pre;
        node.next = tail;
        pre.next = node;
        node.pre = pre;
        tail.pre = node;
    }
}

在leetcode中可以找到相应的题目：链接