Results 1 to 7 of 7
Like Tree3Likes
  • 1 Post By shall
  • 1 Post By shall
  • 1 Post By shall

Thread: linked list quick sort null pointer exception

  1. #1
    cherrychives is offline Member
    Join Date
    Apr 2012
    Posts
    25
    Rep Power
    0

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

    Java 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.
    Last edited by cherrychives; 05-13-2012 at 11:28 AM.

  2. #2
    shall is offline Senior Member
    Join Date
    Apr 2012
    Posts
    199
    Rep Power
    0

    Default Re: linked list quick sort null pointer exception

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

  3. #3
    cherrychives is offline Member
    Join Date
    Apr 2012
    Posts
    25
    Rep Power
    0

    Default Re: linked list quick sort null pointer exception

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

  4. #4
    shall is offline Senior Member
    Join Date
    Apr 2012
    Posts
    199
    Rep Power
    0

    Default Re: linked list quick sort null pointer exception

    Can you post the code for the intList class?

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

  5. #5
    cherrychives is offline Member
    Join Date
    Apr 2012
    Posts
    25
    Rep Power
    0

    Default Re: linked list quick sort null pointer exception

    Here's my intList class:

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

    Java 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 + ", ");
        }
    }
    Last edited by cherrychives; 05-14-2012 at 01:09 AM.

  6. #6
    shall is offline Senior Member
    Join Date
    Apr 2012
    Posts
    199
    Rep Power
    0

    Default Re: linked list quick sort null pointer exception

    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.
    cherrychives likes this.

  7. #7
    cherrychives is offline Member
    Join Date
    Apr 2012
    Posts
    25
    Rep Power
    0

    Default Re: linked list quick sort null pointer exception

    Quote Originally Posted by shall View Post
    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!

Similar Threads

  1. Null pointer exceptions and linked lists
    By Tsirist in forum New To Java
    Replies: 6
    Last Post: 03-19-2011, 07:39 PM
  2. Insertion Sort for linked list help?
    By bubtub24 in forum New To Java
    Replies: 3
    Last Post: 11-28-2010, 07:21 AM
  3. Null Pointer Exception in Radix Sort
    By resspopv in forum New To Java
    Replies: 7
    Last Post: 11-19-2010, 06:21 AM
  4. [SOLVED] Insertion Sort in Linked List
    By taylorp in forum New To Java
    Replies: 10
    Last Post: 03-27-2009, 01:34 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •