Abstract Data Types

The data types we have looked at so far are all concrete, in the sense that we have completely specified how they are implemented. For example, the Card class represents a card using two integers. As I discussed at the time, that is not the only way to represent a card; there are many alternative implementations.

An abstract data type, or ADT, specifies a set of operations (or methods) and the semantics of the operations (what they do) but it does not not specify the implementation of the operations. That's what makes it abstract.

Why is that useful?

• It simplifies the task of specifying an algorithm if you can denote the operations you need without having to think at the same time about how the operations are performed.
• Since there are usually many ways to implement an ADT, it might be useful to write an algorithm that can be used with any of the possible implementations.
• Well-known ADTs, like the Stack ADT in this chapter, are often implemented in standard libraries so they can be written once and used by many programmers.
• The operations on ADTs provide a common high-level language for specifying and talking about algorithms.

When we talk about ADTs, we often distinguish the code that uses the ADT, called the client code, from the code that implements the ADT, called provider code because it provides a standard set of services.