Solution using HashMap and DoubleLinkedList


  • 0
    S
    public class LRUCache {
        public static class Node {
            int key;
            int value;
            Node next;
            Node prev;
            
            Node(int key, int value) {
                this.key = key;
                this.value = value;
                this.prev = null;
                this.next = null;
            }
        }
        
        public static class LinkedList {
            Node head;
            Node tail;
            int size;
        
            LinkedList() {
                this.size = 0;
                this.head = null;
                this.tail = null;
            }
            
            public Node add(int key, int value) {
                Node n = new Node(key, value);
               
                if (tail == null) {
                    head = n;
                }
                else {
                    tail.next = n;
                    n.prev = tail;
                }
                
                tail = n;
                size++;
                return n;
            }
            
            //remove the head 
            public Node removeLRU() {
                Node oldHead = head;
                
                if (head == tail) {
                    head = null;
                    tail = null;
                    size--;
                }
               
                else if (head != null) {
                    head.next.prev = null;
                    head = head.next;
                    size--;
                }
               
                return oldHead;
            }
            
            public void moveToTail(Node n) {
                if(tail == n){
                    return;
                }
                
                if(head == n){
                    head = n.next;
                    n.next.prev = null;
                }
                else {
                    n.prev.next = n.next;
                    n.next.prev = n.prev;
                }
                
                tail.next = n;
                n.prev = tail;
                n.next = null;
                tail = n;
            }
            
            //for debugging purpose
            public void print() {
                Node cur = this.head;
                System.out.print("(");
                while(cur!= null) {
                    System.out.print(cur.key+" ");
                    cur = cur.next;
                }
                System.out.println(")");
            }
           
        }
        
        int capacity;
        LinkedList linkedList;
        Map<Integer, Node> map;
        
        public LRUCache(int capacity) {
            this.linkedList = new LinkedList();
            this.map = new HashMap<Integer, Node>();
            this.capacity = capacity;
        }
        
        public int get(int key) {
            if(map.containsKey(key)) {
                Node n = map.get(key);
                linkedList.moveToTail(n);
                return (int) map.get(key).value;
            }
            else {
                return -1;
            }
        }
        
        public void set(int key, int value) {
            if (map.containsKey(key)) {
                Node n = map.get(key);
                n.value = value;
                map.put(key, n);
                linkedList.moveToTail(n);
            }
            else if (linkedList.size == this.capacity) {
                Node n = linkedList.removeLRU();
                map.remove(n.key);
                map.put(key, linkedList.add(key, value));
            }
            else {
                //new node, and cache has space for it
                map.put(key, linkedList.add(key, value));
            }
        }
    }

Log in to reply
 

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