NullPointerException when iterating over linked list

Question

The concept behind the code is to delete elements in a list that are greater than the element before it. In this case my nodes have an int data and are comparable through that. (The class these are in extends Comparable<>

The issue is when I get a nullpointexception when this code runs with the linked list:

 [2,5,4,3,7,6,4,2,3,4,5]

The expected list that should be gotten is

[2,2]

Because (5 > 2) removes 5 then (4 > 2) removes 4 then (3 > 2) removes 3 ... and so on until it hits the end with a nullpointerexception.

Another example would be for the list

[3,1,-2,3,6,-1,3,2,1]

The list should end up being

[3,1,-2]

The debug code in there is to show which elements got removed.

The getter methods are basics and work fine.

public void deleteIncrementing() {
    T largest = null;

    while(head.getNext() != null || head != null) {
        Node<T> temp = head.getNext();

        while(temp.getValue().compareTo(head.getValue()) > 0){
            largest = temp.getValue();
            remove(largest);
            System.out.println(largest); // debug
            if(temp.getNext() == null){
                break;
            }
            temp = head.getNext();
        }
        head = temp;
    }
}

DERIVED FROM SUGGESTED PSEUDO-CODE:

    Node<T> current = head;
    Node<T> previous = null;

    while(current != null) {
        if (previous != null){
            if (current.getValue().compareTo(previous.getValue()) > 0){
                //System.out.println(current.getValue().toString());
                remove(current.getValue());
            }
            if (current.getValue().compareTo(previous.getValue()) < 0){
                //System.out.println(previous.getPrevious().getValue().toString());
                //System.out.println(current.getValue().toString());
                remove(previous.getValue());
            }
        }

        previous = current;
        current  = current.getNext(); 
    }

Which still isn't correct because it doesn't take in account the first to last element and keep the final one attached... any reasons?

I'm guessing you should remove the `||` and add the `&&` in this following line `while(head.getNext() != null || head != null)` — jmail, Mar 22 '14 at 07:58

score 1 · Answer 1 · answered Mar 21 '14 at 20:55

1

For starters, this condition:

while (head.getNext() != null || head != null)

Should be:

while (head != null && head.getNext() != null)

Always check for nulls first!

answered Mar 21 '14 at 20:55

Óscar López

232,561
37
312
386

score 1 · Answer 2 · edited May 23 '17 at 10:31

1

I don't know whether this is the reason for you Exception but you you have to switch your tests in the while loop:

while (head != null && head.getNext() != null)

When you first test for head.getNext() != nulland head is null a NullPointerException will be thrown

For more information look here

edited May 23 '17 at 10:31

Community

1
1

answered Mar 21 '14 at 20:57

Ennosigaeon

442
7
15

score 0 · Answer 3 · answered Mar 21 '14 at 20:58

0

You are over-thinking this problem.

Consider what you need to accomplish: Write a function that delete LinkedList elements whose value is greater than that of the preceding element.

After reading this statement you should have an idea of what you need to consider at every point the LinkedList (e.g the current element, and the previous element). So there is really no-need for a nested while loop.

Pseudo-code:

current  = head 
previous = null

while current is not null
   is previous non-null and current > previous?
      if yes: delete current
      if  no: do nothing

   previous = current
   current  = current.next

See if you can use this pseudo-code to simplify your own code.

answered Mar 21 '14 at 20:58

Hunter McMillen

59,865
24
119
170

adapted that for java code and added it to the main question - still a null pointer exception. but it does make more sense this way. thanks so far – user3362954 Mar 21 '14 at 21:13
Because you are doing the null check improperly – Hunter McMillen Mar 21 '14 at 21:18
There's other ways of checking null....? Or did you means just by changing it to previous != null ? Which in turn, doesn't yield the write output, but closer. Thank you. – user3362954 Mar 21 '14 at 21:19
The problem isn't that previous.getValue() is null, but previous itself is null – Hunter McMillen Mar 21 '14 at 21:25
I think I changed, it, but it's still incorrect. Been fiddling for the past 30 minutes trying to figure out why it doesn't account for the two elements? (updated question with new code) – user3362954 Mar 21 '14 at 22:07

ajb · Answer 4 · 2014-03-22T00:24:02.610

Besides the incorrect check on head that others have mentioned, I think there are some potential issues with this:

    while(temp.getValue().compareTo(head.getValue()) > 0){
        largest = temp.getValue();
        remove(largest);
        System.out.println(largest); // debug
        if(temp.getNext() == null){
            break;
        }
        temp = head.getNext();
    }
    head = temp;

temp will refer to a node that is about to get removed. What happens to that node? I don't know, because I don't know what list type this is or what remove does. However, unless the documentation of the list class made it clear that remove would not affect the node's "next" pointer, I wouldn't count on it. As a general rule, that kind of data should be saved before a remove call. (In other languages, where you might have a "remove" that also explicitly deallocates storage, it would definitely be necessary to save the link first.)

The more serious problem is, even if the "next" pointer stays the same, what happens at the end of the list. temp points to a node that is then removed. Its "next" pointer is null, so you break. But then you set head = temp, which means head now points to a node that is no longer in the list. I think you want head = temp only if you get to that point because of the compareTo--not if you get there because you hit the end of the list.

NullPointerException when iterating over linked list

4 Answers4