.net - What data structure should I use for this caching strategy? - Programmers Stack Exchange

.net - What data structure should I use for this caching strategy? - Programmers Stack Exchange

If you wan to use a LRU eviction cache (Least Recently Used eviction), then probably a good combination of data structures to use is:

• Circular linked list (as a priority queue)
• Dictionary

This is why:

• The linked list has a O(1) insertion and removal time
• List nodes can be reused when the list is full and no extra allocations need to be performed.

This is how the basic algorithm should work:

The data structures

LinkedList<Node<KeyValuePair<Input,Double>>> list; Dictionary<Input,Node<KeyValuePair<Input,Double>>> dict;

1. Input is received
2. If the dictionary contains the key
   • return the value stored in the node and move the node to the beginning of the list
3. If the dictionary does not contain the key
   • compute the value
   • store the value in the last node of the list
   • if the last not has a value, remove the previous key from the dictionary
   • move the last node to first position.
   • store in the dictionary the (input, node) key value pair.

Read full article from .net - What data structure should I use for this caching strategy? - Programmers Stack Exchange