How to implement Least Recently Used Algorithm using C/C++ ??

Question

How to implement least recent use for the numbers displayed on phone screen ??

Comments

It would be identical to least recently used page replacement algorithm, the only difference would be that you may need to change the page with phone number.

---

LRU can be implemented by using Doubly linked list with nodes also inserted in Hash. Whenever an element is used, use the hash table to get the address of the Node in the linked list, remove it from the doubly linked list and insert at first place. To get the recently used element access first node. To insert new element which is not present in Hash, insert the element at the beginning of the list and then update Hash Table accordingly.

Answer 1

Following is the code for LRU cache in C++, let me know if you need C implementation also.

#include <iostream>
#include <vector>
#include <hash_map>

using namespace std;
using namespace stdext;

template<class K, class T>
struct LRUCacheEntry
{
    K key;
    T data;
    LRUCacheEntry* prev;
    LRUCacheEntry* next;
};

template<class K, class T>
class LRUCache
{
private:
    hash_map< K, LRUCacheEntry<K,T>* >  _mapping;
    vector< LRUCacheEntry<K,T>* >       _freeEntries;
    LRUCacheEntry<K,T> *            head;
    LRUCacheEntry<K,T> *            tail;
    LRUCacheEntry<K,T> *            entries;
public:
    LRUCache(size_t size){
        entries = new LRUCacheEntry<K,T>[size];
        for (int i=0; i<size; i++)
            _freeEntries.push_back(entries+i);
        head = new LRUCacheEntry<K,T>;
        tail = new LRUCacheEntry<K,T>;
        head->prev = NULL;
        head->next = tail;
        tail->next = NULL;
        tail->prev = head;
    }
    ~LRUCache()
    {
        delete head;
        delete tail;
        delete [] entries;
    }
    void put(K key, T data)
    {
        LRUCacheEntry<K,T>* node = _mapping[key];
        if(node)
        {
            // refresh the link list
            detach(node);
            node->data = data;
            attach(node);
        }
        else{
            if ( _freeEntries.empty() )
            {
                node = tail->prev;
                detach(node);
                _mapping.erase(node->key);
                node->data = data;
                node->key = key;
                attach(node);
            }
            else{
                node = _freeEntries.back();
                _freeEntries.pop_back();
                node->key = key;
                node->data = data;
                _mapping[key] = node;
                attach(node);
            }
        }
    }

    T get(K key)
    {
        LRUCacheEntry<K,T>* node = _mapping[key];
        if(node)
        {
            detach(node);
            attach(node);
            return node->data;
        }
        else return NULL;
    }

private:
    void detach(LRUCacheEntry<K,T>* node)
    {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    void attach(LRUCacheEntry<K,T>* node)
    {
        node->next = head->next;
        node->prev = head;
        head->next = node;
        node->next->prev = node;
    }
};