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