A data structure is an abstract description of a way of organizing data to allow certain operations on it to be performed efficiently. For example, a binary tree is a data structure, as is a Fibonacci heap, AVL tree, or skiplist. Theoreticians describe data structures and prove their properties in order to show that certain algorithms or problems can be solved efficiently under certain assumptions.
A data type is a (potentially infinite) class of concrete objects that all share some property. For example, “integer” is a data type containing all of the infinitely many integers, “string” is a data type containing all of the infinitely many strings, and “32-bit integer” is a data type containing all integers expressible in thirty-two bits. There is no requirement that a data type be a primitive in a language – for example, in C++, the type int is a primitive, as is this one:
struct MyStruct {
int x, y;
};
In this case, MyStruct is a data type representing all possible objects labeled MyStruct that have two ints in them labeled x and y.
It is possible to have a data type representing all possible instances of a data structure. For example, you could encode a binary search tree with this data type:
struct BST {
int data;
BST* left, *right;
};
In short, a data structure is a mathematical object with some set of properties that can be realized in many different ways as data types. A data type is just a class of values that can be concretely constructed and represented.