One solution for the LRU Cache


  • 0
    E

    public class LRUCache {
    class Node {
    int val;
    int key;
    Node prev;
    Node next;
    public Node(int key, int val) {
    this.key = key;
    this.val = val;
    this.prev = null;
    this.next = null;
    }
    }
    private Map<Integer,Node> map;
    private Node head;
    private Node tail;
    private int cp;
    private int size;

    public LRUCache(int capacity) {
       this.map = new HashMap<Integer,Node>();
       this.head = null;
       this.tail = null;
       this.cp = capacity;
       this.size = 0;
    }
    
    public int get(int key) {
       if (this.map.containsKey(key)) {
           Node node = map.get(key);
           moveToTail(node);
           return node.val;
       } else {
           return -1;
       }
        
    }
    
    public void set(int key, int value) {
        if (this.map.containsKey(key)) {
            Node node = map.get(key);
            node.val = value;
            moveToTail(node);
        } else {
            Node node = new Node(key,value);
            if (size==cp) {
                removeHead();
            }
            //Add the new node
            if (size==0) {
                head = node;
                tail = node;
            } else {
                tail.next = node;
                node.prev = tail;
                tail = node;
            }
            size++;
            map.put(key,node);
        }
    }
    
    private void moveToTail(Node node) {
       if (node==tail) return;
       Node prevN = node.prev;
       Node nextN = node.next;
       if (head==node) {
           // node is the head node;
           this.head = nextN;
           this.head.prev = null;
       } else { {
           prevN.next = nextN;
           nextN.prev = prevN;
       }
       }
       this.tail.next = node;
       node.prev = tail;
       this.tail = node;
       this.tail.next = null;
    }
    
    private void removeHead() {
        map.remove(this.head.key);
        if (head==tail) {
            head=null;
            tail=null;
            size--;
            return;
        } 
        
        Node temp = this.head.next;
        this.head.next = null;
        this.head = temp;
        this.head.prev = null;
        
        size--;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.