abstract data types we now turn our attention to selecting data structure for implementing the bag adt the possible candidates at this point include the list and dictionary structures the list can store any type of comparable objectincluding duplicates each item is stored individuallyincluding duplicateswhich means the reference to each individual object is stored and later accessible when needed this satisfies the storage requirements of the bag adtmaking the list candidate structure for its implementation the dictionary stores key/value pairs in which the key component must be comparable and unique to use the dictionary in implementing the bag adtwe must have way to store duplicate items as required by the definition of the abstract data type to accomplish thiseach unique item can be stored in the key part of the key/value pair and counter can be stored in the value part the counter would be used to indicate the number of occurrences of the corresponding item in the bag when duplicate item is addedthe counter is incrementedwhen duplicate is removedthe counter is decremented both the list and dictionary structures could be used to implement the bag adt for the simple version of the baghoweverthe list is better choice since the dictionary would require twice as much space to store the contents of the bag in the case where most of the items are unique the dictionary is an excellent choice for the implementation of the counting bag variation of the adt having chosen the listwe must ensure it provides the means to implement the complete set of bag operations when implementing an adtwe must use the functionality provided by the underlying data structure sometimesan adt operation is identical to one already provided by the data structure in this casethe implementation can be quite simple and may consist of single call to the corresponding operation of the structurewhile in other caseswe have to use multiple operations provided by the structure to help verify correct implementation of the bag adt using the listwe can outline how each bag operation will be implementedan empty bag can be represented by an empty list the size of the bag can be determined by the size of the list determining if the bag contains specific item can be done using the equivalent list operation when new item is added to the bagit can be appended to the end of the list since there is no specific ordering of the items in bag removing an item from the bag can also be handled by the equivalent list operation the items in list can be traversed using for loop and python provides for user-defined iterators that be used with bag from this itemized listwe see that each bag adt operation can be implemented using the available functionality of the list thusthe list is suitable for implementing the bag