implementation with sorted list an alternative implementation of priority queue uses positional listyet maintaining entries sorted by nondecreasing keys this ensures that the first element of the list is an entry with the smallest key our sortedpriorityqueue class is given in code fragment the implementation of min and remove min are rather straightforward given knowledge that the first element of list has minimum key we rely on the first method of the positional list to find the position of the first itemand the delete method to remove the entry from the list assuming that the list is implemented with doubly linked listoperations min and remove min take ( time this benefit comes at costhoweverfor method add now requires that we scan the list to find the appropriate position to insert the new item our implementation starts at the end of the listwalking backward until the new key is smaller than an existing itemin the worst caseit progresses until reaching the front of the list thereforethe add method takes (nworst-case timewhere is the number of entries in the priority queue at the time the method is executed in summarywhen using sorted list to implement priority queueinsertion runs in linear timewhereas finding and removing the minimum can be done in constant time comparing the two list-based implementations table compares the running times of the methods of priority queue realized by means of sorted and unsorted listrespectively we see an interesting tradeoff when we use list to implement the priority queue adt an unsorted list supports fast insertions but slow queries and deletionswhereas sorted list allows fast queries and deletionsbut slow insertions operation len is empty add min remove min unsorted list ( ( ( (no(nsorted list ( ( (no( ( table worst-case running times of the methods of priority queue of size nrealized by means of an unsorted or sorted listrespectively we assume that the list is implemented by doubly linked list the space requirement is (