Generating a random number not already duplicated in a DoublyLinkedList

I am encountering some difficulty with an algorithmic issue, and it would be great if anyone had some advice.

I have a doubly linked list, and each node holds a string and an integer. The goal is to take a number of specified nodes, delete them, and add a new single, "merged" node at the end of the list. This I have done. However, I also want this new node to have a random four digit integer that does not already exist in the list.

So far I have the following: ('list' is the name of the linked list, 'cur' is the node I am using to iterate through the list.)

int num = (int)(Math.random ()*9999)+1000;
while (cur != null){
    while (num == cur.getNumber())
          num = (int)(Math.random ()*9999)+1000;
    cur = cur.getNext();
} 

Unfortunately, this code allows for the possibility of being halfway through the list and generating a number that already exists in the first half, which I do not want...

Thank you in advance for your help.