LRU(leetcode.146)

146. LRU 缓存机制
先贴代码：

struct LRUNode
{
    int _key, _val;
    LRUNode* _pre, *_next;
    LRUNode(int k, int v) : _key(k), _val(v), _next(NULL), _pre(NULL) { }
};
class LRUCache {
public:
    LRUCache(int capacity) {
        _capacity = capacity;
        // 伪头、尾指针
        _head = new LRUNode(-1, 0), _tail = new LRUNode(-1, 0);
        _head->_next = _tail;
        _tail->_pre = _head;
        um.clear();
    }

    int get(int key) {
        // key 存在
        if (um.count(key))
        {
            int res = um[key]->_val;
            dele(um[key]);
            insert(um[key]);
            return res;
        }
        // 否则返回-1
        return -1;
    }

    void dele(LRUNode* node)
    {
        node->_pre->_next = node->_next;
        node->_next->_pre = node->_pre;
    }

    void insert(LRUNode* node)
    {
        node->_next = _head->_next;
        node->_pre = _head;
        _head->_next->_pre = node;
        _head->_next = node;
        return;
    }

    void put(int key, int value) 
    {
        if (um.count(key))
        {
            LRUNode* node = new LRUNode(key, value);
            dele(um[key]);
            insert(node);
            um[key] = node;
            return;
        }
        if (um.size() >= _capacity)
        {
            LRUNode* tmp = _tail->_pre;
            um.erase(_tail->_pre->_key);
            dele(_tail->_pre);
            delete tmp;
            tmp = NULL;
        }
        LRUNode* node = new LRUNode(key, value);
        insert(node);
        um[key] = node;
    }
private:
    LRUNode* _head, *_tail;
    unordered_map<int, LRUNode*> um;
    int _capacity;
};

解析：
首先为了防止一些空指针的问题，先初始化两个伪指针，分别为头指针和尾指针，也即初始的链表为

初始链表
每个节点都是一个LRUNode，包含了该节点存放的key、value以及前向、后向指针
此外，还维护了一个unordered_map用来标识某个key值是否存在，对应的value为一个LRUNode
首先维护两个insert和dele函数，前者用于将某个node插入链表队首（伪头指针后），后者用于将某个node“删除”，即若A->B->C，删除B，则A->C(C->A)，但此时不能真正delete B，因为后续还要通过insert将其插入队首
每当调用put函数，首先检查该key值是否存在，若存在，直接替换value值，并将其“挪”到队首，即先将其从原队列"删除"，后挪至队首：
将nodeB挪至队首
由于维护了一个双向链表，因此只需令

node->_pre->_next = node->_next; // A->C
node->_next->_pre = node->_pre;  // C->A

此时不delete node B，而是通过insert插入到队首：

node->_next = _head->_next;
node->_pre = _head;
_head->_next->_pre = node;
_head->_next = node;

这样链表就变成_head->B->A->C->_tail
若put时key不存在，即需要新插入一个node，则需要判断当前链表容量与可用容量的大小，如果仍有可用容量，只需直接调用insert将新node 插入队首
如果已满，则需要把队尾的node先delete（注意此时是真正的删除，因此除了调用dele，还需要delete该node节点并置NULL防止内存泄漏），后将新node插入队首
调用get时则直接判断key值是否存在，并返回对应的值即可