java - sorted list recursive insert method

Question

I'm implementing an abstract class, and implementing an insert method which inserts into a sorted list. This is the recursive method I have so far:

public void insert(E data) {
    Node<E> temp = head;
    insert(temp, data);
}

private void insert(Node<E> curr, E data){
    Node<E> temp = new Node<E>(data);
    if (head == null || data.compareTo(head.data) < 0) {
        temp.next = head;
        head = temp;
    }
    else if(curr.data.compareTo(data) < 0 && (curr.next == null || curr.next.data.compareTo(data) > 0)){
        temp.next = curr.next;
        curr.next = temp;
        return;
    }
    else{
      insert(curr.next, data);
    }
}

However, anytime I try to insert 2+ items into the list, I get a null pointer exception error. Can someone explain my mistake? This is what happens when I try to run it simply inserting 1 and 2: https://gyazo.com/d254d563675b9d1b0efbce443eda4445

merterpam · Accepted Answer · 2016-10-10 23:33:14Z

1

It says that there is a NullPointerException at line 53, which is the else-if statement:

else if(curr.data.compareTo(data) < 0 && curr.next.data.compareTo(data) > 0)

I think it gives that exception because curr.next is null. From the way I can see, when you add the first element you initialize head, but head.next is null (temp.next = head is null as head is null at that time). So when you try to add the second element, you are unable to access curr.next.data and it gives NullPointerException.

answered Oct 10, 2016 at 23:33

merterpam

7756 silver badges14 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

witcheR Over a year ago

How would I handle that?

J E Carter II Over a year ago

A simple way would be to start the else if with (curr.data != null && curr.next !=null). The if condition will be false as soon as either is null and fale through to the final else. But that's not the root issue. The root issue is the approach whereby you're trying to manage something that could be better handled by other means, like appending to the list and then making it unique, for example.

merterpam Over a year ago

else if(curr.data.compareTo(data) < 0 && (curr.next == null || curr.next.data.compareTo(data) > 0) could possibly solve the problem as in the else-if block you want to add data iff curr > data > curr.next and curr.next = null means data is the smallest element.

witcheR Over a year ago

Seems like that handles the null pointer exception, but the issue is that now a node simply isn't being inserted after the first node (can't be found with search). What am I missing? I updated the code.

merterpam Over a year ago

I did a small test using Integer as the template type and it is inserting correctly in ascending order. I may be missing something, but insert function looks OK (However note that it does not handle duplicate entries). I cannot say without seeing the search function, I suggest you writing a print function to see what the linked list contains and also use breakpoints to debug your application to see where the problem lies.

Collectives™ on Stack Overflow

java - sorted list recursive insert method

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related