## 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:

- Stack
- Queue
- Bag
- List
- Priority Queue
- Trie
- Heap
- Binary Tree
- Set
- Map

while these are data structures:

- array
- 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