ordered list beginning with the memory usagewe note that the space required for list-based dictionary with entries is ( )since the linked list data structure has memory usage proportional to its size in additionwith this implementation of the dictionary adtwe can realize operation insert(kveasily and efficientlyjust by single call to the add last method on swhich simply adds the new entry to the end of the list thuswe achieve ( time for the insert(kvoperation on the dictionary unfortunatelythis implementation does not allow for an efficient execution of the find method find(koperation requiresin the worst casescanning through the entire list sexamining each of its entries for examplewe could use an iterator on the positions in sstopping as soon as we encounter an entry with key equal to (or reach the end of the listthe worst case for the running time of this method clearly occurs when the search is unsuccessfuland we reach the end of the list having examined all of its entries thusthe find method runs in (ntime similarlytime proportional to is needed in the worst case to perform remove(eoperation on dif we assume that entries do not keep track of their positions in thus the running time for performing operation remove(eis (nalternativelyif we use location-aware entries that store their position in sthen we can perform operation remove(ein ( time (see section the operation find all always requires scanning through the entire list sand therefore its running time is (nmore preciselyusing the big-theta notation (section )we say that operation find all runs in th(ntime since it takes time proportional to in both the best and worst case in conclusionimplementing dictionary with an unordered list provides for fast insertionsbut at the expense of slow searches and removals thuswe should only use this implementation where we either expect the dictionary to always be small or we expect the number of insertions to be large relative to the number of searches and removals of coursearchiving database and operating system transactions are precisely situations such as this neverthelessthere are many other scenarios where the number of insertions in dictionary will be roughly proportional to the number of searches and removalsand in these cases the list implementation is clearly inappropriate the unordered dictionary implementation we discuss next can often be usedhoweverto achieve fast insertionsremovalsand searches in many such cases hash table dictionary implementation we can use hash table to implement the dictionary adtmuch in the same way as we did for the map adt the main differenceof courseis that dictionary allows