LRU算法的实现

// LRU算法的实现
public class LRU<K,V> {
    // 集合中元素的个数
    private int currentCacheSize;
    // 集合容量
    private int cacheCapcity;
    // 用HashMap是为了获取更快
    private HashMap<K,Node> caches;
    // 记录头部
    private Node head;
    // 记录尾部
    private Node tail;

    // 构造方法
    public LRU(int size) {
        currentCacheSize = 0;
        cacheCapcity = size;
        caches = new HashMap<K,Node>(size);
    }
    // 增加一个元素
    public void put(K k,V v) {
        // 先获取看看有没有
        Node node = caches.get(k);
        // 没有
        if (node == null) {
            // 看看容量是否满了
            if (caches.size() >= cacheCapcity) {
                // 满了就将最后一个元素移出HashMap集合
                caches.remove(tail.key);
                // 移除map还不够 还要从链表中移除
                removetail();
            }
            // 如果集合还没满，那么就构造这样一个节点
            node = new Node();
            node.key = k;
        }
        // 设置node的值 这里注意：如果集合中存在node 以下操作就是覆盖value
        // 不存在的话就是赋值
        node.value = v;
        // 将这个node放到链表队头
        moveTohead(node);
        // 放入HashMap
        caches.put(k,node);
    }

    public Object get(K k){
        Node node = caches.get(k);
        if (node == null) {
            return null;
        }
        // 获取命中后要放到链表头部去
        moveTohead(node);
        return node.value;
    }

    private void moveTohead(Node node) {
        // 如果是第一个节点 那么就直接返回了
        if (head == node) {
            return;
        }
        // 接下来俩次操作就是为了把该节点移除
        if (node.next != null) {
            node.next.pre = node.pre;
        }
            node.pre.next = node.next;

        if (node == tail) {
            tail = tail.pre;
        }
        // 如果头节点和尾节点都没有设置 那么就设置为当前的节点
        if (head == null || tail == null) {
            head = tail = node;
            return;
        }
        // 将头节点赋值新的节点为头节点
        node.next = head;
        // 先将当前节点放到头节点前面
        head.pre = node;
        // 再将当前节点赋值为头节点
        head = node;
        // 再将头节点的前驱置空
        head.pre = null;
    }

    // 如果满了 那就将最后一个清理掉
    private void removetail() {
        if (tail != null) {
            // 将尾指针向前挪一位
            tail = tail.pre;
            if (tail == null) {
                head = null;
            } else {
                tail.next = null;
            }
        }
    }

    // 清空
    public void clear() {
        // 将指向链表的指针置空
        head = null;
        tail = null;
        // 调用HashMap的清空
        caches.clear();
    }

    class Node{
        Node pre;
        Node next;
        Object key;
        Object value;
    }
}