I need some help clearing up a problem with sorting a Priority Queue+linked list in Java.

Question

Hello I am trying to implement a Priority Queue in Java from scratch with a linked list but I am having a problem sorting elements on insertion. Here is my program thus far, any help would be massively appreciated.

import java.util.Scanner;

public class T0 {

    public static void main(String args[]) {
        Scanner keyboard = new Scanner(System.in);

        PQ myList = new PQ();

        myList.addSort("Z");
        myList.addSort("B");
        myList.addSort("C");
        myList.addSort("B");
        myList.addSort("Z");

        System.out.println(myList.view(0));
        System.out.println(myList.view(1));
        System.out.println(myList.view(2));
        System.out.println(myList.view(3));
        System.out.println(myList.view(4));
    }
}


class PQ {

    Node tail = new Node(null, null);
    int elementCount = 0;

    Node lastAdded = tail;

        public void add(String word) {
        Node added = new Node(word, lastAdded);
        lastAdded=added;
        elementCount++;
    }

    public void addSort(String word){
                Node temp = new Node(null, null);
        for(int n = 0; n<elementCount && word.compareTo(lastAdded.next().toString()) >1; n++){
            temp=lastAdded.next();
        }
        Node added = new Node(word, lastAdded.next());
        lastAdded.changeNext(added);
        elementCount++;
    }

    public String view(int i){
        Node temp = lastAdded;

        for(int n = elementCount; n > i; n--){
            temp=temp.next();
        }
        return temp.toString();

    }
    public String toString() {
        return lastAdded.toString();
    }



    class Node {

        String name;
        Node nextNode;

        public Node(String s, Node n) {
            name = s;
            nextNode = n;
        }
        public void changeNext(Node n){
            nextNode=n;
        }
        public Node next() {
            return nextNode;
        }

        public String toString() {
            return name;
        }
    }
}

Currently outputs:

   run:
Z
B
C
B
Z
BUILD SUCCESSFUL (total time: 1 second)

Upadate: Changed addSort to be:

    public void addSort(String word){
            Node temp = lastAdded;
for(int n = 0; n<elementCount && word.compareTo(lastAdded.next().toString()) > 0; n++){
    temp=lastAdded.next();
}
    Node added = new Node(word, lastAdded.next());
    lastAdded.changeNext(added);
    elementCount++;
    lastAdded=temp;
} 

This throws a null pointer exception at

System.out.println(myList.view(0));

Answer 1

In the addSort method you are assigning a Node temp to (what seems to be) the place you want to insert the node - but then you do not use this reference again after the for-loop.

Answer 2

In the loop

    for(int n = 0; n<elementCount && word.compareTo(lastAdded.next().toString()) >1; n++){
        temp=lastAdded.next();
    }

you are always comparing the new word to the same element, instead of iterating through the list (1a) (and you keep assigning temp the same value inside the loop (1b)). [Update] And you compare the output of compareTo to 1 instead of 0 (2). Thus - depending on the implementation of compareTo - the result may always be false. (AFAIK it would not be for String.compareTo specifically, since it can return values greater than 1 - but this is not guaranteed in general.) [/Update]

And then, regardless of the result of your checks, you always add the new element after the last added element (3).

However, since you don't adjust lastAdded (4), it will keep pointing to the same element (tail), so in effect tail will always be the first item in your list, not the last.

Update 2: in your updated addSort, you fixed issues (2) and (4) above, but (1a-b) and (3) are still there.

Part of the problem is that for a singly linked list to work, you need to keep a reference to its head at all times - otherwise you have no way to walk through it! You are sort of trying to use lastAdded for this purpose, but this is just mixing two different things, causing further confusion. Note that you don't actually need a reference to the last added node - this information is of no use when you are about to insert the next element into the list. I recommend bringing a dedicated head reference into the picture, and changing the code accordingly (and dropping lastAdded unless you are sure you are going to need it later). Note that this does not eliminate the need for (4) - even if you have a head reference only, you still need to modify it (although not always - only when inserting at the beginning of the list).