Leetcode 146. LRU 缓存机制（java实现）

原题链接：https://leetcode-cn.com/problems/lru-cache/
解题思路：双向链表+hashmap
代码如下：

// 双向链表
class linkNode{
    int key;
    int val;
    linkNode front; // 前一个结点
    linkNode next;  // 后一个结点
    // 构造函数
    public linkNode(int k,int v){
        this.key=k;
        this.val=v;
    }
}

class LRUCache {
    int capacity; // 容量
    // HashMap,key为key，value为上面定义好的linkNode
    Map map= new HashMap<>();
    linkNode head = new linkNode(0,0); // 头结点
    linkNode tail = new linkNode(0,0); // 尾结点
    // 构造函数
    public LRUCache(int capacity) {
        this.capacity=capacity;
        // 头结点和尾结点先连起来
        head.next=tail;
        tail.front=head;
    }
    
    public int get(int key) {
        // 检查map中是否有key
        if(map.containsKey(key)){
            linkNode node=map.get(key);
            moveNodeToTop(node);
            return node.val;
        }else{
            return -1;
        }

    }
    
    public void put(int key, int value) {
        // 在HashMap中找key
        // 如果找不到
        if(!map.containsKey(key)){
            // 判断map目前的大小是否超过容量
            if(map.size()==capacity){
                // 如果放不下, 要删除最后面的结点
                deleteLastNode();
            }
            // 放进链表前面
            linkNode node=new linkNode(key,value);
            linkNode temp=head.next;
            node.next=temp;
            temp.front=node;
            head.next=node;
            node.front=head;                    
            map.put(key,node); // 将该结点放进HashMap
        }else{ 
        //如果找到了
            linkNode node=map.get(key);
            node.val=value; // 更改value的值
            // 移动到链表前面
            moveNodeToTop(node);
        }
    }

    public void deleteLastNode(){
        linkNode lastNode=tail.front;
        lastNode.next.front=lastNode.front;
        lastNode.front.next=tail;
        // 从map中删除
        map.remove(lastNode.key);

    }

    public void moveNodeToTop(linkNode node){
        // node前后断开并连上，把node拎出来
        node.front.next=node.next;
        node.next.front=node.front;
        // node移动到前面
        linkNode temp=head.next; // 原来的第一个结点
        node.next=temp;
        temp.front=node;
        head.next=node;
        node.front=head;

    }
}