0

I am having difficulties implementing a priority queue using an SLList due to the problem of sorting the list.

When I try to compare content of Nodes in the add(x) method, after compiling, I get a NullPointerException.

How can I avoid this?

Node Class:

class Node<T extends Comparable<T>> {
    T x;
    Node<T> next;
} // end of class Node

Global Variables:

Node<T> head; // Front of the SLList

Node<T> tail; // Tail of the SLList

int n; // Number of elements in the SLList

add(x) method:

/** Adds elements to the SLList ensuring that they are in the order of smallest to largest */
public void add(T x) {
    Node<T> u = new Node<T>();
    u.x = x;

    Node<T> previous = head;

    while ((previous.x.compareTo(u.x) < 1) && (previous.x != null)) { // error: NullPointerException thrown
        previous = previous.next;
    }

    Node<T> current = previous.next;
    u.next = current;
    previous.next = u;

    n++; // Increases the list element counter by 1
} // End of add(x) subroutine

I have already tried the solution outlined here: NullPointerException when comparing the data in two nodes

(without success).

Edit:

The original NullPointerException was fixed, however; this caused another NullPointerException, and I am trying to fix it with an If-Else condition.

Error:

Exception in thread "main" java.lang.NullPointerException: Cannot read field "next" because "< local3 >" is null at SLList.add(SLList.java:27) at SLList.main(SLList.java:53)

It looks like when I executed the program, the block in the if part of the if-else statement was executed despite the condition.

public class SLList<T extends Comparable<T>> {

    /** Defines a Node in the context of a SLList */
    class Node<T extends Comparable<T>> {
        T x;
        Node<T> next;
    } // end of class Node

    Node<T> head; // Front of the SLList

    Node<T> tail; // Tail of the SLList

    int n = 0; // Number of elements in the SLList

    /** Adds elements to the SLList ensuring that they are in the order of smallest to largest */
    public void add(T x) {
        Node<T> u = new Node<T>();
        u.x = x;
        Node<T> previous = head;
        if (previous != null) {
            while ((previous != null) && (previous.x.compareTo(u.x) < 1)) { 
                previous = previous.next;
            }
            Node<T> current = previous.next; //Error here
            u.next = current;
            previous.next = u;
        } else {
            tail = u;
            head = u;
        }
        n++; // Increases the list element counter by 1
    } // End of add(x) subroutine

  /** Deletes the first value from the list and sets the second value to the head */
  public T deleteMin() {
    T x = head.x;
    head = head.next;
        n--; // Decreases the list element counter by 1
    return x;
  } // End of deleteMin() subroutine

  /** Returns the first and smallest value of the list */
  public int size() {
    return n;
  } // End of size() subroutine

  public static void main(String[] args) {
    SLList<Integer> q = new SLList<Integer>();
    for (int i = 0; i < 100; i++) {
        q.add(i);
    }
    int min = q.deleteMin();
    System.out.print(min);
  } //End of main() subroutine

Edit #2: Thank you @JeroneSteenBeeke ! I was able to solve the problem. Solution posted below:

public class SLList<T extends Comparable<T>> {

    /** Defines a Node in the context of a SLList */
    class Node<T extends Comparable<T>> {
        T x;
        Node<T> next;
    } // end of class Node

    Node<T> head; // Front of the SLList

  Node<T> tail; // Tail of the SLList

  int n = 0; // Number of elements in the SLList

  /** Adds elements to the SLList ensuring that they are in the order of smallest to largest */
  public void add(T x) {
        Node<T> u = new Node<T>();
        u.x = x;
        Node<T> previous = head;
        if (previous != null) {
            while ((previous.x.compareTo(u.x) < 1 && previous.next != null)) { // Error fixed, added "&& previous.next != null"
                previous = previous.next;
            }
            Node<T> current = previous.next;
            u.next = current;
            previous.next = u;
        } else {
            tail = u;
            head = u;
            previous = head;
        }
    n++; // Increases the list element counter by 1
  } // End of add(x) subroutine

    /** Deletes the first value from the list and sets the second value to the head */
  public T deleteMin() {
    T x = head.x;
    head = head.next;
        n--; // Decreases the list element counter by 1
    return x;
  } // End of deleteMin() subroutine

    /** Returns the first and smallest value of the list */
  public int size() {
    return n;
  } // End of size() subroutine

    public static void main(String[] args) {
        SLList<Integer> q = new SLList<Integer>();
        for (int i = 0; i < 100; i++) {
            q.add(i);
        }
    int min = q.deleteMin();
    System.out.print(min);
    } //End of main() subroutine
} // End of class SLList

krjakub
  • 1
  • 1
  • I'm reasonably sure that `previous` is null. Also you should put the null-check in your `while`-loop first – Jeroen Steenbeeke Jul 06 '21 at 14:49
  • Hello @JeroenSteenbeeke , thank you for your advice. I tried to fix the problem by changing the condition to `((previous != null) && (previous.x.compareTo(u.x) < 1))`. Now that generated a few more NullPointerExceptions. When I tried to fix them with an if-else statement, I still got the same error. I will update the question with the whole program. . . – krjakub Jul 06 '21 at 15:44
  • Your updated while-loop repeats until `previous` is `null` and then tries to read the property `x` of `previous` (which is now always `null`, otherwise you'd still be inside the loop) – Jeroen Steenbeeke Jul 07 '21 at 16:23

0 Answers0