Sorting linked list as numbers are added

Question

I am trying to create a sorted linked list that sorts as new numbers are added in Java. The way I would like the program to work is to insert the new node in the correct place so that it is sorted. However, I keep getting a NullPointerException. Here is my code:

public void Add(int d){
        Node newNode = new Node(d);
        if(first == null){
            first = newNode;
            return;
        }
        Node cur = first.next;
        Node prev = first;
        if(newNode.data > prev.data){
            newNode.next = first.next;
            first = newNode;
            return;
        }
        while(cur.next != null){
            if(cur.data < newNode.data && prev.data > newNode.data){
                newNode.next = cur;
                prev.next = newNode;
            }
            cur = cur.next;
            prev = prev.next;
        }
        cur.next = newNode;

    }

I have no idea why it does not work.

Answer 1

If your collection of numbers cannot contain any duplicates (each number can only appear once) then simply use a TreeSet<Integer>. A TreeSet keeps itself sorted, and will not allow duplicates. This will be far more efficient, and far easier to use, than a list which gets sorted every time something goes into it.

If your collection of numbers can contain duplicates, then you'll need to use something more sophisticated. I'd use a TreeMap<Integer, Integer> so that the map keys are your numbers, and the map values are the number of times that number has been added to the map.

Regarding your existing code, any object reference which has not been assigned an object will default to having a value of null and you cannot call any methods or refer to any fields on a null reference (or "null pointer").

Answer 2

When you set curr=first.next it will be null, this is where your getting your null point exception from... in the future this question could have been easily figured out by using the debugger feature in you IDE I urge you to get familiar with this feature it will save you hours of annoyance!

Cheers