Abstract Data Types

A data type is a set of values and a set of operations on those values that can be used by some client. (In Java, the client is often another class.) An abstract data type (ADT) is a special type of data type, whose internal representation is hidden from the client.

However, clients must have some way to communicate with and employ the ADT. The specific ways in which a client can interact with a client is described through something called an Application Programming Interface (API). The API can be thought of as a contract between the ADT and the client. It guarantees the type of data that can be stored in the ADT and what actions can be taken with that data. To this end, an API will specify what constructors and instance methods the ADT will make available.

The one thing an ADT does not reveal is how this data is stored or what internal mechanisms are used to accomplish the actions that the API guarantees can be taken. There are many benefits to this separation of interface and implementation:

  • Using this design, one creates modular, reusable libraries
  • Different implementations have different strengths and weaknesses. With there often being no clear winner, many implementations get written and clients can select the best implementation for what they are trying to accomplish
  • With regard to performance, having multiple implementations allows one to use an optimized implementation when it matters, and something more quick-and-dirty if it doesn't. (e.g., when one is prototyping a program)

In Java, we implement ADTs as classes. In keeping with the "contract" defined by the API, constructors and instance methods specified in the API are typically declared as public. However, in order to keep the internal mechanisms of the ADT hidden from the client, instance variables and instance methods used to organize the internal computations of the class are typically declared to be private.

When we create objects of some implemented ADT, or invoke instance methods to operate on these, we are said to be "using" the ADT.

There are many, many types of ADTs. Just as a few examples:

  • The standard system ADTs in Java include the Integer, Double, String, StringBuilder, etc..
  • ADTs that facilitate organizing and processing data include Point2D, Interval1D, Date, etc..
  • Still other ADTs that facilitate organizing and manipulating collections of data or objects include Stack, Queue, Priority Queue, ArrayList, etc...

We will focus initially on the ADTs in this last group -- those that work with collections of data or objects. These are fundamental data types when it comes to computer programming.