Assignment

The purpose of this assignment is practicing priority queues implemented as a single linked list.

The Problem

1. In this assignment you will implement a priority queue as a linked list based data structure. Your reading book offers a good guide for the design and implementation, see the class LinkedQueue, pp 395 - 397 in Chapter 7. For the sake of simplicity your classes do not have to be generic. Name your class LinkedPriorityQueue.

2. A Node class supporting the list will be needed as usual, reuse the Node class from HW4. Review your HW 4 and section 5.4 pp 283 - 285 from your book, but replace the generic code with a plane non-generic choice; use String for type of data. Your simplified Node class will need the following members only:

• Fields for data and link
• Getter and setters
• Initializer constructor
• The recursive toString() method from HW 4
• A new version of the static method listCopyWithTail( ) since the list now will have several tail references, one for each priority level
• All other methods are optional

3. The behavior of add and remove operations of LinkedPriorityQueue must satisfy the following requirements:

• Elements of the queue always removed at the head of the list that is, head will be the front of the queue (like in the LinkedQueue)

• The highest priority elements are stored in the initial section of the list, the next priority level follows the initial section etc. You can visualize this list such that each priority level is a linked list of its own, and then the lists are appended one after each other in the order of decreasing priority

• A rear reference must be maintained for each priority level, these are the tail nodes of the priority levels; except for 0 level the links in these tails are not null but rather the first node of the next lower priority (a ‘deputy head')

• Additional care is needed when some or all of the priority levels are empty

• Adding an element to the queue must be done at the rear that corresponds to the priority of the element

• Extra care needed when an element is added to the empty queue

4. The implemented methods listCopyWithTails( ) from Node, add( ) and remove( ) from LinkedPriorityQueue must be tested and the results verified on the console

5. Determine the big-Oh for each method and append your comments after the Test class

Design and RequirementsNode class

1. The simplified Node class will need only the following members:

• Fields for data and link
• Getters and setters
• Initializer constructor
• The recursive toString() method from HW 4
• A new version of the static method listCopyWithTail( ) since the list now will have several tail references, one for each priority level •All other methods are optional

2. Define a new method listCopyWithTails ( ). The method takes an array of nodes from the list for parameter. The array contains the head, the tail and possibly additional in-between nodes from the list; all these nodes follow each other in the order of decreasing index. The method makes a copy of the linked list and returns an array of new nodes that contains the head of the new list and additional nodes which are copies of the corresponding nodes of the parameter array.

LinkedPriorityQueue class

1. Fields

• An array of nodes named rears; stores the tail of the priority groups as subarrays; if a priority group is empty, its rear reference is null
• front; the head reference of the entire linked list

2. Methods

• Constructor initializing the rears array

• remove( ): Removes the front as usual; returns the data of the removed element

• add( ): adds a new element to the list at the rear of the priority group where the element belongs to. Note that the nodes in the list do not know their priority level, the level is determined by their position in the list. For this reason the add( ) method takes two parameters, a String for data and an int for the priority level. Implementation significantly harder than that of the original add. If p is the priority level and front is null (empty list) or rears[p] is not null, addition is obvious. However, careful selection logic is needed when the priority group of level p is empty.

• displayQueue( ): prints the data of all queue elements to the console (optional)

Testing

1. Define a Test class with the main method to exercise your code

• Instantiate a Node array of length 4 ( we deal with 4 priority levels 0,1,2,3)

• Instantiate a LinkedPriorityQueue object, use the array for parameter

• Test the add() method: run a for loop to add at least 15 different String elements to various priority levels

• Call toString() with respect to front to display the list on the console; verify that each priority group is indeed a contiguous sub-list within the queue and that the higher the priority the nearer to the front (you may also use your displayQueue method if implemented).

• Test the remove() method; remove at least 5 elements and display the queue again on the console

• Copy your queue to test your listCopyWithTails( ) method from the Node class, the parameter array contains the front and the elements of the rears array. Test that the method works correct even if some of the rears are null. Notice that if say rears[2] is null, then it is not a node in the list!

Output template

Priority level: 3
data: ant0
link: data: ant12
link: data: ant8
rears[3]: data: ant4

Priority level: 2 link: data: ant3 link: data: ant11 rears[2]: data: ant7
Priority level: 1
link: data: ant2
link: data: ant14
link: data: ant10
rears[1]: data: ant6

Priority level: 0 link: data: ant1 link: data: ant13 link: data: ant9 rears[0]: data: ant5 link: null in tail!