Lintcode 960. First Unique Number in Data Stream II

We need to implement a data structure named DataStream. There are two methods required to be implemented:

1. void add(number) // add a new number
2. int firstUnique() // return first unique number

Example

Example 1:

Input:
add(1)
add(2)
firstUnique()
add(1)
firstUnique()
Output:
[1,2]

Example 2:

Input:
add(1)
add(2)
add(3)
add(4)
add(5)
firstUnique()
add(1)
firstUnique()
add(2)
firstUnique()
add(3)
firstUnique()
add(4)
firstUnique()
add(5)
add(6)
firstUnique()
Output:
[1,2,3,4,5,6]

Notice

You can assume that there must be at least one unique number in the stream when calling the firstUnique.

Solution:
Similar to the "LRU cache" problem. Build a hashMap + doubly linked list. The list is ordered by the sequence of adding the numbers. 

Code (Java):

public class DataStream {
    Map<Integer, ListNode> numToNodeMap;
    LinkedList nodeList;
    
    public DataStream(){
        // do intialization if necessary
        numToNodeMap = new HashMap<>();
        nodeList = new LinkedList();
    }
    /**
     * @param num: next number in stream
     * @return: nothing
     */
    public void add(int num) {
        // write your code here
        if (!numToNodeMap.containsKey(num)) {
            ListNode node = nodeList.appendToTail(num);
            numToNodeMap.put(num, node);
        } else {
            ListNode node = numToNodeMap.get(num);
            nodeList.remove(node);
            numToNodeMap.put(num, null);
        }
    }

    /**
     * @return: the first unique number in stream
     */
    public int firstUnique() {
        // write your code here
        return nodeList.getFirst().val;
    }
}

class ListNode {
    int val;
    ListNode prev, next;
    
    public ListNode(int val) {
        this.val = val;
        prev = next = null;
    }
}

class LinkedList {
    ListNode dummyHead;
    ListNode dummyTail;
    
    public LinkedList() {
        dummyHead = new ListNode(-1);
        dummyTail = new ListNode(-1);
        
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
    }
    
    ListNode appendToTail(int val) {
        ListNode tailNode = new ListNode(val);
        dummyTail.prev.next = tailNode;
        tailNode.prev = dummyTail.prev;
        
        tailNode.next = dummyTail;
        dummyTail.prev = tailNode;
        
        return tailNode;
    }
    
    ListNode getFirst() {
       if (dummyHead.next == dummyTail) {
           return null;
       }
       
       return dummyHead.next;
    }
    
    void remove(ListNode node) {
        if (node == null) {
            return;
        }
        
        ListNode prevNode = node.prev;
        ListNode nextNode = node.next;
        
        prevNode.next = nextNode;
        nextNode.prev = prevNode;
        
        node.prev = null;
        node.next = null;
    }
}