define map adt map is container for storing collection of data records in which each record is associated with unique key the key components must be comparable map()creates new empty map length ()returns the number of key/value pairs in the map contains key )determines if the given key is in the map and returns true if the key is found and false otherwise addkeyvalue )adds new key/value pair to the map if the key is not already in the map or replaces the data associated with the key if the key is in the map returns true if this is new key and false if the data associated with the existing key is replaced removekey )removes the key/value pair for the given key if it is in the map and raises an exception otherwise valueofkey )returns the data record associated with the given key the key must exist in the map or an exception is raised iterator ()creates and returns an iterator that can be used to iterate over the keys in the map list-based implementation we indicated earlier that many different data structures can be used to implement map since we are trying to replicate the functionality of the dictionary provided by pythonwe don' want to use that structure that leaves the use of an array or list as with the set adtboth the array and list structures can be usedbut the list is better choice since it does not have fixed size like an array and it can expand automatically as needed in the implementation of the bag and set adtswe used single list to store the individual elements for the map adthoweverwe must store both key component and the corresponding value component for each entry in the map we cannot simply add the component pairs to the list without some means of maintaining their association one approach is to use two listsone for the keys and one for the corresponding values accessing and manipulating the components is very similar to that used with the bag and set adts the differencehoweveris that the association between the component pairs must always be maintained as new entries are added and existing ones removed to accomplish thiseach key/value must be stored in corresponding elements of the parallel lists and that association must be maintained