using System.Collections.Generic;
public ListNode prev, next;
public ListNode(int k, int v)
private int capacity, size;
private ListNode dummyHead, dummyTail;
private Dictionary<int, ListNode> map;
public LRUCache(int capacity)
this.capacity = capacity;
this.dummyHead = new ListNode(0, 0);
this.dummyTail = new ListNode(0, 0);
this.dummyHead.next = this.dummyTail;
this.dummyTail.prev = this.dummyHead;
map = new Dictionary<int, ListNode>();
if(!map.ContainsKey(key))
ListNode target = map[key];
public void set(int k, int v)
ListNode target = map[k];
map.Remove(dummyHead.next.key);
ListNode newNode = new ListNode(k, v);
private void addToLast(ListNode target)
target.prev = dummyTail.prev;
dummyTail.prev.next = target;
private void remove(ListNode target)
target.next.prev = target.prev;
target.prev.next = target.next;
public static void Main()
LRUCache cache = new LRUCache(4);
int[][] data = new int[5][] {
cache.set(data[i][0], data[i][1]);
cache.set(data[4][0], data[4][1]);