Implementing an LRU Cache in C#

Introduction

An LRU (Least Recently Used) Cache is a data structure that stores a limited number of items and ensures that the least recently used items are removed first when the cache reaches its capacity. This article explains the implementation of an LRU Cache in C# using a combination of a dictionary and a doubly linked list.

Implementation Details

The LRUCache class uses a dictionary for O(1) time complexity for get and put operations and a doubly linked list to maintain the order of usage.

Below are the two approaches to implementing LRU cache.

Manual Doubly Linked List

In an LRU Cache, the Manual Doubly Linked List approach is used to maintain the order of usage of cache items. When an item is accessed via the Get method or added/updated via the Put method, it is moved to the end of the list. This ensures that the most recently used items are always at the end, and the least recently used items are at the beginning, ready to be evicted when necessary.

public class LRUCache
{
    int Capacity;
    IDictionary<int, LRUNode> keyValuePairs;
    LRUNode head;
    LRUNode tail;

    public LRUCache(int capacity)
    {
        Capacity = capacity;
        keyValuePairs = new Dictionary<int, LRUNode>();
        head = new LRUNode(0, 0);
        tail = new LRUNode(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    private void MoveToTail(LRUNode node)
    {
        RemoveNode(node);
        AddToTail(node);
    }

    private void RemoveNode(LRUNode node)
    {
        node.next.prev = node.prev;
        node.prev.next = node.next;
    }

    private void AddToTail(LRUNode node)
    {
        node.next = tail;
        node.prev = tail.prev;
        tail.prev.next = node;
        tail.prev = node;
    }

    public int Get(int key)
    {
        if (keyValuePairs.TryGetValue(key, out LRUNode node))
        {
            MoveToTail(node);
            return node.value;
        }
        return -1;
    }

    public void Put(int key, int value)
    {
        if (!keyValuePairs.TryGetValue(key, out LRUNode node))
        {
            if (keyValuePairs.Count == Capacity)
            {
                LRUNode lru = head.next;
                RemoveNode(lru);
                keyValuePairs.Remove(lru.key);
            }
            LRUNode newNode = new LRUNode(key, value);
            keyValuePairs[key] = newNode;
            AddToTail(newNode);
        }
        else
        {
            node.value = value;
            MoveToTail(node);
        }
    }
}

public class LRUNode
{
    public int key;
    public int value;
    public LRUNode prev;
    public LRUNode next;

    public LRUNode(int key, int value)
    {
        this.key = key;
        this.value = value;
    }
}

The Manual Doubly Linked List approach is a powerful technique for implementing an LRU Cache, providing efficient and controlled management of cache items. By manually handling the nodes and their connections, this approach ensures optimal performance for cache operations, making it suitable for high-performance applications where caching is critical.

Inbuilt LinkedList in C#

The LRUCacheDLL class implements a Least Recently Used (LRU) Cache using a combination of a Dictionary and a LinkedList. This approach ensures that both the Get and Put operations have a time complexity of O(1).

Class Members

1. capacity: An integer that defines the maximum number of items the cache can hold.
2. keyValuePairs: A dictionary that maps keys to their corresponding nodes in the linked list. This allows for O(1) access to the nodes.
3. dll: A doubly linked list that maintains the order of usage of the cache items. The most recently used items are at the end of the list, and the least recently used items are at the beginning.

Constructor

public LRUCacheDLL(int capacity)
{
    this.capacity = capacity;
    keyValuePairs = new Dictionary<int, LinkedListNode<(int key, int value)>>();
    dll = new LinkedList<(int key, int value)>();
}