Leetcode 146.LRU缓存机制（哈希表+双向链表，纯手动实现）

解题思路：考数据结构的一道题，除了记录当前cache内的<key-value>对外，还要记录使用信息。这里采用哈希表+双向链表的方法，双向链表中存放cache的内容，哈希表存放对应的key和指向对应结点的指针。考点在于双向链表的手动实现+链表操作（头插法···）

//哈希表+双向链表
public class LRUCache {
    class DeLinkedNode{
        int key;    //删除结点时使用
        int value;
        DeLinkedNode prev;
        DeLinkedNode next;
        public DeLinkedNode(){} //构造函数
        public DeLinkedNode(int _key, int _value){key = _key; value = _value;}
    }

    Map<Integer, DeLinkedNode> dic = new HashMap<Integer, DeLinkedNode>();
    int size;
    int capacity;
    DeLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;

        //创建空的头尾节点
        head = new DeLinkedNode();
        tail = new DeLinkedNode();
        head.next = tail;
        head.prev = tail;
        tail.next = head;
        tail.prev = head;
    }
    
    public int get(int key) {
        //1.在哈希表中寻找目标key
        DeLinkedNode node = dic.get(key);
        
        //2.若为空，则不存在该key，返回-1
        if (node == null) {
            return -1;
        }
        
        //3.若该key存在，将该value指向的node移到链表头部
        node.prev.next = node.next;
        node.next.prev = node.prev;

        //头插法
        headInsert(head, node);

        return node.value;
    }
    
    public void put(int key, int value) {
        //1.在哈希表中寻找目标key，若存在，则更新其数据值
        DeLinkedNode node = dic.get(key);

        if (node != null) {
            node.value = value;
            node.prev.next = node.next;
            node.next.prev = node.prev;

            //头插法
            headInsert(head, node);
        }else{

            node = new DeLinkedNode(key, value);
            dic.put(key,node);

            if(size<capacity){
                //容量未满时，头插法直接插入，size+1
                headInsert(head, node);
                size++;
            }else{
                //容量已满，将tail.prev指向的结点删去再插入
                int delKey = tail.prev.key;
                tail.prev = tail.prev.prev;
                tail.prev.next = tail;
                //从哈希表中删除
                dic.remove(delKey);

                headInsert(head, node);
            }
        }
    }

    //头插法
    private void headInsert(DeLinkedNode head, DeLinkedNode node){
        node.next = head.next;
        node.next.prev = node;
        node.prev = head;
        head.next = node;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */