Question

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.
Demonstrate by inserting keys at random, displayForward(), call remove then displayForward() again.
You will then attach a modified DoublyLinkedList.java (to contain the new priorityInsert(long key) and priorityRemove() methods), and a driver to demonstrate as shown above.

Use the provided PQDoublyLinkedTest.java to test your code.

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

_____________________________________________________________________________________________________________________________________________________

// doublyLinked.java
// demonstrates doubly-linked list
// to run this program: C>java DoublyLinkedApp

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

} // end class DoublyLinkedList

class DoublyLinkedApp
{
public static void main(String[] args)
{ // make a new list
DoublyLinkedList theList = new DoublyLinkedList();

theList.insertFirst(22); // insert at front
theList.insertFirst(44);
theList.insertFirst(66);

theList.insertLast(11); // insert at rear
theList.insertLast(33);
theList.insertLast(55);

theList.displayForward(); // display list forward
theList.displayBackward(); // display list backward

theList.deleteFirst(); // delete first item
theList.deleteLast(); // delete last item
theList.deleteKey(11); // delete item with key 11

theList.displayForward(); // display list forward

theList.insertAfter(22, 77); // insert 77 after 22
theList.insertAfter(33, 88); // insert 88 after 33

theList.displayForward(); // display list forward
} // end main()
} // end class DoublyLinkedApp

____________________________________________________________________________________________________________________________________________________

Answer 1

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