2.2 Selecting a Data Structure

The implementation of a complex abstract data type typically requires the use of a data structure for organizing and managing the collection of data items. There are many different structures from which to choose. So how do we know which to use? We have to evaluate the suitability of a data structure for implementing a given abstract data type, which we base on the following criteria:

1. Does the data structure provide for the storage requirements as specified by the domain of the ADT?

   Abstract data types are defined to work with a specific domain of data values. The data structure we choose must be capable of storing all possible values in that domain, taking into consideration any restrictions or limitations placed on the individual items.

2. Does the data structure provide the necessary data access and manipulation functionality to fully implement the ADT?

   The functionality of an abstract data type is provided through its defined set of operations. The data structure must allow for a full and correct implementation of the ADT without having to violate the abstraction principle by exposing the implementation details to the user.

3. Does the data structure lend itself to an efficient implementation of the operations?

   An important goal in the implementation of an abstract data type is to provide an efficient solution. Some data structures allow for a more efficient implementation than others, but not every data structure is suitable for implementing every ADT. Efficiency considerations can help to select the best structure from among multiple candidates.

Storage Requirements

We now turn our attention to selecting a 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 object, including duplicates. Each item is stored individually, including duplicates, which means the reference to each individual object is stored and later accessible when needed. This satisfies the storage requirements of the Bag ADT, making the list a 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 ADT, we must have a way to store duplicate items as required by the definition of the abstract data type. To accomplish this, each unique item can be stored in the key part of the key/value pair and a 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 a duplicate item is added, the counter is incremented; when a duplicate is removed, the counter is decremented.

Both the list and dictionary structures could be used to implement the Bag ADT. For the simple version of the bag, however, the list is a 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.

Functional Requirements

Having chosen the list, we must ensure it provides the means to implement the complete set of bag operations. When implementing an ADT, we must use the functionality provided by the underlying data structure. Sometimes, an ADT operation is identical to one already provided by the data structure. In this case, the implementation can be quite simple and may consist of a single call to the corresponding operation of the structure, while in other cases, we have to use multiple operations provided by the structure. To help verify a correct implementation of the Bag ADT using the list, we can outline how each bag operation will be implemented:

• An 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 a specific item can be done using the equivalent list operation.
• When a new item is added to the bag, it can be appended to the end of the list since there is no specific ordering of the items in a bag.
• Removing an item from the bag can be handled by the equivalent list operation.
• The items in a list can be traversed using a for loop and Python provides for user-defined iterators that can be used with a bag.

From this itemized list, we see that each Bag ADT operation can be implemented using the available functionality of the list. Thus, the list is suitable for implementing the bag.