linked list quick sort null pointer exception

I'm creating a method which receives a linked list, and sorts it using quick sort method - i.e. takes the first value in the list as a pivot value and keeps splitting the list into two lists; one containing values greater than (or equal to) the pivot value, and the other containing values less than the pivot value.

My program keeps coming up with null pointer exception after running the method a few times (I've marked the line where it occurs below):

Code:

---


private static void quickSort(intList list){
        //System.out.println();
        intNode pivot = new intNode(list.first.value); //create new node to store first value in list as a pivot value
        list.deleteFirst(); //delete first value from list
        intList abovePivot = new intList(list.size); //create temporary linked list to hold all values greater than pivot value
        intList belowPivot = new intList(list.size); //create temporary linked list to hold all values less than pivot value
        while(list.first != null){ //loop while list still has values to be added to abovePivot or belowPivot
                if(list.first.value < pivot.value){
                        belowPivot.insertFirst(list.first.value); //insert list's first value into the start of belowPivot if less than pivot value
                }
                else{
                        abovePivot.insertFirst(list.first.value); //else insert list's first value into abovePivot if greater than pivot value
                }
                //belowPivot.printList();
                //abovePivot.printList();
                list.deleteFirst(); //delete first node in list before looping again
        }
        if(belowPivot.first.nextNode != null){ // << null pointer exception occurs here
                quickSort(belowPivot); //use quicksort again if belowPivot contains more than one node
        }
        if(abovePivot.first.nextNode != null){
                quickSort(abovePivot); //use quicksort again if abovePivot contains more than one node
        }
}

---

The problem seems to occur when the received list contains two or less values, but I am completely unsure as to why.

Any advice would be much appreciated.

I don't see the mark (in the comment?). Which line is it?

wow!.. I always forget something.. just edited code to show where the exception occurs "null pointer exception occurs here"

Can you post the code for the intList class?

Make sure first is getting set properly in the intList class.

Here's my intList class:

Code:

---


class intList {
        public intNode first;
        public int size;

        public intList(int x) {
                first = null;
                size = x;
    }

        public void createRandomList(){
                Random rand = new Random();
                for(int i = size; i > 0; i--){
                        int r = rand.nextInt(size);
                        insertFirst(r);
                }
        }

        public void insertFirst(int x) {
                intNode newNode = new intNode(x);
                if(first != null){
                        newNode.nextNode = first;
                        newNode.next = first.value;
                }
                first = newNode;
        }

        public void deleteFirst() {
                first = first.nextNode;
        }

        public void printList() {
                intNode current = first;
                System.out.print("List: ");
                while(current != null) {
                        current.printNode();
                        current = current.nextNode;
                }
                System.out.println("");
        }
}

---

And my intNode class, just in case it helps:

Code:

---


class intNode {
    public int value;
        public int next;
    public intNode nextNode;

    public intNode(int x) {       
        value = x;
                next = 0;
    }

    public void printNode() {
        System.out.print(value + ", ");
    }
}

---

belowPivot.first is null. Your program needs to make sure belowPivot.first is not null before calling belowPivot.first.nextNode. The same can be said of abovePivot.first.

Quote:

---

Originally Posted by shall

belowPivot.first is null. Your program needs to make sure belowPivot.first is not null before calling belowPivot.first.nextNode. The same can be said of abovePivot.first.

---

I didn't even think of that; I figured if first.nextNode is not null, then first won't be null either. But I didn't take into consideration a case where the list being sorted has only one or two values, which is bound to happen with recursive methods such as this.

Many thanks! You're a lifesaver!