All O`one Data Structure

class AllOne {

    Bucket head;
    Bucket tail;
    Map<Integer, Bucket> valueBucketMap;
    Map<String, Integer> keyValueMap;

    private class Bucket {
        int value;
        Set<String> keySet;
        Bucket pre;
        Bucket next;

        public Bucket(int val) {
            value = val;
            keySet = new LinkedHashSet<>();
            pre = null;
            next = null;
        }
    }

    /** Initialize your data structure here. */
    public AllOne() {
        head = new Bucket(-1);
        tail = new Bucket(-1);
        head.next = tail;
        tail.pre = head;
        valueBucketMap = new HashMap<>();
        keyValueMap = new HashMap<>();
    }

    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    public void inc(String key) {
        if (keyValueMap.containsKey(key)) {
            changeKeyValue(key, 1);
        } else {
            keyValueMap.put(key, 1);
            if (head.next.value != 1) {
                addBucketAfter(new Bucket(1), head);
                valueBucketMap.put(1, head.next);
            }
            head.next.keySet.add(key);
        }
    }

    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    public void dec(String key) {
        if (!keyValueMap.containsKey(key)) {
            return;
        }
        int value = keyValueMap.get(key);
        if (value == 1) {
            keyValueMap.remove(key);
            removeKeyFromBucket(valueBucketMap.get(value), key);
        } else {
            changeKeyValue(key, -1);
        }
    }

    /** Returns one of the keys with maximal value. */
    public String getMaxKey() {
        if (tail.pre == head) {
            return "";
        }
        return tail.pre.keySet.iterator().next();
    }

    /** Returns one of the keys with Minimal value. */
    public String getMinKey() {
        if (tail.pre == head) {
            return "";
        }
        return head.next.keySet.iterator().next();
    }

    private void changeKeyValue(String key, int offset) {
        int curVal = keyValueMap.get(key);
        keyValueMap.put(key, curVal + offset);
        Bucket curBucket = valueBucketMap.get(curVal);
        Bucket newBucket = valueBucketMap.get(curVal + offset);
        if (newBucket == null) {
            newBucket = new Bucket(curVal + offset);
            valueBucketMap.put(curVal + offset, newBucket);
            if (offset == 1) {
                addBucketAfter(newBucket, curBucket);
            } else {
                addBucketAfter(newBucket, curBucket.pre);
            }
        }
        newBucket.keySet.add(key);
        removeKeyFromBucket(curBucket, key);
    }

    private void removeKeyFromBucket(Bucket bucket, String key) {
        bucket.keySet.remove(key);
        if (bucket.keySet.size() == 0) {
            bucket.pre.next = bucket.next;
            bucket.next.pre = bucket.pre;
            bucket.next = null;
            bucket.pre = null;
            valueBucketMap.remove(bucket.value);
        }
    }

    private void addBucketAfter(Bucket newBucket, Bucket preBucket) {
        newBucket.pre = preBucket;
        newBucket.next = preBucket.next;
        preBucket.next.pre = newBucket;
        preBucket.next = newBucket;
    }
}

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