$leetcode 146 题 : lru 模拟实现$
$lru : Least Recently Used，$
$即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。$

class LRUCache {
public:
    struct Node{
        int key, val;
        Node *l, *r;
        Node(int key, int val){
            this -> key = key;
            this -> val = val;
            l = NULL; r = NULL;
        }
    };

    int n;
    unordered_map<int, Node*>d;
    Node *head, *end;

    LRUCache(int capacity) {
        n = capacity;
        head = new Node(-1, -1);
        end = new Node(-1, -1);
        head -> r = end;
        end -> l = head; 
    }

    // 移除
    void remove(Node *cur){
        cur -> l -> r = cur -> r;
        cur -> r -> l = cur -> l;
    }

    // 插入到最左边, 表示是最新被使用的, 越靠近左说明最新被使用过
    void insert(Node* cur){
        cur -> l = head;
        cur -> r = head -> r;
        head -> r = cur;
        cur -> r -> l = cur;
    }

    int get(int key) {
        // 哈希表中有, 取出, 并将结点移到双链表最左边
        if(d.count(key)){
            Node *cur = d[key];
            remove(cur);
            insert(cur);
            return cur -> val;
        } else return -1;  // 哈希表中没有, 直接返回-1
    }

    void put(int key, int value) {
        // 哈希表中有相同的key, 更新一下value, 并将这个结点放到双链表的最左边, 表示最新被使用的
        if(d.count(key)){
            Node* cur = d[key];
            cur -> val = value;
            remove(cur);
            insert(cur);
        } else {
            // 没有key的话插入, 先看容量是否已经满了, 满了则删除最旧的一个
            if(d.size() == n){
                d.erase(end -> l -> key);
                remove(end -> l);
            }
            // 插入到最左边, 表示最新的
            Node* cur = new Node(key, value);
            d[key] = cur;
            insert(cur);
        }
    }
};

/**
 * 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);
 */