Is this algorithm implementation LRU or MRU?

Question

I am working on implementing a MRU(Most Recently Used) cache in my project using C#.

I googled some conceptions and implementations about MRU, and its contrary, LRU(Least Recently Used), and found this article http://www.informit.com/guides/content.aspx?g=dotnet&seqNum=626 that describes the implementation of MRU collection in C#.

To confuse me is that I think this implementation is LRU rather than MRU. Could anyone help me to confirm this collection class is MRU or not?

Following code block is the whole MRUCollection class. Thanks.

class MruDictionary<TKey, TValue>
{
    private LinkedList<MruItem> items;
    private Dictionary<TKey, LinkedListNode<MruItem>> itemIndex;
    private int maxCapacity;
    public MruDictionary(int cap)
    {
        maxCapacity = cap;
        items = new LinkedList<MruItem>();
        itemIndex = new Dictionary<TKey, LinkedListNode<MruItem>>(maxCapacity);
    }
    public void Add(TKey key, TValue value)
    {
        if (itemIndex.ContainsKey(key))
        {
            throw new ArgumentException("An item with the same key already exists.");
        }
        if (itemIndex.Count == maxCapacity)
        {
            LinkedListNode<MruItem> node = items.Last;
            items.RemoveLast(); //Why do we move the last than first here? The node accessed recently is moved to the front of list.
            itemIndex.Remove(node.Value.Key);
        }
        LinkedListNode<MruItem> newNode = new LinkedListNode<MruItem>(new MruItem(key, value));
        items.AddFirst(newNode);
        itemIndex.Add(key, newNode);
    }
    public bool TryGetValue(TKey key, out TValue value)
    {
        LinkedListNode<MruItem> node;
        if (itemIndex.TryGetValue(key, out node))
        {
            value = node.Value.Value;
            items.Remove(node);
            items.AddFirst(node);
            return true;
        }
        value = default(TValue);
        return false;
    }
}

class MruItem
{
    private TKey _key;
    private TValue _value;
    public MruItem(TKey k, TValue v)
    {
        _key = key;
        _value = v;
    }
    public TKey Key
    {
        get { return _key; }
    }
    public TValue Value
    {
        get { return _value; }
    }
}

---

http://en.wikipedia.org/wiki/Cache_algorithms#Most_Recently_Used
Most Recently Used (MRU): discards, in contrast to LRU, the most recently used items first.

According my understanding, as the node accessed recently is moved to the front of list, if the cache is full, we should remove the first node of list rather than last.

Answer 1

It looks to me like an MRU implementation. Notice how searches start from the beginning of the linked list and go back, and whenever a node is accessed it's moved to the front of the list. In Add(), the node is added using AddFirst(), and in TryGetValue(), it removes the node and adds it to the front of the list.