复习LRU算法，落实到代码加深一下印象

import java.util.HashMap;

/**
 * 手写LRU算法
 * @param <K>
 * @param <V>
 */
public class LRU<K,V> {

    private class Node {
        // 前结点
        private Node prev;
        // 后结点
        private Node next;
        // 键
        private K key;
        // 值
        private V value;
    }

    // 队列头尾
    private Node head, tail;
    // 队列长度
    private int capacity;
    // 存储结点
    private HashMap<K, Node> map = new HashMap<>();

    // 构造函数初始化
    public LRU(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>(capacity);
    }

    // 存储键值
    public void put(K k, V v){
        Node node = map.get(k);
        if (node != null) {
            node.value = v;
            // 移动到队首
            moveToHead(node);
        }else {
            node = new Node();
            node.key = k;
            node.value = v;
            // 超过阈值，移除队尾
            if (map.size() == capacity) {
                removeTail();
            }
            // 新增放到队首
            addToHead(node);
            map.put(k,node);
        }
    }

    // 根据key获取值
    public V get(K k) {
        Node node = map.get(k);
        if (node == null) {
            return null;
        }
        // 移动到队首
        moveToHead(node);
        return node.value;
    }

    // 将结点移动到队首
    public void moveToHead(Node node) {
        if (node == head) {
            return;
        }else if (node == tail) {
            tail.prev.next = null;
            tail = tail.prev;
        }else {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        node.prev = head.prev;
        node.next = head;
        head.prev = node;
        head = node;
    }

    // 添加结点到队首
    public void addToHead(Node node) {
        if (map.isEmpty()) {
            head = node;
            tail = node;
        }else {
            node.next = head;
            head.prev = node;
            head = node;
        }
    }

    // 移除队尾
    public void removeTail() {
        map.remove(tail.key);
        Node prev = tail.prev;
        if (prev != null) {
            prev.next = null;
            tail = prev;
        }
    }

    @Override
    public String toString() {
        return map.keySet().toString();
    }

    public static void main(String[] args) {
        LRU<String, String> lru = new LRU<>(3);
        lru.put("a","a");
        lru.put("b","b");
        lru.put("c","c");
        lru.put("d","d");
        System.out.println(lru.toString());
        // 输出[d,c,b]
    }
}