Thinking process

doubly linked list

public class AllOne {
    class Node {
        String key;
        int val;

        Node prev;
        Node next;

        public Node(String k, int v) {
            this.key = k;
            this.val = v;
        }

    }

    HashMap<String, Node> map;
    Node dummyHead;//dummyHead.next => max
    Node dummyTail;//dummyTail.prev => min

    /** Initialize your data structure here. */
    public AllOne() {
        map = new HashMap<>();
        dummyHead = new Node("", Integer.MAX_VALUE);
        dummyTail = new Node("", Integer.MIN_VALUE);

        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
    }

    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    public void inc(String key) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.val = node.val + 1;

            while (node.val > node.prev.val) {
                System.out.println(node.key);
                swap(node.prev, node);
            }
        } else {
            Node node = new Node(key, 1);
            map.put(key, node);

            Node tmpNode = dummyTail.prev;
            dummyTail.prev = node;
            node.next = dummyTail;
            node.prev = tmpNode;
            tmpNode.next = node;
        }

    }

    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    public void dec(String key) {
        if (map.containsKey(key)) {
            Node node = map.get(key);

            if (node.val == 1) {
                map.remove(key);
                deleteNode(node);
                return;
            }

            node.val = node.val - 1;

            while (node.val < node.next.val) {
                swap(node, node.next);
            }
        }
    }

    /** Returns one of the keys with maximal value. */
    public String getMaxKey() {
        return dummyHead.next.val == Integer.MIN_VALUE ? "" : dummyHead.next.key;
    }

    /** Returns one of the keys with Minimal value. */
    public String getMinKey() {
        return dummyTail.prev.val == Integer.MAX_VALUE ? "" : dummyTail.prev.key;
    }

    private void swap(Node node1, Node node2) {
        //0,  1, 2 , 3
        //0,  2, 1 , 3
        Node prevNode = node1.prev;
        Node nextNode = node2.next;

        node1.prev = node2;
        node2.prev = prevNode;

        node1.next = nextNode;
        node2.next = node1;

        prevNode.next = node2;
        nextNode.prev = node1;
    }

    private void deleteNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}