LeetCode: LRU Cache

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.

---

According to Wikipedia, LRU is discarding the least recently used items first. This algorithm requires keeping track of what was used when, which is expensive if one wants to make sure the algorithm always discards the least recently used item. For querying, we need a hashmap to ensure the query time is O(1). And remove the least recently used entry, we can use a doubly linked list to ensure modification in O(1).

C++ Code:

class LRUCache{
public:
    /*
     * struct: CacheEntry
     * desc: to represent each cache entry
     * key: the key for quering
     * value: the actual value needed
     * prev: a pointer pointing to its previous node
     * next: a pointer pointing to its next node
     */
    struct CacheEntry{
        int key;
        int value;
        CacheEntry *prev;
        CacheEntry *next;
        CacheEntry(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
    };
    
    /*
     * func: constructor
     * @param capacity: the number of most nodes the cache can hold
     */
    LRUCache(int capacity){
        this->capacity = capacity;
        curr_size = 0;
        head = nullptr;
        tail = nullptr;
    }
    
    /*
     * func: get
     * goal: get the value based on input key
     * @param key: input key
     * return: value found. If not found, return -1
     */
    int get(int key){
        if(cache_map.find(key) != cache_map.end()){
            CacheEntry *entry = cache_map[key];
            move_to_head(entry);
            return entry->value;
        }else{
            return -1;
        }
    }
    
    /*
     * func: set
     * goal: set the key and value into the cache, if the key is in the
             cache, update the entry. If not, insert it into the cache.
     * @param key: input key
     * @param value: input value
     * return:
     */
    void set(int key, int value){
        if(get(key) != -1){
            CacheEntry *entry = cache_map[key];
            entry->value = value;
            move_to_head(entry);
        }else{
            if(curr_size >= capacity){
                cache_map.erase(tail->key);
                remove_last();
            }else{
                ++curr_size;
            }
            CacheEntry *entry = new CacheEntry(key, value);
            if(curr_size == 1){
                head = entry;
                tail = entry;
            }
            move_to_head(entry);
            cache_map.emplace(key, entry);
        }
    }
private:
    int capacity;
    int curr_size;
    unordered_map<int, CacheEntry*> cache_map;
    CacheEntry *head;
    CacheEntry *tail;
    
    /*
     * func: move_to_head
     * goal: move the input entry to the head of the list
     * @param entry: input entry
     * return:
     */
    void move_to_head(CacheEntry *entry){
        if(entry == head){
            return;
        }
        
        if(entry->prev){
            entry->prev->next = entry->next;
        }
        if(entry->next){
            entry->next->prev = entry->prev;
        }
        
        if(entry == tail){
            tail = entry->prev;
        }
        
        if(head){
            entry->next = head;
            head->prev = entry;
        }
        
        head = entry;
        entry->prev = nullptr;
    }
    
    /*
     * func: remove_last
     * goal: remove the last node in the list
     * return:
     */
    void remove_last(){
        if(tail){
            if(tail->prev){
                tail->prev->next = nullptr;
            }else{
                head = nullptr;
            }
            CacheEntry *garbage = tail;
            tail = tail->prev;
            delete garbage;
            
        }
    }
};

Python Code:

class LRUCache:
    class CacheEntry:
        def __init__(self, k, v):
            self.key = k
            self.value = v
            self.next = None
            self.prev = None
    
    # func: constructor
    # @param capacity: the maximum capacity
    def __init__(self, capacity):
        self.capacity = capacity
        self.curr_size = 0
        self.cache_map = {}
        self.head = None
        self.tail = None

    # func: get the value based on the key
    # @param key: input key
    # return: the value found. If not found, return -1
    def get(self, key):
        if key in self.cache_map:
            entry = self.cache_map[key]
            self.move_to_head(entry)
            return entry.value
        else:
            return -1
    
    # func: set the key and value into the cache, if key is in the cache
    #       update the value. If not, insert it into the cache
    # @param key: input key
    # @param value, input value
    # @return:
    def set(self, key, value):
        if key in self.cache_map:
            entry = self.cache_map[key]
            entry.value = value
            self.move_to_head(entry)
        else:
            if self.curr_size >= self.capacity:
                self.cache_map.pop(self.tail.key)
                self.remove_tail()
            else:
                self.curr_size += 1
            new_entry = self.CacheEntry(key, value)
            if self.curr_size == 1:
                self.head = new_entry
                self.tail = new_entry

            self.cache_map[key] = new_entry
            self.move_to_head(new_entry)

    # func: move the input entry to the head of the list
    # @param entry: input entry
    # @return:
    def move_to_head(self, entry):
        if self.head == entry:
            return

        if entry.prev:
            entry.prev.next = entry.next
        if entry.next:
            entry.next.prev = entry.prev

        if entry == self.tail:
            self.tail = entry.prev
        if self.head:
            entry.next = self.head
            self.head.prev = entry

        self.head = entry
        entry.prev = None

    # func: remove the tail node from the list
    # @return:
    def remove_tail(self):
        if self.tail:
            if self.tail.prev:
                self.tail.prev.next = None
            else:
                self.head = None
            self.tail = self.tail.prev