implementation with an unsorted list in our first concrete implementation of priority queuewe store entries within an unsorted list our unsortedpriorityqueue class is given in code fragment inheriting from the priorityqueuebase class introduced in code fragment for internal storagekey-value pairs are represented as compositesusing instances of the inherited item class these items are stored within positionallistidentified as the data member of our class we assume that the positional list is implemented with doubly-linked listas in section so that all operations of that adt execute in ( time we begin with an empty list when new priority queue is constructed at all timesthe size of the list equals the number of key-value pairs currently stored in the priority queue for this reasonour priority queue len method simply returns the length of the internal data list by the design of our priorityqueuebase classwe inherit concrete implementation of the is empty method that relies on call to our len method each time key-value pair is added to the priority queuevia the add methodwe create new item composite for the given key and valueand add that item to the end of the list such an implementation takes ( time the remaining challenge is that when min or remove min is calledwe must locate the item with minimum key because the items are not sortedwe must inspect all entries to find one with minimum key for conveniencewe define nonpublic find min utility that returns the position of an item with minimum key knowledge of the position allows the remove min method to invoke the delete method on the positional list the min method simply uses the position to retrieve the item when preparing key-value tuple to return due to the loop for finding the minimum keyboth min and remove min methods run in (ntimewhere is the number of entries in the priority queue summary of the running times for the unsortedpriorityqueue class is given in table operation len is empty add min remove min running time ( ( ( (no(ntable worst-case running times of the methods of priority queue of size nrealized by means of an unsorteddoubly linked list the space requirement is (