LRU算法的实现

LRU（Least Recently Used）

      最近最久未使用。其原理就是当数据在最近一段时间经常被访问，那么它在以后也会经常被访问。换句话说我们需要然其能够快速命中经常访问的数据，而不常访问的数据且超出限度的数据我们需要将其淘汰。

      看了一些网上的实现方案，感觉好多代码写的都有点问题，但是实现思路基本没啥问题。我是用链表+hashmap的方式进行编写的。

思路

1 构建双向链表
2 get操作 将本节点进行截取，然后移动到头部
3 put 操作

public class LRUCache {
    
    private Integer capacity;

    private Map<Integer, ListNode> nodeMap = new HashMap<>();

    private ListNode head;

    private ListNode tail;

    public LRUCache(Integer capacity) {
        this.capacity = capacity;
        head = new ListNode();
        tail = new ListNode();
        head.pre = null;
        head.next = tail;
        tail.pre = head;
        tail.next = null;
    }

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

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

        public ListNode() {
        }
    }


    public int get(int key) {
        // write your code here
        ListNode a = nodeMap.get(key);
        if (a == null) {
            return -1;
        }

        //截断
        a.pre.next = a.next;
        a.next.pre = a.pre;

        //放到头
        a.next = head.next;
        head.next.pre = a;
        head.next = a;
        a.pre = head;

        return a.value;
    }

    public void set(int key, int value) {
        // write your code here
        //1 -判断是否存在
        if (get(key) != -1) {
            nodeMap.get(key).value = value;
            return;
        }

        //2 - 判断是否超出容量 删除对列尾巴
        if (nodeMap.size() >= capacity) {

            nodeMap.remove(tail.pre.key);
            tail.pre = tail.pre.pre;
            tail.pre.next = tail;
        }

        ListNode b = new ListNode(key, value);
        nodeMap.put(key, b);

        ListNode a = nodeMap.get(key);
        a.next = head.next;
        head.next.pre = a;
        head.next = a;
        a.pre = head;
        


    }
}```
测试地址 ：https://www.lintcode.com/problem/lru-cache/description