Abstract Data Type

Recall the definitions of "data type" and "data structure" from previous chapters:

A data type consists of a type (a collection of values) together with a collection of operations to manipulate the type.

A data structure encapsulates organized mechanisms for efficiently storing, accessing & manipulating data.

Recall that I have previously mentioned any data type (even as simple as an integer) can be viewed as a simple data structure in the general sense.

Now, I introduce the concept of Abstract Data Types, sometimes abbreviated as ADT.

ADT is a description (representation) of some (type of) data and the operations that are allowed on that data, while abstracting (ignoring) implementation details.

ADT simply provides a minimal expected interface and set of behaviors without regard to how they will be implemented.

A data structure is an implementation of an ADT.

ADTs are used in the study of data structures, design and analysis of algorithms, programming languages, and software engineering.

  • ADTs are a theoretical concept. They are often described in terms of algebraic specifications with axioms that formalize the operations and their expected behaviors.

  • Most programming languages do not directly support formally specified ADTs. In programming languages that support object-oriented programming, the abstract class construct comes close to the specification of an ADT.

For example, the abstract class Roster can be seen as an ADT for "roster" which lays out the interface of its core operations add, remove and find. It is essential that these operations are not implemented (otherwise, it would not be an ADT). The responsibility of implementing the core operations falls on the data structures MoocRoster and JhuRoster.

To specify an ADT, we need to supplement the abstract class construct with proper documentation and a suite of tests. We will explore these in later lessons and chapters.

Resources

I found Eric Elliott's post on Medium Abstract Data Types and the Software Crisis an interesting read. You may want to check it out.