https://leetcode.com/problems/all-oone-data-structure/submissions/

allO1DataStructure.js

/**
 * Initialize your data structure here.
 */
var AllOne = function() {
    this.counter = new Map(); // [key: int]
    this.index = new Map(); // [int: ListNode]
    this.head = new ListNode(); // prev, next, set<key>
    this.tail = new ListNode();
    this.head.prev = this.tail;
    this.tail.next = this.head;
};


var ListNode = function(){
    this.prev = null;
    this.next = null;
    this.set = new Set();
}

// removes key from listNode at index[val]
// if node is empty after removal, removes node as well
AllOne.prototype.removeFromListNode = function(key, val){
    const node = this.index.get(val);
    node.set.delete(key);
    if(node.set.size === 0){
        const prev = node.prev;
        const next = node.next;
        prev.next = next;
        next.prev = prev;
        this.index.delete(val);
    }
}

// inserts node in list after node indexed at index[val]
// adds pointer index[val+1] = newNode
AllOne.prototype.insertNodeAfter = function(key, val){
    if(this.index.has(val+1)){
        this.index.get(val+1).set.add(key);
    }else{
        // create a new node
        const newNode = new ListNode();
        newNode.set.add(key); // add the key to it
        
        const prevNode = this.index.get(val);
        const nextNode = prevNode.next;
        
        newNode.prev = prevNode;
        newNode.next = nextNode;
        prevNode.next = newNode;
        nextNode.prev = newNode;
        this.index.set(val+1, newNode);
    }
}

// inserts node in list before node indexed at index[val]
// adds pointer index[val-1] = newNode
AllOne.prototype.insertNodeBefore = function(key, val){
    if(val === 1) return;
    if(this.index.has(val-1)){
        this.index.get(val-1).set.add(key);
    }else{
        // create a new node
        const newNode = new ListNode();
        newNode.set.add(key); // add the key to it
        
        const nextNode = this.index.get(val);
        const prevNode = nextNode.prev;
        
        newNode.prev = prevNode;
        newNode.next = nextNode;
        prevNode.next = newNode;
        nextNode.prev = newNode;
        this.index.set(val-1, newNode);
    }
}

// inserts node at index[1]
AllOne.prototype.addToTail = function(key){
    // create a new node
    const newNode = new ListNode();
    newNode.set.add(key); // add the key to it

    const nextNode = this.tail.next
    const prevNode = this.tail;

    newNode.prev = prevNode;
    newNode.next = nextNode;
    prevNode.next = newNode;
    nextNode.prev = newNode;
    this.index.set(1, newNode);
}

/**
 * Inserts a new key <Key> with value 1. Or increments an existing key by 1. 
 * @param {string} key
 * @return {void}
 */
AllOne.prototype.inc = function(key) {
    if(this.counter.has(key)){
        const currentVal = this.counter.get(key);
        const nextVal = currentVal + 1;
        
        // manage counter
        this.counter.set(key, nextVal);
        
        // manage index and list
        if(this.index.has(nextVal)){
            this.index.get(nextVal).set.add(key); // add to existing listnode
        }else{
            this.insertNodeAfter(key, currentVal);
        }
        this.removeFromListNode(key, currentVal);
        
        
    }else{
        const nextVal = 1;
        // manage counter
        this.counter.set(key, nextVal);
        // manage index and list
        if(this.index.has(nextVal)){
            this.index.get(nextVal).set.add(key); // add to existing listnode
        }else{
            this.addToTail(key); // add 1 to tail
        }
    }
};

/**
 * Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. 
 * @param {string} key
 * @return {void}
 */
AllOne.prototype.dec = function(key) {
    if(!this.counter.has(key)) return;
    const currentVal = this.counter.get(key);
    const nextVal = currentVal - 1;
    
    // manage counter
    if(nextVal === 0) this.counter.delete(key);
    else this.counter.set(key, nextVal);
    
    // manage index and list
    if(this.index.has(nextVal)){
        this.index.get(nextVal).set.add(key); // add to existing listnode
    }else{
        this.insertNodeBefore(key, currentVal);
    }
    this.removeFromListNode(key, currentVal);
};

/**
 * Returns one of the keys with maximal value.
 * @return {string}
 */
AllOne.prototype.getMaxKey = function() {
    const maxNode = this.head.prev;
    if(maxNode.prev === null) return ''; // maxNode is tail
    for(let key of maxNode.set) return key;
};

/**
 * Returns one of the keys with Minimal value.
 * @return {string}
 */
AllOne.prototype.getMinKey = function() {
    const minNode = this.tail.next;
    if(minNode.next === null) return ''; // min node is head
    for(let key of minNode.set) return key;
};

/** 
 * Your AllOne object will be instantiated and called as such:
 * var obj = new AllOne()
 * obj.inc(key)
 * obj.dec(key)
 * var param_3 = obj.getMaxKey()
 * var param_4 = obj.getMinKey()
 */