The concept of data structures is closely related to another important concept in computer science called abstract data types. Recall the definition of a data type: "a data type consists of the values it represents and the operations defined upon it." You are already familiar with some basic data types such as integers and characters. These data types are found in nearly all computers, and they have well-defined operations that can be done with them. For example, the integer data type has operations for addition, subtraction, multiplication, and division. The computer knows how to perform these arithmetic operations with any two integers because these operations are part of the integer data type.

We can extend the idea of data types to include more than just the basic data types. Our definition of data types consists of two parts: 1) values, and 2) operations. Now suppose we extended our definition so that the first part included data structures. This extension makes sense because our data structures are really just novel ways of organizing values. We have already seen several examples of these extended or abstract data types (ADTs). The examples that we studied are listed below.

Data Structure Operations Abstract View
Ordered List    AddListItem(List, Item)
   RemoveListItem(List, Item)
Stack    Item  PushStackItem(Stack, Item)
   Item  PopStackItem(Stack)
Queue    Item  EnqueueItem(Queue, Item)
   Item  DequeueItem(Queue)

Notice that each of the ADTs above has the two elements required by our definition: 1) a particular data structure, and 2) operations related to the data structure. We call these data types "abstract" because we have said nothing about how they are implemented. Instead, we have defined an interface for using the data type which consists of certain operations. The interface for an ADT remains the same regardless of how the data structure and operations are implemented. For example, we can use the stack ADT in a computer program by using the two operations defined in the stack interface. We do not need to know whether these operations were implemented using a linked list or an array.

Now let's consider how to create a new ADT using our definition. First, we must choose a particular data structure. Remember that data structures are simply ways of organizing data in the computer. For our ADT, we will use a bag data structure. This structure is based on the idea of storing various items into a bag just as you might put various groceries in a grocery bag. We want our data structure to have the same properties that real bags have.

Second, we need to define an interface for our ADT by specifying the operations it will support. Since we are modeling a bag, we will choose operations that give our data structure the same functionality that a grocery bag might have. The applet below shows the interface for our data structure as a row of buttons. Try each of the operations to discover how the bag ADT works. You will be asked to describe these operations in the review questions.