Thread: Priority Queue Linked List Help

So I'm been trying to figure out what I'm doing wrong with this for hours now and I'm just completely stuck. For this assigment we need to create a Linked List Priority Queue. What's making it difficult for me is that we need to have an array of all the first nodes from the queue. So for example, position 0 in the array should be the first node of the first entry for priority 1. Everything I've been trying is losing what I've previously added to the queue.

Here's some of the code I have so far:

    public class LinkedPriorityQueue<T extends Comparable<? super T>>
             implements PriorityQueueInterface<T>
{
   private Node[] firstNode; // reference to first node of chain and the front 
                           // of the priority queue, which has the 
                           // highest priority
   private int  length;    // number of entries in chain
 
   public LinkedPriorityQueue(int max)
    {
       firstNode =  (Node[])new LinkedPriorityQueue.Node[max];
       for (int index = 0; index < max; index ++)
       {
           firstNode[index] = new Node(null);
       }
      length = 0;
   } // end default constructor
 
   public void add(T newEntry, int priority)
   {
      Node newNode = new Node(newEntry, null);
 
      Node nodeBefore = getNodeBefore(newEntry, priority);
 
      if(nodeBefore == null)
      {
         newNode.setNextNode(firstNode[priority]);
         firstNode[priority] = newNode;
      }
      else                                   // add after nodeBefore
      {
         Node nodeAfter = nodeBefore.getNextNode();
         newNode.setNextNode(nodeAfter);
         nodeBefore.setNextNode(newNode);
      } // end if
 
      length++;
      //display();
   } // end add
 
private Node getNodeBefore(T anEntry, int priority)
   {
     Node currentNode = firstNode[priority];
     Node nodeBefore = null;
 
     while ((currentNode.getData() != null))
     {
        nodeBefore = currentNode;
        currentNode = currentNode.getNextNode();
     } // end while
 
     return nodeBefore;
   } // end getNodeBefore

Most of this was given to us from our textbook, we're just supposed to modify it to handle an array of first nodes. I think my issue is that I'm not linking the nodes properly when I add a new entry but I can't figure out how to fix it.

Well I'd really appreciate any help you can offer me, and if there's more info you need from me just ask, and sorry for posting so much, I just wanted to make sure you had an enough info to help.

How are you testing it? How do you know it is or isn't working correctly? If you have sample runs, errors, or results from an online checking program, post those. Not sure what your question is or what we can help you with.

Sorry for not being clearer. I'm testing it from my driver I have which is adding the data to the queue. It just reads in the data from a file and then uses the add method in the priority queue to add the data and the priority. I know it's not working because I've used System.out.println to output what's in the queue and it's only holding the last added item, everything else is null.

Here's the code I have to display everything in the queue.

public void display()
   {
      for(int i = 0; i < firstNode.length; i++)
      {
    	  Node currentNode = firstNode[i];
 
    	  while (currentNode != null)
      	  { 
    		  System.out.println(currentNode.getData());
    		  currentNode = currentNode.getNextNode(); 
      	  } // end while  
      }

When I call this method after adding everything to the queue everything prints out as null except for the last added entry. If you need more info just let me know, I just didn't want to post too much.

So there are several possible sources of the "error(s)" you're experiencing:

Data isn't being read from the file correctly
Data read from the file isn't being used to add items to the queue
The queue's add() method doesn't add new items, only replaces one item in the queue with the latest
The items in the queue aren't being incremented when an item is added
The queue iterator that reads the items in the queue and prints them isn't correct
The queue methods used by the iterator aren't correct

Try to isolate the problem to the above possible source(s) or others I haven't thought of by adding print statements to loops and methods that read, add, iterate, etc. to determine what's letting you down. I can't test it for you without the data file and would rather help you figure it out than do it for you anyway.

I can tell you it definitely isn't a problem with reading in from the file, because I had this entire program working fine but I had to adjust it to implement the array of nodes. I'm thinking it might be an issue with the add() method because when I put a print statement at the end of the method it always prints the last added item only.

And here's something else I just found by testing, apparently my length variable isn't holding it's value, every time the add method is called length is 0 again. That should keep incrementing as new items are added but it's not doing that, I'm thinking this probably has something to do with my issue, I just can't figure out why it would do this.

So focus on the add() method, and the add() method relies heavily on the getNodeBefore() method, so check that. And getNodeBefore() relies on getData() and getNextNode(), so you'll have to check those.

getNodeBefore() looks suspicious to me, but I'm not saying that's the problem.

I also notice that in add() if nodeBefore == null, then nodeAfter = nodeBefore.getNextNode(), but if nodeBefore is null, what the heck will nodeBefore.getNextNode() be?

Plus, having to ask the question above reminds me that you should comment your code. What I just asked should be clearly explained in code comments. It'll help you keep all of this node shuffling straight, it'll document what you're trying to do and then give you a check of the code to see if it makes sense. Don't tell me you're one of those who "comments it when I'm done." I don't believe it, and it's lame.

If you were to write out in plain language what this code should do, it's pretty simple. The add method is:

find the last item in the queue (with the same priority?)
if the next item is null, replace the null item with the item being added
if the next item is not null, insert the new item being added between the item found and the next item.

Something like that, because I'm not sure exactly what you're doing. But once you write out those steps in plain language, you can then write corresponding code and see when the code does't make sense when compared to the plain language description. At least that's how it works for me.

Yeah I've been trying to work on the add() method for a while now since I've suspected that's been the issue. One thing I tried to do that my teacher mentioned is to keep a lastNode as well for each priority, that would allow me to eliminate the getNodeBefore method which I didn't like any way, I was just still having the same issues so I scrapped it.

Unless I'm looking at it wrong, nodeAfter = nodeBefore.getNextNode() is in the else branch so it should only be ran if nodeBefore != null, that was the textbook's code anyway.

I agree with including comments to make it easier to understand and I normally do try to include them, it was difficult for this one since like I said, this is just code from our textbook that we're supposed to modify and they have no comments and they don't explain anything.

In plain language my the add method should:

Look at the firstNode corresponding to the priority of the entry being added.
If that chain is empty then I should add it to the begining and set the firstNode for that priority to the entry that was added.
If that chain is not empty, then I should add it to the end and set the previous node's next to point to the newly added entry.

Looking at this plain language description I might try and remove a lot of the methods that I modified from the previous implementation, such as that getNodeBefore(), because I think the code I have is much more complicated than it should be. I'm basically either adding to the beginning of a chain if it's the first of that priority, or the end if it has at least one other entry for that priority.

Ya, I forgot that a lot of the code was provided from the book, which can be a blessing or a curse. To be a blessing, you have to understand it. I document my understanding of provided code by adding comments to it if it's not already commented or commented badly. Sometimes that means I actually have to read the book or the web page to understand what the author is doing, and sometimes even that's not enough. Those times when the provided explanations are not enough, I actually have to study every line and figure it out, and then I document my understanding in code comments.

I have a sense that the code you were provided does not have the array of first nodes of each priority that your instructor is requiring, so you have to add that feature to the provided code. Considering that and your plain language description:

Look at the firstNode corresponding to the priority of the entry being added.
If that chain is empty then I should add it to the beginning and set the firstNode for that priority to the entry that was added.
If that chain is not empty, then I should add it to the end and set the previous node's next to point to the newly added entry.

The array of firstNodes for each priority simplifies this a bit. If adding a node of priority 5, check to see if there's already a first priority 5 node. If there isn't one, this one's it. If there is already one, then check to see if there's a first node with priority 6. If not, then start with the first priority 5 node and insert this new priority 5 node at the end of that chain. If there is a first priority 6 node, then insert this new priority 5 node right before the priority 6 node.

Okay so first of all I really appreciate all the help you've been offering me, because I felt really stuck before with all this.

So I just had another long response almost written about how even after I rewrote the add() method it was still giving me the same issues, but before I posted it I decide to go over my driver class one more time and I found the problem! I had a while loop for reading the data from the file and inside the while loop I was creating a new LinkedPriorityQueue every time through the loop. That's why I was only seeing the last one added and that's why the length variable wasn't incrementing, because every time it was adding to a new list. It was like that from the last way I had it implemented and I must not of caught it when I was redoing it. Now I just have to fix the remove() methods for the array implementation, but I shouldn't have a problem anymore since I've got it working now. Thank you again for helping me and I'll definitely keep in mind the tips you gave me for the future, especially about the commenting!

It's frustrating to find errors in code you were sure was perfect! You'll make both of those errors again, assuming code can't be broken and making new objects when you shouldn't, so be looking for them.

I'll definitely keep in mind the tips you gave me for the future, especially about the commenting!

I doubt it. You don't think comments are that important, and they require extra work, so why bother? Someday maybe you'll see the benefit.

Glad you found the error, good luck with the rest. Keep coding.