1429 first unique number

https://leetcode.com/problems/first-unique-number/

class FirstUnique {
    class Node {
        private int val;
        private Node pre;
        private Node next;
        public Node(int val) {
            this.val = val;
        }
    }
    private Node dummyHead;
    private Node dummyTail;
    private Map<Integer, Node> vals;
    public FirstUnique(int[] nums) {
        dummyHead = new Node(-1);
        dummyTail = new Node(-1);
        dummyHead.pre = null;
        dummyHead.next = dummyTail;
        dummyTail.next = null;
        dummyTail.pre = dummyHead;
        vals = new HashMap<>();
        for (int num : nums) {
            add(num);
        }
    }
    
    public int showFirstUnique() {
        return dummyHead.next.val;
    }
    
    public void add(int num) {
        Node node = vals.get(num);
        if (node == null) {
            node = new Node(num);
            insert(node);
            vals.put(num, node);
        } else {
            remove(node);
        }
    }
    private void insert(Node node) {
        Node pre = dummyTail.pre;
        pre.next = node;
        node.pre = pre;
        node.next = dummyTail;
        dummyTail.pre = node;
    }
    private void remove(Node node) {
        //不要重复remove
        if (node.next == null || node.pre == null) {
            return;
        }
        Node pre = node.pre;
        Node next = node.next;
        pre.next = next;
        next.pre = pre;
        node.next = null;
        node.pre = null;
    }
}

/**
 * Your FirstUnique object will be instantiated and called as such:
 * FirstUnique obj = new FirstUnique(nums);
 * int param_1 = obj.showFirstUnique();
 * obj.add(value);
 */

注意remove node是idempotent的，重复remove不能起作用，map是val -> Node(val)