chap listsstacksand queues space overhead will not be great simple class for representing key-value pairs is shown in figure the insert method of the dictionary class supports the key-value pair implementation because it takes two parametersa record and its associated key for that dictionary now that we have defined the dictionary adt and settled on the design approach of storing key-value pairs for our dictionary entrieswe are ready to consider ways to implement it two possibilities would be to use an array-based or linked list figure shows an implementation for the dictionary using an (unsortedarray-based list examining class ualdict (ual stands for "unsorted array-based list)we can easily see that insert is constant time operationbecause it simply inserts the new record at the end of the list howeverfindand remove both require th(ntime in the average and worst casesbecause we need to do sequential search method remove in particular must touch every record in the listbecause once the desired record is foundthe remaining records must be shifted down in the list to fill the gap method removeany removes the last record from the listso this is constant-time operation as an alternativewe could implement the dictionary using linked list the implementation would be quite similar to that shown in figure and the cost of the functions should be the same asymptotically another alternative would be to implement the dictionary with sorted list the advantage of this approach would be that we might be able to speed up the find operation by using binary search to do sofirst we must define variation on the list adt to support sorted lists sorted list is somewhat different from an unsorted list in that it cannot permit the user to control where elements get inserted thusthe insert method must be quite different in sorted list than in an unsorted list likewisethe user cannot be permitted to append elements onto the list for these reasonsa sorted list cannot be implemented with straightforward inheritance from the list adt the cost for find in sorted list is th(log nfor list of length this is great improvement over the cost of find in an unsorted list unfortunatelythe cost of insert changes from constant time in the unsorted list to th(ntime in the sorted list whether the sorted list implementation for the dictionary adt is more or less efficient than the unsorted list implementation depends on the relative number of insert and find operations to be performed if many more find operations than insert operations are usedthen it might be worth using sorted list to implement the dictionary in both casesremove requires th(ntime in the worst and average cases even if we used binary search to cut down on the time to