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):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90

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;     } }