Explain the difference between a data *structure* and a data *type* [closed]

Question

While trying to answer What is the difference between a composite data type and a data structure? I realized that while I have a clear idea of what a data type is, and how it is not the same thing as a data structure, I cannot put the difference into words. If you were teaching an intro CS course, how would you explain the difference?

Answer 1

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.

Answer 2

Data type can't be reduced anymore, while a data structure can, as it consists of multiple fields of different data.

However, most likely, I would use an analogy - a data type is an atom, while data structures are molecules. (yes, I know, atoms can be split etc, but the analogy should hold up for the purpose).

Answer 3

data type is any type including the base types likes int but also extending to structures. structures are always made up of base types and/or other structures.

So int is a datatype but not a structure. Whereas struct point { int x; int y; } is both a structure and a datatype.