Naive Solution Using Doubly Linked List and Map


  • 0
    H
    public class LRUCache {
        
        public LRUCache(int capacity) {
            this.MAX = capacity;
            this.head = new Item();
            this.currenttime = 0;
            this.currentsize = 0;
            this.map = new HashMap<>();
        }
        
        private Item head;
        private int MAX;
        private int currenttime;
        private int currentsize;
        private Map<Integer, Item> map;
        
        
        public int get(int key) {
            this.cacheTick();
            Item cur = head.next;
            if(map.containsKey(key)){
                Item c = map.get(key);
                c.timestamp = this.currenttime;
                c.pre.next = c.next;
                c.next.pre = c.pre;
                //insert in the start
                c.next = this.head.next;
                this.head.next.pre = c;
                this.head.next = c;
                c.pre= this.head;
                return c.value;
            }
            return -1;
        }
        
        public void set(int key, int value) {
            this.cacheTick();
            Item newItem = new Item();
            newItem.key = key;
            newItem.value = value;
            newItem.timestamp = this.currenttime;
            newItem.next = this.head.next;
            head.next = newItem;
            newItem.pre = head;
            if(newItem.next != null){
                newItem.next.pre = newItem;
            }else{
                //last one, make a circle
                head.pre = newItem;
                newItem.next = head;
            }
            ++this.currentsize;
            //remove duplicate key
            if(map.containsKey(key)){
                //remove
                Item d = map.get(key);
                d.pre.next = d.next;
                if(d.next != null)
                    d.next.pre = d.pre;
                map.put(key, newItem);
                --this.currentsize;
            }else{
                map.put(key, newItem);
            }
            if(this.currentsize > this.MAX){
                this.removeLRU();
                --this.currentsize;
            }
            
        }
        
        private void cacheTick(){
            ++this.currenttime;
        }
        
        private void removeLRU(){
            Item tail = head.pre;
            tail.pre.next = tail.next;
            tail.next.pre = tail.pre;
            this.map.remove(tail.key);
        }
        
        class Item{
            int key;
            int value;
            int timestamp;
            Item next;
            Item pre;
        }
    }
    

Log in to reply
 

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