算法之LRU模版1

package com.zhang.reflection.面试.算法模版.LRU;
import java.util.HashMap;
import java.util.Map;

public class LRU {
    class Node<K,V>{
        K key;
        V value;
        Node pre;
        Node next;
        public Node(){
            this.pre=null;
            this.next=null;
        }
        public Node(K key,V value){
            this.key=key;
            this.value=value;
            this.pre=null;
            this.next=null;
        }
    }
    class DoubleLinkedList{
        Node head;
        Node tail;
        public DoubleLinkedList(){
            head=new Node();
            tail=new Node();
            head.next=tail;
            tail.pre=head;
        }
        public void addHead(Node node){
            node.next=head.next;
            node.pre=head;
            head.next.pre=node;
            head.next=node;
        }
        public void removeTail(Node node){
            node.pre.next=node.next;
            node.next.pre=node.pre;
            node.pre=null;
            node.next=null;
        }
        public Node getLast(){
            return tail.pre;
        }
    }
    int cacheSize;
    Map<Integer,Node<Integer,Integer>> map;
    DoubleLinkedList list;
    public LRU(int cacheSize){
        this.cacheSize=cacheSize;
        map=new HashMap<Integer,Node<Integer,Integer>>();
        list=new DoubleLinkedList();
    }
    public int get(int key){
        if(!map.containsKey(key)){
            return -1;
        }
        Node<Integer,Integer> node=map.get(key);
        list.removeTail(node);
        list.addHead(node);
        return node.value;
    }
    public void put(int key,int value){
        if(map.containsKey(key)){
            Node<Integer,Integer> node=map.get(key);
            node.value=value;
            list.removeTail(node);
            list.addHead(node);
        }else{
            if(cacheSize==map.size()){
                Node<Integer,Integer> last = list.getLast();
                map.remove(last.key);
                list.removeTail(last);
            }
            Node<Integer,Integer> node=new Node<>(key,value);
            map.put(key,node);
            list.addHead(node);
        }
    }
    public static void main(String[] args) {
        LRU t=new LRU(3);
        t.put(1,1);
        t.put(2,2);
        t.put(3,3);
        System.out.println(t.map.keySet());
        t.get(1);
        t.put(4,4);
        System.out.println(t.map.keySet());
        t.put(5,5);
        System.out.println(t.map.keySet());
    }
}