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)>();
}

1. Purpose: Initializes the cache with a specified capacity.
2. Initialization
   • keyValuePairs is initialized as an empty dictionary.
   • dll is initialized as an empty linked list.

Get Method

public int Get(int key)
{
    if (keyValuePairs.TryGetValue(key, out LinkedListNode<(int key, int value)> node))
    {
        dll.Remove(node);
        dll.AddLast(node);
        return node.Value.value;
    }
    return -1;
}

Purpose: Retrieves the value associated with the specified key.

Steps

1. Check if the key exists in the dictionary.
2. If it exists
   • Removes the node from its current position in the linked list.
   • Adds the node to the end of the linked list to mark it as recently used.
   • Returns the value of the node.
3. If the key does not exist, returns -1.

Put Method

public void Put(int key, int value)
{
    if (keyValuePairs.TryGetValue(key, out LinkedListNode<(int key, int value)> node))
    {
        dll.Remove(node);
        node.Value = (key, value);
        dll.AddLast(node);
    }
    else
    {
        if (keyValuePairs.Count == capacity)
        {
            keyValuePairs.Remove(dll.First.Value.key);
            dll.RemoveFirst();
        }
        keyValuePairs[key] = dll.AddLast((key, value));
    }
}

Purpose: Adds a new key-value pair to the cache or updates an existing key.

Steps

1. Check if the key already exists in the dictionary.
2. If it exists
   • Removes the node from its current position in the linked list.
   • Updates the node’s value.
   • Adds the node to the end of the linked list to mark it as recently used.
3. If the key does not exist.
   • Check if the cache is at capacity.
   • If at capacity
     • Removes the least recently used item (the first node in the linked list).
     • Removes the corresponding entry from the dictionary.
   • Adds the new key-value pair.
     • Creates a new node with the key-value pair.
     • Adds the new node to the end of the linked list.
     • Adds the new node to the dictionary.

The LRUCacheDLL class efficiently manages a fixed-size cache using a combination of a dictionary and a doubly linked list. This implementation ensures that both the Get and Put operations have a time complexity of O(1), making it suitable for high-performance applications. The use of a doubly linked list allows for efficient management of the order of cache items, ensuring that the least recently used items are evicted when the cache reaches its capacity.

Time Complexity

• Get Operation: O(1)
  • The Get method uses the dictionary to find the node in O(1) time and then moves the node to the tail of the linked list, which is also O(1).
• Put Operation: O(1)
  • The Put method checks if the key exists in the dictionary in O(1) time. If the key does not exist and the cache is at capacity, it removes the least recently used node, which is O(1), and then adds the new node, which is also O(1).

Space Complexity

• O(n), where n is the capacity of the cache.
  • The dictionary stores up to n key-value pairs.
  • The doubly linked list stores up to n nodes.

Example Usage

Here’s an example of how to use the LRUCache class.

LRUCache cache = new LRUCache(2);

cache.Put(1, 1);
cache.Put(2, 2);
Console.WriteLine("Get key 1: " + cache.Get(1));
cache.Put(3, 3);
Console.WriteLine("Get key 2: " + cache.Get(2));
cache.Put(4, 4);
Console.WriteLine("Get key 1: " + cache.Get(1));
Console.WriteLine("Get key 3: " + cache.Get(3));
Console.WriteLine("Get key 4: " + cache.Get(4));

In this example, the cache is initialized with a capacity of 2. It stores key-value pairs and evicts the least recently used items when the capacity is exceeded.

Conclusion

The LRUCache class efficiently manages a fixed-size cache using a combination of a dictionary and a doubly linked list. This implementation ensures that both the Get and Put operations have a time complexity of O(1), making it suitable for high-performance applications.