Here is the link.
C# Work on double linked list and learn from mistakes
Sept. 15, 2020
146. LRU Cache
Introduction
I like to take some time to learn how to write a working solution using double linked list written by myself. I started to work on coding, and I plan to make it work first.
Case study
Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]
The idea is to use double linked list so that it is O(1) time complexity to remove a node from double linked list and also insertion.
Second idea is to use a hashmap to save each key and it's pointer in double linked list.
A key has to be removed if it is least used and capacity is reached to upper limit. Also a key is visited by calling Get(int key), the node in the double linked list should be found using O(1) time, and then it is inserted in the double linked list.
To make it easy, recently used should be inserted at the beginning of double linked list, in other words, as a head. I choose to insert in the end of double linked list.
Step by step:
step 1: set double linked list capacity as 2
step 2: [1, 1], insert key and value node(1, 1) object into double linked list as last node or tail node
step 3: [2, 2], insert key and value node(2, 2) object into double linked list as last node or tail node
double linked list:
head tail
1 <-> 2
step 4: [1], get key 1
In the above step 2 and step 3, save each node in double linked list into a hashmap by key value, so it will take O(1) time complexity to find node using key value
Since key 1 is visited, head node with key value 1 will be deleted first, and a new node with key value 1 is added as last node in double linked list.
Do it yourself
I also like to write a double linked list by myself, instead of using dummy head and dummy tail two nodes, I study Microsoft C# LinkedList source code, and I like to copy ideas from LinkedList. Here is the link.
The idea of double linked list design is to use a head node, and then head is connected to tail of double linked list using head.Prev = tail.Next.
There are a few challenges, so that I failed each test case in my code listed as test case 1 and 2 and 3.
I like to try a few ideas to make the implementation easy. Add a new node to the head of double linked list instead, and also extra a double linked list class to include minimum functionalities to make solution work.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace L146_LRU_cache_practice
{
class Program
{
static void Main(string[] args)
{
//RunTestcase1();
//RunTestcase2();
RunTestcase3();
}
public static void RunTestcase1()
{
var cache = new LRUCache(2);
cache.Put(1, 1);
cache.Put(2, 2);
var value = cache.Get(1);
cache.Put(3, 3);
var result = cache.Get(2);
Debug.Assert(result == -1);
cache.Put(4, 4);
var result2 = cache.Get(1);
Debug.Assert(result2 == -1);
}
public static void RunTestcase2()
{
var cache = new LRUCache(2);
cache.Put(2, 1);
cache.Put(1, 1);
cache.Put(2, 3);
cache.Put(4, 1);
var result1 = cache.Get(1);
var result2 = cache.Get(2);
}
// [[3],[1,1],[2,2],[3,3],[4,4],[4],[3],[2],[1],[5,5],[1],[2],[3],[4],[5]]
// [null,null,null,null,null,4,3,2,-1,null,-1,2,-1,4,5]
// [null,null,null,null,null,4,3,2,-1,null,-1,2,3,-1,5]
public static void RunTestcase3()
{
var cache = new LRUCache(3);
cache.Put(1, 1);
cache.Put(2, 2);
cache.Put(3, 3);
cache.Put(4, 4);
var result1 = cache.Get(4);
var result2 = cache.Get(3);
var result3 = cache.Get(2);
var result4 = cache.Get(1);
cache.Put(5, 5);
var resultB1 = cache.Get(1);
var resultB2 = cache.Get(2);
var resultB3 = cache.Get(3);
var resultB4 = cache.Get(4);
var resultB5 = cache.Get(5);
}
}
public class LRUCache
{
internal class Node
{
public Node Next { get; set; }
public Node Prev { get; set; }
public int key, val;
public Node(int key, int value)
{
this.key = key;
this.val = value;
}
}
private Dictionary<int, Node> map;
private Node head;
private int capacity;
/// <summary>
/// double linked list
/// reference:
/// C# LinkedList class implementation
/// https://referencesource.microsoft.com/#system/compmod/system/collections/generic/linkedlist.cs
/// </summary>
/// <param name="capacity"></param>
public LRUCache(int capacity)
{
this.capacity = capacity;
map = new Dictionary<int, Node>();
}
/// <summary>
/// LRU - put least recently used - last one out
/// </summary>
/// <param name="key"></param>
/// <returns></returns>
public int Get(int key)
{
if (!map.ContainsKey(key))
return -1;
var node = map[key];
var newNode = new Node(node.key, node.val);
// remove the node -> add to the tail - last one - refreshed
if (node != node.Prev)
{
var isHead = node == head;
if (isHead)
{
head = head.Next;
}
// remove existing one first, connect node.Prev with node.Next
node.Prev.Next = node.Next;
node.Next.Prev = node.Prev;
// add new node at the end of double linked list
head.Prev.Next = newNode;
newNode.Prev = head.Prev;
newNode.Next = head;
head.Prev = newNode;
node.Prev = null;
node.Next = null;
}
else
{
head = newNode;
head.Prev = head;
head.Next = head;
}
// update key's address
map[key] = newNode;
return node.val;
}
public void Put(int key, int value)
{
var update = map.ContainsKey(key);
var eviction = map.Count == capacity;
if (!update)
{
if (eviction)
{
// remove one
var removed = head;
// remove from the map
map.Remove(removed.key);
if (head == head.Prev)
{
head = null;
}
else
{
head.Prev.Next = head.Next;
head.Next.Prev = head.Prev;
head = head.Next;
}
}
}
else
{
// if key is existed, then it should be removed first and also
// map should be updated as well.
var removed = map[key];
if (map.Count == 1)
{
head = null;
}
if (map.Count == 2) // added after debugging
{
head = head == removed ? head.Next : head;
head.Next = head;
head.Prev = head;
}
else
{
removed.Prev.Next = removed.Next;
removed.Next.Prev = removed.Prev;
head = head == removed ? head.Next : head;
}
}
// add the node
var newNode = new Node(key, value);
if (head == null)
{
head = newNode;
// caught by debugger - connect head and tail in double linked list
// avoid null pointer bug
head.Prev = head;
head.Next = head;
}
else
{
head.Prev.Next = newNode;
newNode.Prev = head.Prev;
// head and tail get connected
head.Prev = newNode;
newNode.Next = head;
}
map[key] = newNode;
}
}
}
