8.2. Introduction to ADTs

An Abstract Data Type (ADT) is a high-level (abstract) description of the operations (methods) available on a collection of data. They do not specify how the methods are implemented as there can be many possible implementations in practice.

In this chapter, we will focus on the List ADT. You could implement a list (like the grocery list in the previous section) using either an array or a linked list. However, when you talk about the List ADT, the conversation is centered around the operations you can perform on the list instead of the underlying structure used to store the data.

Important

You can think of an ADT as a well-documented interface that describes the data-related operations that implementing classes must have. As with other interfaces we have seen, the exact implementation details, including the underlying structure used to store the data, may vary with each implementing class.

In this chapter, we explain how the operations in the popular List ADT (interface) can be implemented using an array or a linked list. The first implementation, ArrayBasedList, uses an array, and the second, LinkedBasedList uses a linked list.

Both implementing classes fulfill the requirements outlined in the documentation for the List ADT in different ways. Thanks to polymorphism, code written to use the List interface will work regardless of whether the underlying object is an ArrayBasedList or a LinkedBasedList!

Note

There are often many useful implementations for a given ADT (many more than just two). The decision of which implementation to use depends on which one would be more efficient for the application at hand.

Another Real World Analogy (Vending Machine)

Consider a vending machine description as a physical analogy for an ADT. Actions (methods) performed on the vending machine affect the underlying data (the items in the machine). From the outside perspective, users of a vending machine are only concerned with whether or not a machine can vend. They don’t necessarily care how a machine vends. An operation for a vending machine might be described by the following method:

  • void vendItem(double payment, int item) throws UnavailableItemException, InsufficientPaymentException

    • Users should be able to call the method vendItem, specifying a payment amount and item number. If valid input is supplied, then the vending machine should vend the item to the user.

    • If the item is unavailable, then the method throws an UnavailableItemException which causes the vending machine’s display to update accordingly.

    • Likewise, if an insufficient amount for the specified item is supplied, then the method throws an InsufficientPaymentException which also causes the vending machine’s display to update accordingly.

In this analogy, we have a VendingMachine ADT with one operation called vendItem. Not only should any vending machine implementation have a vendItem operation, but it should operate, from the user’s perspective, as described in the ADT description.

Rapid Fire Review

  1. What is an Abstract Data Type (ADT)?

    1. A low-level description of a data structure’s implementation.

    2. A predefined class in the Java library.

    3. A high-level description of the operations available on a collection of data.

    4. A specific method for implementing data structures in Java.

  2. Which of the following is an example of an ADT operation mentioned in the text?

    1. initialize()

    2. displayItem()

    3. vendItem()

    4. purchaseItem()

  3. How does polymorphism relate to ADTs in Java?

    1. Polymorphism allows multiple ADTs to be defined within the same class.

    2. Polymorphism enables the List interface to be implemented by different classes, like ArrayBasedList and LinkedBasedList.

    3. Polymorphism is only applicable when using arrays as underlying structures.

    4. Polymorphism is not used in conjunction with ADTs.

  4. Why is it beneficial to have different implementations of an ADT like the List interface?

    1. It allows the programmer to access more methods.

    2. It simplifies the process of writing new code.

    3. It eliminates the need for interfaces in Java.

    4. It provides flexibility in choosing an implementation that is more efficient for the specific application.

  5. Given the VendingMachine ADT described in the text, what would happen if a user inputs an insufficient amount for an item?

    1. The vending machine will return the item and display an error message.

    2. The vendItem method will throw an InsufficientPaymentException.

    3. The machine will dispense the item regardless of the amount.

    4. The machine will reset and ask for the correct amount.