Exercise 1. Make a ListPriorityQueue class that's implemented as a linked list like I did with the ListStack class. Have the queue store a collection of ints, and use each int for the priority. The class can have this interface:

public class ListPriorityQueue {
    ...
    void insert(int k) { ... }; 
    int extractMax() { ... };
    int max() { ... };
    boolean isEmpty() { ... };
    ...
}  

1. Insert new items into the front of the list (like we did with the stack). To find the max, then, your code needs to search through the linked list nodes to find the smallest-valued item. Also, to extractMax, you will have to search through the linked list to find the largest-valued item, and remove it.

   With this option, list item removal is tricky. To remove a node in the middle of the list, you have to change the node's predecessor's next field to refer instead to the node's successor node.

2. Insert new items into the list in priority order so that the highest-priority item is at the front of the list.

   With this option, list insertion is tricky. To insert a node into the middle of the list, you have to find the node's predecessor and successor nodes, change the node's next field to refer to the successor, and change the predecessor node's next field to refer to the inserted node.