A logical description of the data and the operations that can manipulate it - independent from implementation (the data structure)
-
An ADT is defined by its behaviour from the user point of view - what does it do?
- e.g.: Possible values, operations on data, behaviour of operations
- Treat it as a black box - when we initiate a list in Python, we don’t really care if it’s being done as a linked list or an array
-
A data structure is the implementation of an ADT - how it does the operations defined in the ADT
- i.e.: An ADT is to a data structure what an interface is to a class
-
Different ADTs can be implemented using the same data structure
Primitive data types
Integers, strings, booleans are all ADTs (defined values and operations)
- Programming languages implement these ADTs via a data structure, usually built-in
Example
A map/dictionary is an ADT
- The ADT specifies its data structure implementation must support key-value pairs, search based on keys, insertion, etc
- The map ADT can be implemented by multiple different data structures, for example, arrays or linked lists