1429. First Unique Number

time: showFirstUnique: O(1), add(1)

space: O(n)

/*
DoubleLinkedList maintain a unique number list
HashMap record num is in DoubleLinkedList?
set Duplicate check is this number has appeared?
*/

class FirstUnique {
    
    class DoubleLinkedListNode {
        int val;
        DoubleLinkedListNode prev, next;
        DoubleLinkedListNode(int val) {
            this.val = val;
            this.prev = null;
            this.next = null;
        }
    }
    
    private DoubleLinkedListNode head;
    private DoubleLinkedListNode tail;
    private Map<Integer, DoubleLinkedListNode> numToNode;
    private Set<Integer> duplicates;

    public FirstUnique(int[] nums) {
        numToNode = new HashMap<>();
        duplicates = new HashSet<>();
        head = new DoubleLinkedListNode(0); // dummy node
        tail = head;
        for (int num : nums) {
            add(num);
        }
    }
    
    public int showFirstUnique() {
        if (head.next != null) {
            return head.next.val;
        }
        return -1;
    }
    
    public void add(int value) {
        if (duplicates.contains(value)) {
            return;
        }
        if (numToNode.containsKey(value)) {
            remove(value);
            duplicates.add(value);
        } else {
            DoubleLinkedListNode node = new DoubleLinkedListNode(value);
            numToNode.put(value, node);
            tail.next = node;
            node.prev = tail;
            tail = node;
        }
            
    }
    public void remove(int value) {
        DoubleLinkedListNode node = numToNode.get(value);
        DoubleLinkedListNode prev = node.prev;
        prev.next = node.next;
        if (node.next != null) {
            node.next.prev = prev;
        } else {
            tail = prev;
        }
        numToNode.remove(value);
    } 
}

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