In: Computer Science
Implement a priority queue using a DoublyLinkedList
where the node with the highest priority (key) is the right-most
node.
The remove (de-queue) operation returns the node with
the highest priority (key).
If displayForward() displays List (first-->last) : 10 30 40
55
remove() would return the node with key 55.
You will then attach priorityInsert(long key) and priorityRemove() methods). AND Use the provided PQDoublyLinkedTest.java to test your code.
BOTH CODES SHOULD WORK TOGETHER, YOU JUST HAVE TO ADD priorityInsert(int). PLEASE PROVIDE CORRECT CODE.
class Link {
public long dData;
public Link next;
public Link previous;
public Link(long d) {
dData = d;
}
public void displayLink() {
System.out.print(dData + " ");
}
}
class DoublyLinkedList {
private Link first;
private Link last;
public DoublyLinkedList() {
first = null;
last = null;
}
public boolean isEmpty() {
return first == null;
}
public void insertFirst(long dd) {
Link newLink = new Link(dd);
if (isEmpty())
last = newLink;
else
first.previous = newLink;
newLink.next = first;
first = newLink;
}
public void insertLast(long dd) {
Link newLink = new Link(dd);
if (isEmpty())
first = newLink;
else {
last.next = newLink;
newLink.previous = last;
}
last = newLink;
}
public Link deleteFirst() {
Link temp = first;
if (first.next == null)
last = null;
else
first.next.previous = null;
first = first.next;
return temp;
}
public Link deleteLast() {
Link temp = last;
if (first.next == null)
first = null;
else
last.previous.next = null;
last = last.previous;
return temp;
}
public boolean insertAfter(long key, long dd) {
Link current = first;
while (current.dData != key){
current = current.next;
if (current == null)
return false;
}
Link newLink = new Link(dd);
if (current == last) {
newLink.next = null;
last = newLink;
}
else {
newLink.next = current.next;
current.next.previous = newLink;
}
newLink.previous = current;
current.next = newLink;
return true;
}
public Link deleteKey(long key) {
Link current = first;
while (current.dData != key) {
current = current.next;
if (current == null)
return null;
}
if (current == first)
first = current.next;
else
current.previous.next = current.next;
if (current == last)
last = current.previous;
else
current.next.previous = current.previous;
return current;
}
public void displayForward() {
System.out.print("List (first-->last): ");
Link current = first;
while (current != null)
{
current.displayLink();
current = current.next;
}
System.out.println("");
}
public void displayBackward() {
System.out.print("List (last-->first): ");
Link current = last;
while (current != null)
{
current.displayLink();
current = current.previous;
}
System.out.println("");
}
public void insertSorted(long key) {
if (isEmpty() || key < first.dData) {
insertFirst(key);
return;
}
Link current = first;
while (current.next != null) {
if (key >= current.dData && key <=
current.next.dData) {
Link lnk = new Link(key);
lnk.next = current.next;
current.next.previous = lnk;
current.next = lnk;
lnk.previous = current;
return;
}
current = current.next;
}
insertLast(key);
}
}
public class PriorityLinkQueue {
private DoublyLinkedList list;
public PriorityLinkQueue() {
list = new DoublyLinkedList();
}
public void insert(long key) {
list.insertSorted(key);
}
public long remove() {
if (list.isEmpty()) {
throw new RuntimeException("Priority Queue is empty!");
}
return list.deleteLast().dData;
}
public boolean isEmpty() {
return list.isEmpty();
}
public void displayForward() {
list.displayForward();
}
}
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
class PQDoublyLinkedTest.JAVA ->>> ONLY FOR TESTING, DO NOT CHANGE ANYTHING IN PQDoublyLinkedTest.JAVA
public class PQDoublyLinkedTest
{
public static void main(String[] args)
{ // make a new list
DoublyLinkedList theList = new DoublyLinkedList();
theList.priorityInsert(22); // insert at front
theList.priorityInsert(44);
theList.priorityInsert(66);
theList.priorityInsert(11); // insert at rear
theList.priorityInsert(33);
theList.priorityInsert(55);
theList.priorityInsert(10);
theList.priorityInsert(70);
theList.priorityInsert(30);
theList.displayForward(); // display list forward
Link2 removed = theList.priorityRemove();
System.out.print("priorityRemove() returned node with key:
");
removed.displayLink2();
} // end main()
} // end class PQDoublyLinkedTest
Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks
//updated DoublyLinkedList file to include the new insert method (inserts a key in sorted order)
class Link {
public long dData; // data item
public Link next; // next link in list
public Link previous; // previous link in list
// -------------------------------------------------------------
public Link(long d) // constructor
{
dData = d;
}
// -------------------------------------------------------------
public void displayLink() // display this link
{
System.out.print(dData + " ");
}
// -------------------------------------------------------------
} // end class Link
// //////////////////////////////////////////////////////////////
class DoublyLinkedList {
private Link first; // ref to first item
private Link last; // ref to last item
// -------------------------------------------------------------
public DoublyLinkedList() // constructor
{
first = null; // no items on list yet
last = null;
}
// -------------------------------------------------------------
public boolean isEmpty() // true if no links
{
return first == null;
}
// -------------------------------------------------------------
public void insertFirst(long dd) // insert at front of list
{
Link newLink = new Link(dd); // make new link
if (isEmpty()) // if empty list,
last = newLink; // newLink <-- last
else
first.previous = newLink; // newLink <-- old first
newLink.next = first; // newLink --> old first
first = newLink; // first --> newLink
}
// -------------------------------------------------------------
public void insertLast(long dd) // insert at end of list
{
Link newLink = new Link(dd); // make new link
if (isEmpty()) // if empty list,
first = newLink; // first --> newLink
else {
last.next = newLink; // old last --> newLink
newLink.previous = last; // old last <-- newLink
}
last = newLink; // newLink <-- last
}
// -------------------------------------------------------------
public Link deleteFirst() // delete first link
{ // (assumes non-empty list)
Link temp = first;
if (first.next == null) // if only one item
last = null; // null <-- last
else
first.next.previous = null; // null <-- old next
first = first.next; // first --> old next
return temp;
}
// -------------------------------------------------------------
public Link deleteLast() // delete last link
{ // (assumes non-empty list)
Link temp = last;
if (first.next == null) // if only one item
first = null; // first --> null
else
last.previous.next = null; // old previous --> null
last = last.previous; // old previous <-- last
return temp;
}
// -------------------------------------------------------------
// insert dd just after key
public boolean insertAfter(long key, long dd) { // (assumes non-empty list)
Link current = first; // start at beginning
while (current.dData != key) // until match is found,
{
current = current.next; // move to next link
if (current == null)
return false; // didn't find it
}
Link newLink = new Link(dd); // make new link
if (current == last) // if last link,
{
newLink.next = null; // newLink --> null
last = newLink; // newLink <-- last
} else // not last link,
{
newLink.next = current.next; // newLink --> old next
// newLink <-- old next
current.next.previous = newLink;
}
newLink.previous = current; // old current <-- newLink
current.next = newLink; // old current --> newLink
return true; // found it, did insertion
}
// -------------------------------------------------------------
public Link deleteKey(long key) // delete item w/ given key
{ // (assumes non-empty list)
Link current = first; // start at beginning
while (current.dData != key) // until match is found,
{
current = current.next; // move to next link
if (current == null)
return null; // didn't find it
}
if (current == first) // found it; first item?
first = current.next; // first --> old next
else
// not first
// old previous --> old next
current.previous.next = current.next;
if (current == last) // last item?
last = current.previous; // old previous <-- last
else
// not last
// old previous <-- old next
current.next.previous = current.previous;
return current; // return value
}
// -------------------------------------------------------------
public void displayForward() {
System.out.print("List (first-->last): ");
Link current = first; // start at beginning
while (current != null) // until end of list,
{
current.displayLink(); // display data
current = current.next; // move to next link
}
System.out.println("");
}
// -------------------------------------------------------------
public void displayBackward() {
System.out.print("List (last-->first): ");
Link current = last; // start at end
while (current != null) // until start of list,
{
current.displayLink(); // display data
current = current.previous; // move to previous link
}
System.out.println("");
}
/**
* method to insert a key in sorted order
*
* @param key
* key to be added
*/
public void insertSorted(long key) {
// if list is empty or key is less than current first, inserting at
// first
if (isEmpty() || key < first.dData) {
insertFirst(key);
return; // exiting method
}
// taking a reference to first
Link current = first;
// looping as long as current.next is not null
while (current.next != null) {
// checking if key can be added between current and current.next
if (key >= current.dData && key <= current.next.dData) {
// adding between current and current.next and updating all
// links
Link lnk = new Link(key);
lnk.next = current.next;
current.next.previous = lnk;
current.next = lnk;
lnk.previous = current;
return; //exiting
}
//otherwise, advancing to next link
current = current.next;
}
//if the element is still not inserted, adding to the end
insertLast(key);
}
// -------------------------------------------------------------
} // end class DoublyLinkedList
// PriorityLinkQueue.java (representing a Priority Queue using the above doubly linked list)
//class representing a PriorityLinkQueue
public class PriorityLinkQueue {
// using a DoublyLinkedList as instance variable
private DoublyLinkedList list;
// constructor initializing empty pq
public PriorityLinkQueue() {
list = new DoublyLinkedList();
}
// inserts a key in proper position
public void insert(long key) {
list.insertSorted(key);
}
// removes and returns the element with highest value
public long remove() {
// if empty, throwing an exception
if (list.isEmpty()) {
throw new RuntimeException("Priority Queue is empty!");
}
// otherwise, removing last value from doubly list and returning the
// data
return list.deleteLast().dData;
}
// returns true if pq is empty
public boolean isEmpty() {
return list.isEmpty();
}
// displays the queue forward
public void displayForward() {
list.displayForward();
}
// main method for testing the new PriorityLinkQueue, move this code to
// anywhere else if you want to.
public static void main(String[] args) {
// creating a queue
PriorityLinkQueue q = new PriorityLinkQueue();
// adding 10 random keys between 0 and 99 to the queue, displaying it
// after every insertion
for (int i = 0; i < 10; i++) {
q.insert((long) (Math.random() * 100));
q.displayForward();
}
// looping and removing all entries from queue, displaying the queue
// after every removal
while (!q.isEmpty()) {
System.out.println(q.remove() + " is removed");
q.displayForward();
}
}
}
/*OUTPUT*/
List (first-->last): 39
List (first-->last): 4 39
List (first-->last): 4 9 39
List (first-->last): 4 9 14 39
List (first-->last): 4 5 9 14 39
List (first-->last): 4 5 9 13 14 39
List (first-->last): 4 5 9 13 14 39 74
List (first-->last): 4 5 9 13 14 39 74 95
List (first-->last): 4 5 9 13 14 39 74 90 95
List (first-->last): 4 5 9 13 14 36 39 74 90 95
95 is removed
List (first-->last): 4 5 9 13 14 36 39 74 90
90 is removed
List (first-->last): 4 5 9 13 14 36 39 74
74 is removed
List (first-->last): 4 5 9 13 14 36 39
39 is removed
List (first-->last): 4 5 9 13 14 36
36 is removed
List (first-->last): 4 5 9 13 14
14 is removed
List (first-->last): 4 5 9 13
13 is removed
List (first-->last): 4 5 9
9 is removed
List (first-->last): 4 5
5 is removed
List (first-->last): 4
4 is removed
List (first-->last):