C# LRU cache with Dictionary and LinkedList

The concept

A least-recently-used (LRU) cache keeps a fixed number of entries and evicts the one that has not been used for the longest time. It needs two things to be fast: finding an entry by key, and finding and updating the order of use. A Dictionary gives O(1) lookup by key. A doubly linked list gives O(1) removal from anywhere and O(1) insertion at the ends, if you hold a reference to the node.

The list keeps the most recently used entry at the front. The dictionary maps each key to its list node. A get moves the node to the front. A put either updates and moves an existing node, or adds a new one at the front and, if the capacity is exceeded, removes the node at the back and its dictionary entry. Every operation is O(1). This is the structure behind many in-memory caches.

Code example

using System;
using System.Collections.Generic;

class LruCache {
  private readonly int capacity;
  private readonly Dictionary<int, LinkedListNode<(int Key, int Value)>> map = new Dictionary<int, LinkedListNode<(int Key, int Value)>>();
  private readonly LinkedList<(int Key, int Value)> order = new LinkedList<(int Key, int Value)>();

  public LruCache(int capacity) {
    this.capacity = capacity;
  }

  public int Get(int key) {
    if (!map.TryGetValue(key, out var node)) {
      return -1;
    }
    order.Remove(node);
    order.AddFirst(node);
    return node.Value.Value;
  }

  public void Put(int key, int value) {
    if (map.TryGetValue(key, out var existing)) {
      order.Remove(existing);
      map.Remove(key);
    } else if (map.Count == capacity) {
      var oldest = order.Last;
      order.RemoveLast();
      map.Remove(oldest.Value.Key);
      Console.WriteLine("evicted " + oldest.Value.Key);
    }
    var node = order.AddFirst((key, value));
    map[key] = node;
  }
}

class Program {
  static void Main() {
    var cache = new LruCache(2);
    cache.Put(1, 10);
    cache.Put(2, 20);
    Console.WriteLine(cache.Get(1));
    cache.Put(3, 30);
    Console.WriteLine(cache.Get(2));
    cache.Put(4, 40);
    Console.WriteLine(cache.Get(1) + " " + cache.Get(3) + " " + cache.Get(4));
  }
}

10
evicted 2
-1
evicted 1
-1 30 40

Follow the code

Open the walkthrough to inspect the example one step at a time.

—

—

—

10

10
evicted 2

10
evicted 2
-1

10
evicted 2
-1
evicted 1

10
evicted 2
-1
evicted 1
-1 30 40

Behind the scenes

Cost and common mistakes

Get and Put are O(1); the space is O(capacity).

• If the dictionary and the list disagree, for example an entry removed from one but not the other, the cache returns wrong answers or leaks memory.
• This cache is not thread-safe. Concurrent use needs a lock around each operation.
• LinkedList<T> is a doubly linked list in .NET, which is what makes removal from the middle O(1).

Try it yourself

Why not use a List<T> to keep the order of use?

Further reading

• C# documentation (external)
• .NET API browser (external)
• Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein) (external)