使用双向链表+map，实现O(1)时间内的get和set

需要注意的是：

1. set时更新tail

size为0时更新头部

size为capacity时删除头部并且更新头部

2. get时更新节点到tail的位置，同时如果是节点是头部的话要更新头部

附上代码：

class LRUCache{
    struct Node{
        int key;
        int val;
        Node* next;
        Node* pre;
        
        Node(int k, int v)
        {
            key = k;
            val = v;
            next = pre = NULL;
        }
    };
    
    Node * head;
    Node * tail;
    int size;
    int cap;
    map<int, Node*> keyMap;
public:
    LRUCache(int capacity) {
        head = tail = NULL;
        cap = capacity;
        size = 0;
        keyMap = map<int, Node*>();
    }
    
    ~LRUCache(){
        while (head)
        {
            Node * deleteNode = head;
            head = head->next;
            delete deleteNode;
        }
    }
    
    Node * getNode(int key)
    {
        if (keyMap.find(key) == keyMap.end())
            return NULL;
        Node* foundNode = keyMap[key];
        if (size == 1 || foundNode == tail) return foundNode;
        if (foundNode == head)//size > 1, foundNode->next is not NULL
            head = foundNode->next;
        //remove foundNode from list
        foundNode->next->pre = foundNode->pre;
        if (foundNode->pre) foundNode->pre->next = foundNode->next;
        //update tail
        tail->next = foundNode;
        foundNode->pre = tail;
        tail = tail->next;
        //update foundNode
        foundNode->next = NULL;
        return foundNode;
    }
    
    int get(int key) {
        Node * foundNode = getNode(key);
        if (foundNode)  return foundNode->val;
        else            return -1;
    }
    
    void set(int key, int value) {
        Node * foundNode = getNode(key);//put Node to the front of list
        //if key exists, update value
        if (foundNode)
        {
            foundNode->val = value;
            return;
        }
        //if key not exists, create Node
        Node * newNode = new Node(key, value);
        keyMap[key] = newNode;
        if (size == 0)
            tail = head = newNode;
        else
        {
            tail->next = newNode;
            newNode->pre = tail;
            tail = tail->next;
        }
        size++;
        //check if need delete
        if (size <= cap) return;
        Node * deleteNode = head;
        head = head->next;
        head->pre = NULL;
        keyMap.erase(deleteNode->key);
        delete deleteNode;
        size--;
    }
};

这是我第一次写的时候的代码：

class LRUCache{
public:
	struct Node
	{
		int value;
		int key;
		Node * next;
		Node * pre;
		Node(int v, int k)
		{
			value = http://www.mamicode.com/v;>

LRU Cache [leetcode]