C# LRU cache with Dictionary and LinkedList
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.
C#
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));
}
}