# Implementing a PriorityQueue w/ a Doubly-Linked List (Java)

• Comp Sci
• Enharmonics
In summary: Methods for getting elements from the priority queue public int get() { // If the list is empty, return -1 if(isEmpty()) return -1; // Otherwise, return the value of the element at the head of the queue return (getSize()-1)%getSize(); } // Gets the element at the head of the priority queue public int getFirst()
Enharmonics

## 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

## 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

{
// 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

// A reference to the previous link in the list

// Constructor for the Link class

{
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
// added to the list (that is, the "first

// This node marks the end of the list

// Constructor for the LinkedList() class
// Uses the reset method to initialize

{
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

{
// 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

// 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())
{

// The current first link is now the "next"

// Our new "first link" is now the newly-created
// newLink, since that is now the top link in the list

}

// 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)

// 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;

// Get rid of temp

}

// 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.

// This

// In order to remove the link, we simply set
// (that is, the previous firstLink)

// 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

{

// Same logic as add() method. We will use these to iterate
// through the list and to remove the link with the highest
// priority value

// This will store the current highest priority
// value

// 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
// 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

// Store the data to be returned

// Removes the link with highest priority value

// Decrement list size

listSize--;

// Return highest priority element

return maxPrio;
}

// Returns the highest priority
// element in the list

public int max()
{
return findMax().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
// inserted "between" them.

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");

// 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

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:

--- TEST THE add() METHOD, PART 1---

Queue size: 1

--- TEST THE max() METHOD, PART 1 ---

Highest priority item: 0

Queue size: 2

--- TEST THE max() METHOD, PART 2---

Highest priority item: 3

1

3

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.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)

[previous output goes here]
-----
1

2

1

--- TEST THE max() METHOD, PART 3 ---

Highest priority item: 1

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.

Maybe I'm misreading; I haven't actually compiled the code and gone through it with a debugger. But here are some thoughts, for what they're worth.

When the List is initially constructed Two Links are instantiated in the method reset(). These two Links appear to me to be "dummy" links that are initially assigned to the List's "firstLink" and "lastLink" properties. This happens before the add() method is ever called.
Code:
    private void reset()
{
// The method now creates the first AND last nodes, and
// connects them to each other by setting lastLink's previous
// inserted "between" them.

listSize = 0;
}
So even before the add() method is called, there are two instances of Link that exist.

and then the following block of code is executed:
Code:
        if (isEmpty())
{

// The current first link is now the "next"

// Our new "first link" is now the newly-created
// newLink, since that is now the top link in the list

}

Let's go through that line by line.
There's still a reference to the old instance of newLink lastLink stored in the firstLink instance, so the garbage collector won't clean up the previous lastLink just yet.
Now newLink's "next" reference is pointing to the dummy instance called firstLink.

Something to keep in mind at this point. There are still 3 instances of Link. No garbage collection has been done since references to each instance still exist.

newLink.next points to the old dummy instance that was once called firstLink. Now this instance doesn't have that name, but a reference to it still exists.

The old lastLink still exists too since the old firstLink (now referenced through newLink.next) still refers to it.

I don't find the "next" and "previous" properties of the dummy Instances ever being updated at all.

I'm not sure if this is this is what you want to do. It seems hard to follow, and something about it doesn't seem quite right. I'm assuming that the problem may be in this part of the code somewhere. [Edit: Rather than reassign, lastLink = newLink, and firstLink = newLink, maybe you should rather change the "next" and "previous" properties of lastLink and firstLink. That might be what is going wrong here.]

Another related thing: If you do intend of keeping the dummy instances around, rather than give them both priority 0, give one of them priority 0 or maybe a negative priority (like int.MIN_VALUE), and the other one one the maximum possible priority (like int.MAX_VALUE). Then when searching for Link elements, make a check so you don't accidentally return either of those. -- Or for a different paradigm, make your List so that it doesn't need these dummy Links.

Last edited:
collinsmark said:
Maybe I'm misreading; I haven't actually compiled the code and gone through it with a debugger. But here are some thoughts, for what they're worth.

When the List is initially constructed Two Links are instantiated in the method reset(). These two Links appear to me to be "dummy" links that are initially assigned to the List's "firstLink" and "lastLink" properties. This happens before the add() method is ever called.
Code:
    private void reset()
{
// The method now creates the first AND last nodes, and
// connects them to each other by setting lastLink's previous
// inserted "between" them.

listSize = 0;
}
So even before the add() method is called, there are two instances of Link that exist.

and then the following block of code is executed:
Code:
        if (isEmpty())
{

// The current first link is now the "next"

// Our new "first link" is now the newly-created
// newLink, since that is now the top link in the list

}

Let's go through that line by line.
There's still a reference to the old instance of newLink lastLink stored in the firstLink instance, so the garbage collector won't clean up the previous lastLink just yet.
Now newLink's "next" reference is pointing to the dummy instance called firstLink.

Something to keep in mind at this point. There are still 3 instances of Link. No garbage collection has been done since references to each instance still exist.

newLink.next points to the old dummy instance that was once called firstLink. Now this instance doesn't have that name, but a reference to it still exists.

The old lastLink still exists too since the old firstLink (now referenced through newLink.next) still refers to it.

I don't find the "next" and "previous" properties of the dummy Instances ever being updated at all.

I'm not sure if this is this is what you want to do. It seems hard to follow, and something about it doesn't seem quite right. I'm assuming that the problem may be in this part of the code somewhere. [Edit: Rather than reassign, lastLink = newLink, and firstLink = newLink, maybe you should rather change the "next" and "previous" properties of lastLink and firstLink. That might be what is going wrong here.]

Another related thing: If you do intend of keeping the dummy instances around, rather than give them both priority 0, give one of them priority 0 or maybe a negative priority (like int.MIN_VALUE), and the other one one the maximum possible priority (like int.MAX_VALUE). Then when searching for Link elements, make a check so you don't accidentally return either of those. -- Or for a different paradigm, make your List so that it doesn't need these dummy Links.

You're absolutely right. Thanks so much for pointing that out. I hadn't realized that I had been overwriting firstLink and lastLink repeatedly rather than actually inserting "between" them by using their next and previous pointers. As soon as I sorted that out, things got better. That's what I get for trying to pull an all-nighter with no breaks, I guess. Thanks again for the help!

collinsmark

## What is a PriorityQueue?

A PriorityQueue is a data structure that stores elements in a certain order, and allows for efficient retrieval of the highest priority element. In a PriorityQueue with a doubly-linked list implementation, the highest priority element will be at the head of the list.

## How is a PriorityQueue implemented with a doubly-linked list in Java?

In Java, a PriorityQueue with a doubly-linked list can be implemented by creating a class that has a doubly-linked list as its underlying data structure. The class should have methods to add elements to the list, remove the highest priority element, and retrieve the highest priority element without removing it.

## What is the time complexity of adding an element to a PriorityQueue with a doubly-linked list?

The time complexity of adding an element to a PriorityQueue with a doubly-linked list is O(1), as the element can be inserted at the front of the list in constant time.

## What is the time complexity of removing the highest priority element from a PriorityQueue with a doubly-linked list?

The time complexity of removing the highest priority element from a PriorityQueue with a doubly-linked list is O(1), as the element is always stored at the head of the list and can be removed in constant time.

## Can a PriorityQueue with a doubly-linked list handle duplicate elements?

Yes, a PriorityQueue with a doubly-linked list can handle duplicate elements. However, the order in which duplicate elements are retrieved may not be consistent, as it depends on the underlying implementation of the doubly-linked list.

• Engineering and Comp Sci Homework Help
Replies
5
Views
2K
• Engineering and Comp Sci Homework Help
Replies
3
Views
1K
• Engineering and Comp Sci Homework Help
Replies
1
Views
1K
• Engineering and Comp Sci Homework Help
Replies
7
Views
1K
• Engineering and Comp Sci Homework Help
Replies
7
Views
2K
• Engineering and Comp Sci Homework Help
Replies
1
Views
1K
• Engineering and Comp Sci Homework Help
Replies
4
Views
2K
• Engineering and Comp Sci Homework Help
Replies
12
Views
1K
• Engineering and Comp Sci Homework Help
Replies
5
Views
2K
• Engineering and Comp Sci Homework Help
Replies
18
Views
1K