- #1
Enharmonics
- 29
- 2
Homework Statement
Basically, as the thread title says, I've got to implement a Priority Queue with a Doubly-Linked List in Java.
This is an excerpt from the instructions for the assignment:
I've assumed that priority is given to larger integers (since it wasn't specified in the instructions), but will ask my professor for specifics next time I'm in class
Homework Equations
The Attempt at a Solution
I've actually got the code more-or-less working as intended. Here it is (some non-crucial methods omitted for brevity):
Java:
public class LinkedList
{
// A private nested class that represents the actual "links",
// or "nodes", in the LinkedList
private static class Link
{
// Data fields for the Link class. Visibility
// doesn't matter since it's a private nested class
// The actual data that will be stored in each link
public int data;
// A reference to the next link in the list
public Link next;
// A reference to the previous link in the list
public Link previous;
// Constructor for the Link class
public Link(int d, Link n, Link p)
{
data = d;
next = n;
previous = p;
}
// Returns the data stored inside a link
// as a String.
public String toString()
{
return data + "\n";
}
}
// Data fields for the LinkedList class
private int listSize;
// This node will at first serve to mark
// the beginning of the list, but will
// then be updated to be the newest link
// added to the list (that is, the "first
// link" in the list)
private Link firstLink;
// This node marks the end of the list
private Link lastLink;
// Constructor for the LinkedList() class
// Uses the reset method to initialize
// the LinkedList
public LinkedList()
{
reset();
}
// Methods of the LinkedList class. Note that these are all standard
// for a LinkedList class (they can all be found in Oracle's documentation
// for the "official" LinkedList class located in the java.util package)
// Accessor for the lists' size
public int getSize()
{
return listSize;
}
// Returns true if the list is empty
public boolean isEmpty()
{
return getSize() == 0;
}
// New implementation of add method for the priority queue problem.
// This will automatically add elements into the list
// in priority order
public void add(int element)
{
// First we create a new Link, storing
// the data passed into the method in it
// and setting its "next" pointer to the previous
// top link in the list
Link newLink = new Link(element, firstLink, lastLink);
// First, check if the list is empty. If it is, then
// the new link is also the "highest priority" link (of course,
// it would also be the "lowest priority" link in that case)
if (isEmpty())
{
lastLink = newLink;
// The current first link is now the "next"
// link after the new link we just created
newLink.next = firstLink;
// Our new "first link" is now the newly-created
// newLink, since that is now the top link in the list
firstLink = newLink;
}
// Next,, we iterate through the list
// looking for the first link whose priority
// is lower than the element we are attempting to add
else
{
// Now we need 2 more links: one to store the link
// with the highest priority (assumed at first to
// be the "first link", and the other to point
// to the link with the highest priority)
Link current = firstLink;
Link previous = current;
Link temp;
// Iterate through the list, looking for value
// with highest priority
while (element <= current.data && current != null)
{
previous = current;
current = current.next;
}
// After the while loop completes, either we have found
// a link whose element has lower priority than the one
// we are trying to insert or we are at the start of the list
// (that is, the position of lowest priority); either way,
// we have found the proper place to insert our new element
temp = current;
previous.next = newLink;
newLink.previous = previous;
newLink.next = temp;
// Get rid of temp
temp.previous.next = newLink;
temp.previous = newLink;
}
// Increment the size of the list
listSize++;
}
// Removes and returns the first
// element in the list
public int remove()
{
// This will store the data in the top
// link so that we can return it later.
int removedData = firstLink.data;
// This
// In order to remove the link, we simply set
// firstLink to be the "next" link in the list
// (that is, the previous firstLink)
firstLink = firstLink.next;
// Decrement the size of the list
listSize--;
// Return the data stored in the link we just removed
return removedData;
}
// Returns the Link with the highest
// priority element in it
public Link findMax()
{
// Same logic as add() method. We will use these to iterate
// through the list and to remove the link with the highest
// priority value
Link current = firstLink;
// This will store the current highest priority
// value
int currentHighest = firstLink.data;
// This will store the value itself, which will be returned
//int maxPrio;
// Iterate through the list, looking for the highest priority
// element
for (int i = 0; i < listSize; i++)
{
// If the current Link's element is less than or equal to
// than the current highest priority value and
// the current link isn't the last link in the list,
// continue iterating
if (current.data <= currentHighest && current != null)
{
current = current.next;
}
// Otherwise, the current Link element must
// be greater than currentHighest, so update currentHighest
// and continue the search
else
{
currentHighest = current.data;
}
}
// Current is the highest priority element, so return it
return current;
}
// Removes and returns the highest priority
// element in the list
public int removeMax()
{
// Call the findMax() method to
// find the link with highest
// priority
Link removeLink = findMax();
// Store the data to be returned
int maxPrio = removeLink.data;
// Removes the link with highest priority value
removeLink.next.previous = removeLink.previous;
removeLink.previous.next = removeLink.next;
// Decrement list size
listSize--;
// Return highest priority element
return maxPrio;
}
// Returns the highest priority
// element in the list
public int max()
{
return findMax().data;
//return firstLink.data;
}
// Empties the list using the reset method
public void clear()
{
reset();
}
// This method creates the first link and sets the size of the list
// to 0. It can be used during instantiation and to clear the list
private void reset()
{
// The method now creates the first AND last nodes, and
// connects them to each other by setting lastLink's previous
// pointer to firstLink. New links will be
// inserted "between" them.
//firstLink = new Link(0, null, null);
firstLink = new Link(0, lastLink, null);
lastLink = new Link(0, null, firstLink);
listSize = 0;
}
}
}Particularly, my problem seems to be with the add() method.
I wrote a driver to test the class (as the instructions say to do). Short excerpt from it:
Java:
PriorityQueue myQueue = new PriorityQueue();
// Let's test the add() method first
System.out.println("\n--- TEST THE add() METHOD, PART 1---\n");
myQueue.add(1);
// There should be an item in the queue now
System.out.println("Queue size: " + myQueue.getSize());
// add() METHOD TEST 1 PASSED.
// Let's test the max() method. Since 1 is the only
// item in the queue, of course it should be the max
System.out.println("\n--- TEST THE max() METHOD, PART 1 ---\n");
System.out.println("Highest priority item: " + myQueue.max());
// Let's try adding an item of higher priority now
myQueue.add(3);
System.out.println("\nQueue size: " + myQueue.getSize());
// Let's test the max() method again. This time, the max should
// be 3, since 3 is greater than 1 and thus has higher priority
System.out.println("\n--- TEST THE max() METHOD, PART 2---\n");
System.out.println("Highest priority item: " + myQueue.max());The output for the above driver code is:
So far, so good. But then I tried adding another element:
Java:
// Another test for the max() method. First, we'll add 2 to the list.
// 2 is smaller than 3, so it should have lower priority.
myQueue.add(2);
myQueue.display();
System.out.println("\n--- TEST THE max() METHOD, PART 3 ---\n");
// The max should still be 3
System.out.println("Highest priority item: " + myQueue.max());And here's the output (previous output omitted for brevity)
Ouch. Given the fact that the 2 appears in the correct spot, but for some reason the 3 has been replaced by another 1, I assume there's some kind of problem with the logic in the add method. At the time of writing this post, I've been up for over 32 hours straight, because I ended up spinning my wheels through the whole night trying to figure out how to fix this. I just don't know what's wrong, and it seems like thinking about it only makes me more confused now.
My hunch is that it's got something to do with how I iterate through the list (using the previous and current pointers) and how I "insert" newLink into the list, but I don't understand why it would work properly the first two times and not the next.