What is the difference between an abstract data type (ADT) and a data structure ?
The question above can be reframed in a more concrete manner by asking this question:
What is the difference between an array and a stack ?
An array is a data structure while a stack is an abstract data type.
An abstract data type (ADT) is a specification for how an ‘data’ interface should behave without any reference to its actual implementation.
The wikipedia definition of an ADT is as follows:
An abstract data type is defined as a mathematical model of the data objects that make up a data type as well as the functions that operate on these objects.
From the NIST Dictionary of Algorithms and Data structures we have the following definition of an ADT:
A set of data values and associated operations that are precisely specified independent of any particular implementation.
Thus in the case of a stack, it exhibits Last In First Out (LIFO) behavior when elements are added to and removed from it. The concrete implementation of the ADT is where the data structure comes in. Thus a Stack can be implemented as an array or as a linked list.
This might lead us to conclude that an ADT is more a theoretical or abstract concept, while the data structure has more to do with the concrete implementation.
Under the definitions above, the following constructs are ADTs:
- Priority Queue
- Binary Tree
while these are data structures:
- linked list
- hash map/dictionary
We can gain a better understanding of this when we consider these constructs in Java.
The ADT corresponds to the interface type, while the data structure would correspond to the concrete class.Thus a Java array, ArrayList, LinkedList, HashMap are actually data structures and the corresponding interfaces they implement would be equivalent to ADTs.
See this article for more about abstract data types in Java