Data Types and Structures

An abstract data type or, in the theoretical context explored here, simply a data type, defines a model for a container of data. This model defines:

• The values applicable to the type;
• The operations which can be performed on the type; and
• The behaviour of these operations.

Conversely, a data structure is a concrete definition of the layout of data and related metadata. A data structure can be used to implement one or more abstract data types.

Tip

This distinction is particularly visible in some java types: for example the Queue and List interfaces are abstract data types implemented by the LinkedList class (data structure), among others.

Whilst an abstract data type may have possible implementations using many data structures, they are likely to have differing space and time complexities.

Some important data types include:

• AVL Trees
• Binary Heaps
• Queues