What is the connection between data structures and data types?

Question

I have read some books and wikipedia, which seem to give not completely consistent definitions and notations. I try to understand the concepts, regardless of what they are called. Here are what I have figured (please correct me) and would like to ask :

1. a (abstract) data type is a set $D$ of values, together with some operations on it (each $n$-ary operation is a mapping $D^n \to D$). E.g. The set of all the integers with arithmetic operations on it forms a data type.
2. A data structure seems to be a data type. Or are they the same concept? What is the formal definition of a data structure?

3. I have some difficulty in understanding if a "container-like construct" is a data structure or data type, or the set of all of them is. What I mean by a "container-like construct", is some set of values, but with some relation(s) on the set, e.g. a queue, a graph, a stack, an array, a map, .....

   E.g., a queue is a set of values in it, with some ordering on the values according to which value was added earlier than which. Is a queue with a fixed size and fixed elements, as a set of values in it, a data type or a data structure? Or do all the queues form a data type or a data structure? Are adding and removing elements from a queue, which obviously create new queues, viewed as operations on the set of all the queues?

   Similarly, a graph is a set of vertices and has relation between the vertices being the edges. Is a graph with fixed vertices and edges a data type or a data structure, or is the set of all the graphs a data type or a data structure? Are transformations from a graph to another different graph considered to be operations on the set of all the graphs? Is searching for a vertex in a graph considered to be an operation on that single graph?

Answer 1

I agree with your definition of abstract data type. (A domain of values, together with some operations on that domain.)

I typically use the term data structure to refer to implementation techniques for data types. Examples of data structures are things like balanced binary trees and hashtables.

For example consider the data type set of integers, with operations like union, intersection, is_member?, and insert_member.

You could implement the data type with at least three different data structures, each of which has advantages and disadvantages. For example, you could implement your set using a balanced binary tree (like a red-black tree, for example). Each node in the tree represents a member of the set, insertion and membership tests take $O(\log n)$. Or, if your sets are over a finite (and relatively small) universe of items you could implement it with a bit array. This is an array of $U$ bits (where $U$ is the size of the universe.) Inserting element $i$ just means setting the $i$^th bit, testing for membership just means testing the $i$^th bit. But now intersection (respectively union) requires you to take the binary-and (respectively or) of $U$ bits, which kind of stinks when you have sets with just a few elements in them. Similarly with hash table implementations, insertion and testing are nice (on average), but intersection and union can be somewhat more complicated to do efficiently.

Answer 2

This is a very simplified view. For a formal approach, you need to look at type theory.

There is no real difference. Data structures are just standardized types and type constructors (such as tuple or list), with associated primitives operations, that are convenient for building other types with usually a very direct implementation, and are predefined in the kernel of your programming language.

An abstract data type is defined as an abstract domain D, with its primitive operations, which is implemented by defining a mapping so some (more concrete?) type defined with the preexisting constructors. The primitive operations are also implemented as function using the primitive operations available for the more concrete implementation. Then there is an encapsulation mecanism so that the concrete implementation is hidden, and only the abstract part is usable in the program.

This abstract data type can be a constructor when its definition depends on some other yet unspecified type.

Then we can remark that:

• the data structure types defined by the programming languages are themselves abstractions: a domain of value and its primitive operations. It is seen as concrete because it is mapped in simple ways on the computer hardware.

• the definitition of an abstract data type may well use another previouly defined abstract data type for its implementation.

Hence there is no reason to make a difference.

However, the expression "data structure" refers generally to the types obtained with the primitive types and constructors of the programming language.

As a reply to some comments, and to make things clearer:

I can define a balanced tree (pick your preferred flavor) as an ADT, call it Balanced, implemented with the more elementary types provided by the language, possibly parameterized by the type of the data it contains (which would rather make it an ADT constructor, to use my informal terminology). Then I can used this ADT Balanced to build another ADT called Set for sets, as suggested in the answer of Wandering Logic. Then I can use the ADT Set to implement some other ADT XXX.

Note that I could be more specific and actually call my ADT Red-Black, with a corresponding implementation, if I want to suggest that it will have exactly all the properties of red-black trees. It will nevertheless be an ADT, since the program will be allowed to use only the given primitives, without being allowed to fiddle with the pointers of the implementation at the risk of bugging the structure.

Then people may consider that data-structures are what is used for implementation, while ADTs are the abstraction that is built with the data structure. I will not fight it as this is terminology, and it does not really matter to me (see further comments below). But, then, I will point out that Balanced, or Set, are clearly ADTs when being defined, but become data structures when looked at from the point of view of the other ADTs they are used to implement.

This only confirms what I said. They are the same.

I know "we eat beef and pork rather than cow and pig", but these four names cover only two species, and the difference is only in the use made of the animal. Whether an ADT is pork or pig may be convenient terminology, may indicate a difference in intent, or a difference of perspective, but not a difference in substance.

Another issue raised in that context is that of complexity, as if it mattered more when looking at data structure, at implementation.

An immediate consequence of what I just said is that there cannot be any difference on that basis. When I implement the ADT Balanced, I am of course very careful to have a good implementation. And the complexity characteristics of the functions associated with that ADT (insertion, deletion, traversal, ...) are of course part of the specification, though that is usually implicit in the program, as well as other interesting properties of the abstraction (quite often). Then I can rely on the complexity of the Balanced primitives to analyse the complexity of whatever is implemented using Balanced.

When I use the ADT Balanced as data structure to implement the ADT Set, I will again be careful to get good complexity of its primitive operations (such as union or intersection of Set values) which will be (possibly implicitely) part of the Set interface specification. So, when I analyse the complexity of the ADT XXX, I can simply rely on what I know of the complexity of Set.

And this is very much what we do when studying the complexity of intricate algorithms. We rely on existing, well analysed constructs, and seldom look into the way they were themselves designed and analyzed. This is the essence of abstraction, and it is only the classical way of doing Mathematics. When we use a theorem, we do not have to think about its proof (Thanks to Curry and Howard for their support in this discussion).

Now I gave my view of the use of the terminology. It may be outdated, I do not know. But I would not worry a second about it since the two expression denote the same substance anyway. The difference, if any, is in the way you want to look at that substance. My own perception is that the only concrete difference is between the fact that original data types of the language are hard-coded by the compiler and have to be taken as they are, while all others, user or library defined abstract data types, can be re-implemented if need be. As I perceive that as the only significant difference, I rather use the extra word data structure to identify that. It may be that there is a different consensus in some communities, actually shared by the answer of Wandering Logic. A justification for it is that people could use the implementation based on other types without ever abstracting it, which would support the idea of having a specific name for it (I often just use the word implementation).

Then, just to make things a bit more confused, the Wikipedia page for Data Structure talks also of Abstract Data Structure, wich a link to ... Abstract Data Type.

Somehow, I strongly doubt there is an official unified terminology for all this. Except probably when giving formal definitions using type theory.