Abstract Data Types

The List interface says that a list (that is, any class that implements it) can add, remove, get, set, report its size, and so on. It does not say anything about how any of that is done. That separation is the idea behind an abstract data type, or ADT.

A data type is a description of some kind of data and the operations allowed on it. For example, the int data type describes the set of all integers that fit in a 32-bit memory block. It also describes the operations that can be performed on those integers: addition, subtraction, multiplication, and division.

The word “abstract” means the description of the data type does not depend on any particular implementation. An ADT lets us reason about a data type without worrying about how it is implemented. In more formal settings, an ADT is often described by an algebraic specification, a set of axioms that formalize the expected behavior. For example, an axiom for a list could say that after add(x), the size is one more than before. Another axiom could state an invariant such as: the size is never negative.

It is often said that a data structure is an implementation of an ADT. DynamicArray and LinkedList are two data structures that implement the same List ADT, so code written against List works with either one. We will follow this pattern in the rest of the course: we will define an ADT, then implement it with one or more data structures.

Most programming languages do not support formally specified ADTs. In Java, the closest construct is the interface, which is what we used for List. An abstract class comes close too, but it can also hold fields and method bodies, so it can mix in the implementation.