public class DoubleLinkedListNode {  
    public T Value { get; set; }  
   
    public DoubleLinkedListNode Next { get; set; }  
   
    public DoubleLinkedListNode Prior { get; set; }  
   
    public DoubleLinkedListNode(T t) { Value = t; }  
   
    public DoubleLinkedListNode() { }  
   
    public void RemoveSelf() {  
        Prior.Next = Next;  
        Next.Prior = Prior;  
    }  
   
}  
public class DoubleLinkedList {  
    protected DoubleLinkedListNode m_Head;  
    private DoubleLinkedListNode m_Tail;  
   
    public DoubleLinkedList() {  
        m_Head = new DoubleLinkedListNode();  
        m_Tail = m_Head;  
    }  
   
    public DoubleLinkedList(T t)  
        : this() {  
        m_Head.Next = new DoubleLinkedListNode(t);  
        m_Tail = m_Head.Next;  
        m_Tail.Prior = m_Head;  
    }  
   
    public DoubleLinkedListNode Tail {  
        get { return m_Tail; }  
    }  
   
    public DoubleLinkedListNode AddHead(T t) {  
        DoubleLinkedListNode insertNode = new DoubleLinkedListNode(t);  
        DoubleLinkedListNode currentNode = m_Head;  
        insertNode.Prior = null;  
        insertNode.Next = currentNode;  
        currentNode.Prior = insertNode;  
        m_Head = insertNode;  
        return insertNode;  
    }  
    public void RemoveTail() {  
        m_Tail = m_Tail.Prior;  
        m_Tail.Next = null;  
        return;  
    }  
}  
public class LRUCacheHelper {  
    class DictItem {  
        public DoubleLinkedListNode Node { get; set; }  
        public V Value { get; set; }  
    }  
    readonly Dictionary _dict;  
    readonly DoubleLinkedList _queue = new DoubleLinkedList();  
    readonly object _syncRoot = new object();  
    private readonly int _max;  
    public LRUCacheHelper(int capacity, int max) {  
        _dict = new Dictionary(capacity);  
        _max = max;  
    }  
   
    public void Add(K key, V value) {  
        lock (this)  
        {  
   
            checkAndTruncate();  
            DoubleLinkedListNode v = _queue.AddHead(key);   //O(1)  
            _dict[key] = new DictItem() { Node = v, Value = value }; //O(1)  
        }  
    }  
   
    private void checkAndTruncate() {  
        int count = _dict.Count;                        //O(1)  
        if (count >= _max) {  
            int needRemoveCount = count / 10;  
            for (int i = 0; i < needRemoveCount; i++) {  
                _dict.Remove(_queue.Tail.Value);        //O(1)  
                _queue.RemoveTail();                    //O(1)  
            }  
        }  
    }  
   
    public void Delete(K key) {  
        lock (this) {  
            _dict[key].Node.RemoveSelf();  
            _dict.Remove(key); //(1)   
        }  
    }  
    public V Get(K key) {  
        lock (this) {  
            DictItem ret;  
            if (_dict.TryGetValue(key, out ret)) {  
                ret.Node.RemoveSelf();  
                _queue.AddHead(key);  
                return ret.Value;  
            }  
            return default(V);   
        }  
    }  
}