设计LRU 缓存结构

import java.util.*;

/**
 *  LRU 最近最少使用，内存淘汰算法
 */
public class LRUCache {

    // 双向链表， 访问节点，说明使用一次，那么这个节点就移动到头部作为热门数据，其余数据位置不变，尾部就是最近最少使用的节点
    // 怎么插入呢？ 如果缓存为空，那么头插法插入。如果缓存满了，先将尾节点删除，然后插入到头节点后面

    // 双向链表删除尾节点、插入头节点的效率都是O（1）
    // 但是如果我们去访问节点的话，双向链表还是遍历O（N）的复杂度，
    // 所以就可以通过HashMap 记录key（访问值），value(链表的节点)，达到O（1）的效率

    Entry head,tail;// 代表双向链表的头节点和尾节点
    int capacity;// 缓存的大小
    int size;// 实际存储的大小
    Map<Integer,Entry> cache; // 查缓存的哈希表

    public LRUCache(int capacity) {
        // 实际上双向链表中是真正的LRU缓存数据
        initLinkedList();
        this.capacity =capacity;
        this.size=0;
        this.cache = new HashMap<>(capacity);
    }

    // 向缓存中放一个值

    /**
     *
     * @param key , 就是我们要放入的元素 1、2、3、4、5、6
     * @param value ， 就是这个元素 对应的在双向链表中的 一个节点
     */
    public void put(int key,int value){
        // 先查这个key在双向链表中是否存在
        Entry node =cache.get(key);
        if(node!=null){// 说明这个key已经在 linkedList中存在，那么首先更新value
            node.value = value;
            // 删掉这个节点的连接关系，然后移动到头节点
            moveToHead(node);
            return;
        }


        // 删 、 添 都需要 操作（链表+缓存Map）
        if(size==capacity){// 此时内存已经满了,需要将尾节点的元素删除，然后构建新节点插入到头节点后面
            Entry lastNode = tail.pre;
            // 删除链表中的一个元素
            deleteNode(lastNode);
            // 删除缓存中的一个节点
            cache.remove(lastNode.key);
            size--;
        }

        // 此时是内存不满，而且key在链表中不存在的情况,头插法查到头节点后面即可
        Entry newHead = new Entry(key,value);
        addToHead(newHead);
        // 也要添加到缓存中
        cache.put(key, newHead);
        size++;
    }

    public int get(int key){
        Entry node = cache.get(key);
        if(node==null){
            return -1;
        }
        // 因为查询了一次，所以这个node又变成了热点数据，需要先删节点关系，然后移动到头节点后面
        int result = node.value;
        moveToHead(node);
        return result;
    }

    /**
     *  删除最后的尾节点前面的节点即可
     * @param node
     */
    private void deleteNode(Entry node) {
           node.pre.next = tail;
           tail.pre = node.pre;
    }

    private void addToHead(Entry node) {
        node.next = head.next;
        head.next.pre = node;

        head.next = node;
        node.pre = head;
    }

    public void moveToHead(Entry node){
        deleteNode(node);
        addToHead(node);
    }



    // 初始化链表的方法
    private void initLinkedList() {
       this.head = new Entry(0,0);
       this.tail = new Entry(0,0);

       head.next = tail;
       tail.pre = head;
    }

    // 代表双向链表的一个节点
    public static class Entry{
        public Entry pre;
        public Entry next;
        public int key;
        public int value;

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


}