A Pretty "Low Level" Javascript Implementation - (One Hash + Hand Implemented Linked List


  • 0
    A

    Just in case anyone was interested. A very low-level - "you see all the pointer manipulation" - solution in Javascript (beat 90% of javascript submission):

    /**
     * @param {number} key
     * @param {number} val
     */
    function ListNode(key,val){
        this.key = key
        this.val = val    
        this.next = null
        this.prev = null
    }
    /**
     * @param {number} capacity
     */
    var LRUCache = function(capacity) {
        this.size = 0
        this.capacity = capacity
        this.hash = {}
        this.head = null
        this.tail = null
        this.isFull = function(){return this.size>=this.capacity}
        this.isEmpty = function(){return this.size==0}
    };
    
    /** 
     * @param {number} key
     * @return {number}
     */
    LRUCache.prototype.get = function(key) {
        if(this.hash[key]){
            var currNode = this.hash[key]
            if(!currNode.prev){
    
            } else if(!currNode.next){
                currNode.prev.next = null
                this.tail = currNode.prev
                currNode.next = this.head
                currNode.prev = null
                this.head.prev = currNode
                this.head = currNode
            } else if(currNode.next && currNode.prev){
                currNode.prev.next = currNode.next
                currNode.next.prev = currNode.prev
                currNode.next = this.head
                currNode.prev = null
                this.head.prev = currNode
                this.head = currNode
            }
            return currNode.val
        } else {
            return -1
        }
    };
    
    /** 
     * @param {number} key 
     * @param {number} value
     * @return {void}
     */
    LRUCache.prototype.put = function(key, value) {
        if(this.hash[key]){
            var currNode = this.hash[key]
            currNode.val = value
            if(!currNode.prev){
                
            } else if(!currNode.next){
                currNode.prev.next = null
                this.tail = currNode.prev
                currNode.next = this.head
                currNode.prev = null
                this.head.prev = currNode
                this.head = currNode
            } else if(currNode.next && currNode.prev){
                currNode.prev.next = currNode.next
                currNode.next.prev = currNode.prev
                currNode.next = this.head
                currNode.prev = null
                this.head.prev = currNode
                this.head = currNode
            }
        } else {
            var newNode = new ListNode(key,value)
            if(this.isFull()){
                var oldHead = this.head
                this.head = newNode
                newNode.next = oldHead
                oldHead.prev = newNode
                this.hash[key] = newNode
                delete this.hash[this.tail.key]
                this.tail.prev.next = null
                this.tail = this.tail.prev
            } else if(this.isEmpty()) {
                this.head = this.tail = newNode
                this.hash[key]=newNode
                this.size++
            } else {
                var oldHead = this.head
                this.head = newNode
                newNode.next = oldHead
                oldHead.prev = newNode
                this.hash[key]=newNode
                this.size++
            }   
        }
    };
    

Log in to reply
 

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