38

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?

Community
  • 1
  • 1
zwol
  • 135,547
  • 38
  • 252
  • 361
  • 3
    A **data structure** is a set of data considered as one entity (thing). An int, for example, is a simple variable, cannot be considered as a data structure, but an array is a data structure (an array is a composed variable). A **data type** is a set of data and operations on them. The main difference between the two is that the operations are not included in the first case. An **abstract data type** is a mathematical model of a data structure and operations on them. In other words, an ADT is an interface to what a DS is the implementation. – Maxim Chetrusca Aug 18 '14 at 05:26

3 Answers3

44

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.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • 2
    Sir , i do not understand what is the difference between abstract data type and data type ? – Suraj Jain Oct 20 '16 at 12:22
  • @SurajJain An ADT is an abstraction of a data structure that refers only abstractly to the data. It describes the interface and behaviors of the data structure, but not the data layout. A data type is *less* abstract than a data structure. A concrete implementation of a data structure in a particular language produces a data type in that language. – Alan May 30 '19 at 13:41
  • 1
    An `abstract data type` is a data type **without** an **__implementation__**, it leaves the choice of implementation to the programmer, synonymous to an `interface`. See [this](https://docs.python.org/3/library/abc.html#module-abc) for a Python implementation. – nosahama May 03 '20 at 14:25
19

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).

Femaref
  • 60,705
  • 7
  • 138
  • 176
  • Great !!! Thanks!!! – beginner Sep 06 '17 at 07:15
  • 2
    Atom works as an analogy because, while it can technically be split, so can data types. Strings can be split into characters. Integers can be split into bits. Regardless, data types, like atoms, represent fundamental units within a particular domain. – svadhisthana Mar 22 '19 at 05:25
4

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.

jun
  • 127
  • 2
  • 1
    There is another, more common meaning of data structure than the C language construct *struct* -- see templatetypedef's answer below. – Andy Thomas Jan 07 '11 at 21:45
  • it could also be a class which is basically a struct with methods. so what? – jun Jan 07 '11 at 22:08