Programming Project 5.1: Implement a priority queue based on a sorted linked list. I have provided the code to get started in file priorityList.java.This code consists of the sorttedlist.java program...

Programming Project 5.1: Implement a priority queue based on a sorted linked list.

I have provided the code to get started in file priorityList.java.This code consists of the sorttedlist.java program from listing 5.6, along with the main app class (class PriorityQApp) from the PriorityQ.java from Listing 4.6.I have added a shell class PriorityQ, which will be the ADT, as this will implement a Priority Queue based on the underlying sorted linked list.You assignment will be to then add code to the 3 methods from within the class PriorityQ (the methods have a comment "// TBD") - to make it all work.Once you add the methods, you should test it to verify it works.Note, that the remove operation on the priority queue should remove the item with the smallest key.

As always, please deposit ONE SINGLE MS Word file with code (copy/pasted) and screenshots of testing.

// priorityList.java // a priority queue based on a sorted list // to run this program: C>java PiorityQApp //////////////////////////////////////////////////////////////// class Link { public long dData; // data item public Link next; // next link in list // ------------------------------------------------------------- public Link(long dd) // constructor { dData = dd; } // ------------------------------------------------------------- public void displayLink() // display this link { System.out.print(dData + " "); } } // end class Link //////////////////////////////////////////////////////////////// class SortedList { private Link first; // ref to first item // ------------------------------------------------------------- public SortedList() // constructor { first = null; } // ------------------------------------------------------------- public boolean isEmpty() // true if no links { return (first==null); } // ------------------------------------------------------------- public void insert(long key) // insert, in order { Link newLink = new Link(key); // make new link Link previous = null; // start at first Link current = first; // until end of list, while(current != null && key > current.dData) { // or key > current, previous = current; current = current.next; // go to next item } if(previous==null) // at beginning of list first = newLink; // first --> newLink else // not at beginning previous.next = newLink; // old prev --> newLink newLink.next = current; // newLink --> old currnt } // end insert() // ------------------------------------------------------------- public Link remove() // return & delete first link { // (assumes non-empty list) Link temp = first; // save first first = first.next; // delete first return temp; // return value } // ------------------------------------------------------------- public void displayList() { Link current = first; // start at beginning of list while(current != null) // until end of list, { current.displayLink(); // print data current = current.next; // move to next link } } } // end class SortedList //////////////////////////////////////////////////////////////// class PriorityQ { private SortedList theList; //------------------------------------------------------------- public PriorityQ() // constructor { theList = new SortedList(); } //------------------------------------------------------------- public void insert(long item) // insert item { // TBD - NEED TO DO INSERT HERE } //------------------------------------------------------------- public long remove() // remove minimum item { // TBD - THIS SHOULD REMOVE THE FIRST ITEM FROM AND LIST AND RETURN THE DATA VALUE OF THE LINK REMOVED } //------------------------------------------------------------- public boolean isEmpty() // true if queue is empty { // TBD - THIS SHOULD RETURN WHETHER THE QUEUE IS EMPTY OR NOT } //------------------------------------------------------------- } // end class PriorityQ //////////////////////////////////////////////////////////////// class PriorityQApp { public static void main(String[] args) { PriorityQ thePQ = new PriorityQ(); thePQ.insert(30); thePQ.insert(50); thePQ.insert(10); thePQ.insert(40); thePQ.insert(20); while( !thePQ.isEmpty() ) { long item = thePQ.remove(); System.out.print(item + " "); // 10, 20, 30, 40, 50 } // end while System.out.println(""); } // end main() //------------------------------------------------------------- } // end class PriorityQApp