LRU Cache [Leetcode]

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Solution: we note that each time we visit a page, this page will become the most recently visited page. We use a singly linked list to maintain the pages in the memory; the first and last pages in the list are the least and most recently visited pages respectively; A hashtable is used to record the key of each page and the address of the previous page in the list. Here I used singly linked list, I think it would be better if we use doubly linked list.

class LRUCache{
private:
    struct Cache{
        int key, val;
        Cache* next;
        Cache(int k, int v):key(k),val(v),next(NULL) {}
    };
    Cache* head;
    Cache* tail;
    unordered_map<int, Cache*> hashTable;
    int cap;
public:
    LRUCache(int capacity):head(NULL),tail(NULL),hashTable(),cap(capacity) {
    }
    
    int get(int key) {
        if(hashTable.find(key)==hashTable.end())
            return -1;
        else{
            //if there is only one page in the cache, or the visited page is the last one
            if(head==tail || hashTable[key]!=NULL && hashTable[key]->next==tail)
                return tail->val;
            Cache* tmp = NULL;
            //if the visited page is the first one
            if(hashTable[key]==NULL){
                tmp = head;
                head = head->next;
                hashTable[head->key]=NULL;
            }
            //if the visited page is in the middle of the list
            else{
                tmp = hashTable[key]->next;
                hashTable[tmp->next->key]=hashTable[key];
                hashTable[key]->next = tmp->next;
            }
            //move the visited page to the end of the list
            tail->next=tmp;
            tmp->next=NULL;
            hashTable[key]=tail;
            tail=tail->next;
            return tail->val;
        }
    }
    
    void set(int key, int value) {
        if(get(key)!=-1)
            tail->val=value;
        else{
            Cache* newNode = new Cache(key, value);
            if(head==NULL){
                head=newNode;
                tail=newNode;
                hashTable[key]=NULL;
            }
            else{
                hashTable[key]=tail;
                tail->next=newNode;
                tail=tail->next;
            }
            //overflow; need to remove the least recently visited page
            if(hashTable.size()>cap){
                Cache* tmp = head;
                hashTable.erase(head->key);
                head = head->next;
                hashTable[head->key]=NULL;
                delete tmp;
                tmp=NULL;
            }
        }
    }
};

Here we use doubly linked list.

class LRUCache{
private:
    struct CacheNode{
        int key, val;
        CacheNode(int k, int v):key(k),val(v) {}
    };
    list<CacheNode> cache;
    unordered_map<int, list<CacheNode>::iterator> hashTable;
    int cap;
public:
    LRUCache(int capacity):cache(),hashTable(),cap(capacity) {
    }
    
    int get(int key) {
        if(hashTable.find(key)==hashTable.end())
            return -1;
        else{
            cache.splice(cache.end(), cache, hashTable[key]);
            hashTable[key]=(--cache.end());
            return hashTable[key]->val;
        }
    }
    
    void set(int key, int value) {
        if(get(key)!=-1)
            hashTable[key]->val=value;
        else{
            cache.push_back(CacheNode(key, value));
            hashTable[key]=(--cache.end());
            if(cache.size()>cap){
                hashTable.erase(cache.front().key);
                cache.pop_front();
            }
        }
    }
}; 

Here we use doubly linked list. The idea is similar to the above; the difference is that the first and last pages in the list are the most and least recently visited pages respectively;

class LRUCache{
private:
    struct CacheNode{
        int key, val;
        CacheNode(int k, int v):key(k),val(v) {}
    };
    list<CacheNode> cache;
    unordered_map<int, list<CacheNode>::iterator> hashTable;
    int cap;
public:
    LRUCache(int capacity):cache(),hashTable(),cap(capacity) {
    }
    
    int get(int key) {
        if(hashTable.find(key)==hashTable.end())
            return -1;
        else{
            cache.splice(cache.begin(), cache, hashTable[key]);
            hashTable[key]=cache.begin();
            return hashTable[key]->val;
        }
    }
    
    void set(int key, int value) {
        if(get(key)!=-1)
            hashTable[key]->val=value;
        else{
            cache.push_front(CacheNode(key, value));
            hashTable[key]=cache.begin();
            if(cache.size()>cap){
                hashTable.erase(cache.back().key);
                cache.pop_back();
            }
        }
    }
};