题解 | #设计LRU缓存结构#

using System;
using System.Collections.Generic;


public class Solution {

    Dictionary<int, Node> cache = new Dictionary<int, Node>();
    Node head = new Node(-1,-1);
    Node tail = new Node(-1,-1);
    int Capacity{get;}
    int Count => cache.Count;

    public class Node{
        public int key;
        public int value;
        public Node pre;
        public Node next;

        public Node(){}
        public Node(int key, int value){
            this.key = key;
            this.value = value;
        }
    }


    public Solution(int capacity) {
        Capacity = capacity;
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        if(cache.TryGetValue(key, out Node node)){
            SetFirst(node);
            return node.value;
        }
        else return -1;
    }

    public void set(int key, int value) {
        if(cache.TryGetValue(key, out Node node)){
            SetFirst(node);
            node.value = value;
            return;
        }
        if(Count == Capacity){
            RemoveLast();
        }
        Add(key, value);
    }
    
    public void Remove(Node node){
        node.pre.next = node.next;
        node.next.pre = node.pre;
        node.pre = null;
        node.next = null;
    }
    public void SetFirst(Node node){
        node.pre.next = node.next;
        node.next.pre = node.pre;
        head.next.pre = node;
        node.pre = head;
        node.next = head.next;
        head.next = node;
    }
    public void Add(int key, int value){
        Node node = new Node(key, value);
        cache.Add(key, node);
        head.next.pre = node;
        node.pre = head;
        node.next = head.next;
        head.next = node;
        Console.WriteLine("add(key):" + key);
    }
    public void RemoveLast(){
        Node node = tail.pre;
        if(node != head){
            Console.WriteLine("remove(key):" + node.key);
            cache.Remove(node.key);
            Remove(node);
            return;
        }
        Console.WriteLine("cant remove the last : the count == 0!");
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution solution = new Solution(capacity);
 * int output = solution.get(key);
 * solution.set(key,value);
 */