2
$\begingroup$

I don't get what is the difference between a Data Type and Data Structure.

As per Wikipedia, "Some types are very useful for storing and retrieving data and are called data structures". But:

  • Is there a clear threshold of "usefulness for storing and retrieving data" that separates a data structure and a data type?
  • Can't the above usefulness be implemented in the data type itself? If yes, would that provide any benefit?

Examples are very much welcome.

Improve this question
$\endgroup$
3
  • $\begingroup$ There isn't a formal definition of "data structure", but it includes various things that are data type constructors, such as lists, maps, queues, etc. Your second question is unclear: which "the data type" are you referring to? Many data structures can be implemented using data types in functional languages, see e.g. Okasaki's thesis. $\endgroup$
    – Naïm Favier
    Commented Aug 3 at 18:56
  • $\begingroup$ I'm not sure I got your examples; can't lists maps and queues be implemented as (abstract) data types as well? $\endgroup$
    – Andrea Nerla
    Commented Aug 4 at 10:55
  • $\begingroup$ Regarding my second point, let's take as example a hash map: can't every of its aspects be defined in a "hash map" abstract data type? If yes, would that have any advantage or drawback? $\endgroup$
    – Andrea Nerla
    Commented Aug 4 at 10:59

1 Answer 1

Reset to default
1
$\begingroup$

Your Wikipedia source formally treats data structure as a sub type of the most general data type, which is a foundational concept just like the foundational concept of set in mathematics where all objects of interest are sets.

In computer science and computer programming, a data type (or simply type) is a collection or grouping of data values, usually specified by a set of possible values, a set of allowed operations on these values, and/or a representation of these values as machine types.

Under this view, your source correctly lists the main useful concrete data structure types as array, record (tuple), object, linked list, binary tree, while treats list, stack, map, tree, graph, queue, set, etc as abstract data types (ADTs) which are all essentially interface specs without implementation details. So the threshold here for data structure is clearly strict for only a few concrete data types, and apart from ADTs you have other types such as pointer and reference types, function type for functional programming languages, dependent type and algebraic types for proof-assistant or other specialized areas. And of course data structure's usefulness can be implemented in the data type itself, such as the binary tree data structure can be viewed as a specific implementation of the tree ADT.

Informally we just treat data type and data structure as two different aspects where data type is a classification that specifies which type of value a variable can hold and what operations can be performed on that value, while data structure defines how data is stored and accessed in memory to support efficient operations.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I get baffled sometimes at how the nomenclature is imprecise even in sucjects like computer science and how it impacts learning that subject. $\endgroup$
    – Andrea Nerla
    Commented Aug 14 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.